dev blog

[백준/2747] 피보나치 수

작성일 2018-09-28 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 2747

Review

본격 DP 들어가기 전에 한번 풀어본 문제.
메모이제이션으로 풀었는데도 시간 초과가 떠서 당황하게 만들었던 문제다.
알고 보니 내 코드에 문제가 있는 거였음. 역시 컴파일러는 거짓말을 안 한다… ㅜ
일단 전역으로 배열 선언한 다음 메인 함수에서 초기화를 해준다.
이때 입력값보다 1을 더해서 배열의 크기를 정해주어야 한다.
예를 들어 0부터 10까지의 피보나치 수열을 구한다면, 배열의 크기는 0~10까지인 총 11이 되어야 하기 때문이다.
그리고 피보나치 수열을 구하는 함수에서 배열에 값을 넣어주면 된다.
나는 배열을 지역 변수로 선언했다가 시간 초과를 보았다… ㅡㅡ;;
사실 1003 문제 풀고 싶었는데… 온갖 삽질로 시간 초과만 보다가 결국 풀지 못했다.
1003은 다음 기회에… 꼭 플고 만다.

Code (JAVA)

import java.io.*;

public class Main {
  static int[] memo;
  public static int fibonacci(int n) {
    

    if (n <= 1) {
      memo[n] = n;
      return n;
    } else if (memo[n] != 0) {
      return memo[n];
    } else {
      return memo[n] = fibonacci(n-1) + fibonacci(n-2);
    }
  }
  
  public static void main(String args[]) throws IOException{
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int input = Integer.parseInt(bf.readLine());
    memo = new int[input + 1];
    System.out.println(fibonacci(input));
  }
  
}

[백준/10824] 네 수

작성일 2018-09-27 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 10824

Review

백준 강의에서 한 번 나왔던 문제다.
입력 조건 안 보면 런타임 에러 나오기 딱 좋음.
엄청 쉬운 문제이지만 입력 범위 때문에 long으로 형변환을 해서 출력을 해야하는 함정을 가지고 있음.

Code (JAVA)

import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException{
    
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    String[] line = bf.readLine().split(" ");
    
    String a = line[0] + line[1];
    String b = line[2] + line[3];
    
    long ans = Long.valueOf(a) + Long.valueOf(b);
    System.out.println(ans);
  }
    
}

[백준/11655] ROT 13

작성일 2018-09-27 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 11655

Review

알파벳은 총 26자니 절반을 딱 나누어 A부터 M까지는 13을 더해주고, N부터 Z까지는 13을 빼주면 되는 문제임.

Code (JAVA)

import java.util.Scanner;

public class Main {
  public static void main(String args[]){

    Scanner sc = new Scanner(System.in);
    String input = sc.nextLine();

    char arr[]=input.toCharArray();

    for(int i = 0; i < input.length(); i++) {
     if(arr[i]>='a' && arr[i]<='m') {
       arr[i] += 13;
     } else if(arr[i]>='n' && arr[i]<='z'){
       arr[i] -= 13;
     } else if(arr[i]>='A' && arr[i]<='M') {
       arr[i] += 13;
     } else if(arr[i]>='N' && arr[i]<='Z') {
       arr[i] -= 13;
     }
    }
      System.out.println(arr);
    }

}

[백준/11656] 접미사 배열

작성일 2018-09-27 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 11656

Review

문자열 하나씩 잘라 ArrayList에 넣은 다음에 Collections.sort()로 정렬하면 된다.

Code (JAVA)

import java.util.*;

public class Main {
  public static void main(String args[]) {
    
    Scanner sc = new Scanner(System.in);
  
    String input = sc.nextLine();
    ArrayList<String> arr = new ArrayList<String>();
    
    for(int i = 0; i < input.length(); i++) {
      arr.add(input.substring(i, input.length()));
    }
    
    Collections.sort(arr);
    
    for (String i : arr) {
      System.out.println(i);
    }
    
  }
    
}

[백준/10808] 알파벳 개수

작성일 2018-09-24 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 10808

Review

배열 하나 만들고 아스키코드상 a를 배열 인덱스 0으로 만든 다음 해당 문자의 배열값을 증가시키면 되는 문제.

Code (JAVA)

import java.util.Scanner;

public class Main {
  public static void main(String args[]){
    
    Scanner sc = new Scanner(System.in);
    String input = sc.next();
    
    int[] abc = new int[26];
    
    for(int i = 0; i < input.length(); i++) {
      abc[input.charAt(i) - 'a']++;
    }
    
    for(int i = 0; i < abc.length; i++) {
      System.out.print(abc[i] + " ");
    }
    
    sc.close();
  }
}

[백준/10809] 알파벳 찾기

작성일 2018-09-24 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 10809

Review

배열의 값이 -1일때만 배열의 값을 바꿔주면 된다.

Code (JAVA)

import java.util.Scanner;

public class Main {
  public static void main(String args[]){
    
    Scanner sc = new Scanner(System.in);
    String input = sc.next();
    
    int[] abc = new int[26];
    
    for(int i = 0; i < abc.length; i++) {
      abc[i] = -1;
    }
    
    for(int i = 0; i < input.length(); i++) {
      if(abc[input.charAt(i) - 'a'] == -1) {
        abc[input.charAt(i) - 'a'] = i;
      } 
    }
    
    for(int i = 0; i < abc.length; i++) {
      System.out.print(abc[i] + " ");
    }
    
    sc.close();
  }
}

