백준 2164번: 카드2

https://www.acmicpc.net/problem/2164

1부터 N까지의 카드가 순서대로 있다고 하자.

이제 맨 위의 카드를 버리고, 그 다음 카드를 맨 아래로 옮겨준다.

이것을 마지막 1장 남을 때까지 반복하면 된다.

 

우선, 코드가 시키는 대로 코드를 짜봤다.

ArrayList에 수를 저장했고, while로 ArrayList의 크기가 1이 될 때까지 반복해주었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		ArrayList<Integer> aList = new ArrayList<>();
		for (int i = 0; i < N; i++) aList.add(i + 1);

		while (aList.size() > 1) {
			aList.remove(0);
			aList.add(aList.remove(0));
		}
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(aList.get(0) + "\n");
		bw.flush();
		bw.close();
	}
}

하지만 이 코드를 제출했을 때 시간 초과가 났다.

한 번은 코드가 더 빨리 실행되도록 코드를 봐꿔봤다.

예를 들어 1~6이 있다고 할 때 홀수번째는 사라지고 짝수번째는 순서대로 뒤에 다시 붙으므로

이걸 이용해서 코드를 만들려고 했으나 이것도 역시 실패했다.

그 다음에 큐(Queue)를 알게 됬다.

큐는 선입선출 방식을 따르는 자료구조로 해당 문제에 찰떡인 자료구조라고 생각했고,

시험삼아  기존 코드에 ArrayList를 Queue로 바꿔서 코드를 만들었는데 그걸로 문제를 풀 수 있었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		Queue<Integer> q = new LinkedList<>();
		for (int i = 0; i < N; i++) q.offer(i + 1);

		while (q.size() > 1) {
			q.remove();
			q.offer(q.remove());
		}

		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(q.peek() + "\n");
		bw.flush();
		bw.close();
	}	
}

고작 자료구조를 바꿔준다고 이런 극적인 변화가 나타날 줄은 몰랐는데,

이제 알게 됬으니까 앞으로는 사용하는 자료구조에 대해 좀 신경써야겠다.