백준 2840: 행운의 바퀴(java)

문제

---

풀이

 

이전의 유사한 유형과 마찬가지로 덱을 사용해 풀이했다. BufferedReader와 StringTokenizer를 이용하여 입력받고 분리하는 과정은 생략하도록 하겠다.

Deque<Character> wheel=new LinkedList<>();
for(int i=0; i<N; i++) {
	wheel.add('?');
}

바퀴의 문자들을 저장할 덱 wheel을 선언해 주고, N개의 '?'들을 초깃값으로 삽입한다. '?'으로 초기화하면 후에 바퀴를 돌리며 한 번도 방문되지 않은 값을 '?'로 따로 설정할 필요가 없다. 

 

이후 회전할 바퀴 수와 입력 문자를 저장할 rotate와 character 변수를 각각 만들어 준다. 이때 N+x바퀴를 돌리는 것은 x바퀴를 돌리는 것과 동일하므로 rotate = (입력값)%N 이다.

for(int j=0; j<rotate; j++) {	//회전 구현
	wheel.addFirst(wheel.removeLast());
}

rotate번째 칸 바로 앞의 칸까지의 값을 덱의 반대편으로 보내는 연산을 통해 바퀴의 회전을 구현했다.

char current=wheel.getFirst();	//적혀 있는 문자
			
if(wheel.contains(character) && current!=character) {
		//입력값과 동일한 문자가 덱에 이미 존재하고 그 문자가 다른 칸에 있을 때
		System.out.println('!');
		return;
}
			
if(current!='?') {	//이미 방문된 칸일 때
		if(current!=character) {	//입력값과 적혀 있는 값이 다르면
			System.out.println("!");
			return;
		}
		else	//입력값과 적혀 있는 값이 같으면
			continue;
}
else {
	//처음 오는 칸일 때
	wheel.removeFirst();	//기존 ?값 삭제
	wheel.addFirst(character);	//문자 삽입
	}
}

바퀴가 존재하지 않는 경우('!'이 출력되는 경우)는

  1. 서로 다른 칸에 같은 문자가 중복되어 존재할 때

  2. 회전된 칸에 이번에 입력한 문자와 다른 문자가 이미 존재할 때

이 두 경우이므로 if문을 이용해 잘 분리해 주어야 한다. 1, 2번 경우에 해당되지 않는다면 그냥 통과하거나 값을 삽입한다.

모든 경우를 잘 구현하지 않으면 오답이 된다. (1번 케이스를 구현하지 않아 3번 정도 틀린 듯)

 

전체 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int K=Integer.parseInt(st.nextToken());
		
		Deque<Character> wheel=new LinkedList<>();
		for(int i=0; i<N; i++) {
			wheel.add('?');
		}
		
		int rotate;
		char character;
		for(int i=0; i<K; i++) {
			st=new StringTokenizer(br.readLine());
			rotate=Integer.parseInt(st.nextToken())%N;
			character=st.nextToken().charAt(0);
			
			for(int j=0; j<rotate; j++) {	//회전 구현
				wheel.addFirst(wheel.removeLast());
			}
			
			char current=wheel.getFirst();	//적혀 있는 문자
			
			if(wheel.contains(character) && current!=character) {
				//입력값과 동일한 문자가 덱에 이미 존재하고 그 문자가 다른 칸에 있을 때
				System.out.println('!');
				return;
			}
			
			if(current!='?') {	//이미 방문된 칸일 때
				if(current!=character) {	//입력값과 적혀 있는 값이 다르면
					System.out.println("!");
					return;
				}
				else	//입력값과 적혀 있는 값이 같으면
					continue;
			}
			else {	//처음 오는 칸일 때
			wheel.removeFirst();	//기존 ?값 삭제
			wheel.addFirst(character);	//문자 삽입
			}
		}
		while(!wheel.isEmpty())
			System.out.print(wheel.remove());
	}
}

 

배열을 이용해서도 풀이할 수 있지만, 배열을 여러 개 선언해야 하고 변수도 많아 그냥 덱을 사용했다.

덱을 사용하면 회전 구현이 용이한 듯