[백준/10820] 문자열 분석

작성일 2018-09-24 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 10820

Review

문자열 갯수가 정해지지 않아 입력 받기가 어려웠던 문제.
hasNextLine() 하나 배웠다.

Code (JAVA)

import java.util.Scanner;

public class Main {
  public static void main(String args[]){
    
    Scanner sc = new Scanner(System.in);
    String input;
    int upper;
    int lower;
    int num;
    int space;
 
    while(sc.hasNextLine()) {
      upper = 0; lower = 0; num = 0; space = 0;
      input = sc.nextLine();
      
      for(int i = 0; i < input.length(); i++) {
        int c = (int)input.charAt(i);
        if(c>= 97 && c <=122) {
          lower++;
        } else if(c>= 65 && c <=90) {
          upper++;
        } else if(c>= 48 && c <=57 ) {
          num++;
        } else if(c==32) {
          space++;
        }
       }
       
       System.out.println(lower + " " + upper + " " + num + " " + space);
     }
    
    sc.close();
    }
    
}

[백준/10866] 덱

작성일 2018-09-23 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 10866

Review

이전에 풀었던 큐 문제를 수정해서 푼 문제.
맞게 푼 것 같은데 push_back()을 여러 번 반복할 때 제대로 출력이 되지 않음.
뭐 놓친 거 있나 싶어서 구글링 했는데 맞게 짠 것 같아서 당황… ㅡㅡ;;
맞왜틀의 늪에 빠져 이것저것 고쳐봤는데 알고 보니 또 입출력 문제였음.
Scanner 사용하니 제대로 출력이 된다.

Code (JAVA)

import java.util.*;

public class Main {
  public static void main(String args[]){
    
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    Deque deque = new Deque(n);
    for(int i=0;i<n;i++){
        String s=sc.next();
        if(s.equals("push_front")){
            int tmp=sc.nextInt();
            deque.push_front(tmp);
        }
        else if(s.equals("push_back")){
            int tmp=sc.nextInt();
            deque.push_back(tmp);
        }
        else if(s.equals("pop_front"))
          System.out.println(deque.pop_front());
        else if(s.equals("pop_back"))
          System.out.println(deque.pop_back());
        else if(s.equals("size"))
          System.out.println(deque.size());
        else if(s.equals("empty"))
          System.out.println(deque.empty());
        else if(s.equals("front"))
          System.out.println(deque.front());
        else if(s.equals("back"))
          System.out.println(deque.back());
    }
    
    sc.close();
  }
  
  static class Deque {
    private int[] array;
    private int rear;
    private int item;
    
    public Deque(int size) {
      rear = -1;
      array = new int[size];
    }
    
    public void push_front(int item) {
      rear++;
      for(int i = rear; i > 0; i--) {
        array[i] = array[i-1];
      }
      array[0] = item;
    }
    
    public void push_back(int item) {
      rear++;
      array[rear] = item;
    }
    
    public int pop_front() {
      if (rear==-1) {
        return -1;
      } else {
        item = array[0];
        for (int i = 0; i < rear; i++) {
          array[i] = array[i+1];
        }
        rear--;
        return item;
      }
    }
    
    public int pop_back() {
      if (rear==-1) {
        return -1;
      } else {
        item = array[rear];
        rear--;
        return item;
      }
    }
    
    public int size() {
      return rear+1;
    }
    
    public int empty() {
      if(rear==-1) {
        return 1;
      } else {
        return 0;
      }
    }
    
    public int front() {
      if(rear==-1) {
        return -1;
      }
      return array[0];
    }
    
    public int back() {
      if(rear==-1) {
        return -1;
      }
      return array[rear];
    }
  }
}

[백준/1978] 소수 찾기

작성일 2018-09-22 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 1978

Review

1과 자기 자신으로만 나누어지는 수를 카운트해서 출력하면 되는 문제.

Code (JAVA)

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		int input;
		int res=0;
		int mok1, mok2;
		
		for (int i=0; i<N; i++) {
			mok2=0;
			input = sc.nextInt();
			for(mok1=1; mok1<=input; mok1++) {
				if(input%mok1==0) mok2++;
			}
			if(mok2==2) res++;
		}
		
		System.out.println(res);
	}
}

[백준/1158] 조세퍼스 문제

작성일 2018-09-21 Edited on 2020-05-05 In 백준 Disqus:

Baekjoon Online Judge - 1158

Review

일단 큐 하나 만들고, m-1만큼 dequeue한 걸 다시 enqueue한 다음, 제일 앞에 있는 데이터를 dequeue하면 되는 문제.
또 출력 형식 때문에 삽질함… ㅜ ㅜ

Code (JAVA)

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String args[]) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    
    String[] line = bf.readLine().split(" ");
    
    int n = Integer.parseInt(line[0]);
    int m = Integer.parseInt(line[1]);
    
    Queue<Integer> queue = new LinkedList<Integer>();
    
    for (int i = 1; i<=n; i++) {
      queue.offer(i);
    }
    while(n-->0) {
      for(int i = 0; i < (m-1); i++) {
        queue.offer(queue.poll());
      }
      sb.append(queue.poll() + ", ");
      
    }
    System.out.print("<" + sb.toString().substring(0,sb.length()-2) + ">");
  }
}