문제

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

풀이 과정

이 문제에서 말하는 카드를 섞고 버리는 작업을 수행하기 위해서는 큐(Queue) 형태의 자료 구조를 활용하면 된다.

이미 큐에 대해서는 예전 문제에서 설명하였으니 아래 링크를 참고.

<BOJ - [Array - 10845 큐] - Silver IV🥈>

https://hoshi2710.github.io/백준/10845.html

이문제에서 반복되는 작업은 다음과 같다.

1. 제일 앞 카드를 버린다.
2. 그다음카드를 제일 뒤로 보낸다.

이 작업을 그대로 큐로 구현하면 쉽게 풀 수있는 문제다.

그러나 나는 이 문제를 풀기전에 알고리즘 분류를 확인하지 않고 접근 했기에 조금 다른 판단을 했다.

이 문제에서 주어진 자료를 일일히 옮기고 지우고 하는 작업을 하여 결과를 도출하면 시간이 훨씬 오래 걸리지 않을까?

지금와서 보면 많이 부족한 생각이었다는 판단이 든다. 시간제한이 2초정도면 꽤나 넉넉하게 주어진 것이기 때문이다.

사용한 알고리즘 개요

일단 내가 구현한 알고리즘은 아래와 같다. (카드 갯수 = n)

1. n을 2로 나눈다. (위 작업중 카드를 버리고 뒤로 보내는 작업 대체) 그다음 \(2^0\)의 값을 별도의 변수(이하 A라 지칭) 에 더하기 (\(2^0\)에서 0은 반복작업이 이루어진 횟수를 의미, 0부터 시작)
2. 나누기 전 값이 홀수라면 첫번째 작업에서 카드를 버리기까지만 하고 뒤로 보내는 작업은 수행 안한것 이므로 다음 작업에서는 작업을 거꾸로(역방향) 하는 것으로 기억. ( 짝수면 그대로 작업)
3. 이번에도 n을 나누는데 만약 위에서 작업을 거꾸로 하는 것으로 기록 되었다면 1번에서 나눈 값에 1을 더하고 다시 2로 나눈다. (정방향이면 1번과 동일한 작업 진행)
4. 2번과 동일한 조건기준으로 역방향, 정방향을 판단하고, 여기에 추가조건으로 3번 작업이 역방향인지 정방향인지 확인후 아래 처럼 결과를 도출(XOR 연산)

1. 3번과 4번작업을 나누는 값이 1보다 값이 큰 동안 계속 반복한다.
2. 1번에서 언급한 별도의 변수 A를 결과값으로 출력한다.

단순글 로만 표현하자니 내가 적었지만 이해하기 어려운것 같다. 그나마 쉽게 요약하면

이 알고리즘에서는 위 문제를 카드를 버리고 섞는 작업으로 카드가 한바퀴 순환했을때를 한 단위로 잡아 연산을 진행하도록 하였다.

그림으로 표현하면 이렇게 되고 코드는 아래와 같다.

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

public class Main
{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine()),gap = 1,result = 1;
		boolean reverse = false;
		for(int count=n; count > 1; gap*=2) {
		  int beforeCount = count;
		  if(!reverse) {
		      count /= 2;
		      result += gap;
		  }
		  else {
		      count = (count+1)/2;
		  }
		  reverse ^= (beforeCount%2 == 1);
		}
		bw.write(Integer.toString(result)+"\n");
		bw.flush();
		bw.close();
	}
}

큐(Queue)를 이용한 풀이방법 과의 비교

큐을 활용해서 풀었을때 먼저 N개의 카드를 모두 버리고 뒤로넘기는 작업을 진행하고 대략 N/2개의 카드를 동일한 작업을 반복한다.

반면 내가 진행한 일종의 분할 정복법으로 했을때 카드에 해당하는 자료를 직접 접근하지 않고 큐 접근법에서 N,N/2,N/4 … 씩으로 카드의 갯수만 계산해서 결과를 도출한다.

따라서 두 방법을 각각 알고리즘으로 구현했을때 대략적인 시간 복잡도는 다음과 같다.

• 큐 활용 : \(O(n \times log(n))\)
• 분할법 활용 : \(O(log(n))\)

따라서 이 문제가 의도한 방법으로 푼것은 아니긴 하나, 효율 측면에서만 봤을때는 위에서 설명한 알고리즘이 상대적으로 더 효율적이었음을 확인할 수 있었다.