백준 2164번 카드2 자바로 풀어 본 짧은 글

2164번 카드2

스터디를 시작했는데 거기서 풀기로한 문제중 하나
처음엔 그냥 하던대로 풀었더니 시간초과가 났다.(첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.) 범위가 큼

큐를 사용하는 문젠데 큐를 사용하지 않아서 상당히 비효율적인듯

직접 구현해보고자 했는데 솔직히 감이 안와서 메소드 활용했다.

큐에 있는 기본 메소드 몇개 사용하니까 금방풀림
--------

hint
Queue queue = new LinkedList<>(); 쓰자...

--------

Solution

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        Queue<Integer> queue = new LinkedList<>();
        int n = Integer.parseInt(br.readLine());
 
        for(int i = 0; i < n; i++){
            queue.add(i+1);
        }
 
        for(int i = 0; i < n-1; i++) {
            queue.remove();
            queue.add(queue.poll());
        }
        System.out.println(queue.peek());
    }
}

pollFirst메소드도 있는데 이건 생각 못했네
실행시간 - 196ms

 

아래 코드는 실패했던 코드

public class Main { // [BOJ] 2164번 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
 
        int n = Integer.parseInt(br.readLine());
        int length = 0;
        int[] a = new int[n];
        int temp = 0;
 
        for(int i = 0; i < a.length; i++){ // 값 초기화
            a[i] = i+1;
        }
 
        length = a.length - 1;
 
        while(length > 1){//index가 0이 될때까지
            temp = a[1];
            for(int i = 0; i < length-1; i++){
                a[i] = a[i+2];
            }
            length--;
            a[length] = temp;
        }
        System.out.println(temp);
    }
}
//시간초과 코드