[백준] 2840: 행운의 바퀴 (Java)

Yoon Uk·2022년 7월 9일

Java 백준 시뮬레이션 알고리즘

알고리즘 - 백준

목록 보기

24/130

문제

BOJ 2840: 행운의 바퀴 https://www.acmicpc.net/problem/2840

처음에 했던 잘못 된 풀이

잘못된 풀이

제출한 결과 java.lang.ArrayIndexOutOfBoundsException이 떴다.

잘못된 코드

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

public class Main {
	
	static int N, K;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken()); // 바퀴 칸의 수
		K = Integer.parseInt(st.nextToken()); // 바퀴 돌리는 횟수
		
		char[] wheel = new char[N]; // 바퀴
		boolean[] isIn = new boolean[N]; // 이미 채워져 있는지 확인
		boolean[] az = new boolean[26]; // A: 0, Z: 25
		int nextIdx = 0;
		boolean isAlready = false; // 자리에 이미 있는지 판별
		boolean isSame = false; // 같은 문자가 다른자리에 또 있는지 판별
		int asci = 0;
		for(int i=0; i<K; i++) {
			String str = br.readLine();
			
			int changeCnt = str.charAt(0) - '0';
			char c = str.charAt(2);
			asci = (int)c - 65; // 문자를 아스키코드를 사용해 정수로 바꿈
			
			nextIdx += changeCnt;
			if(nextIdx >= N) {
				while(nextIdx >= N) {
					nextIdx -= N;
				}
			}
			
			// 받은 문자가 또 들어오면
			if(az[asci]) {
				isSame = true; // 같은 문자가 들어왔다고 전환
				// 그런데 같은 문자가 같은 자리에 삽입된거면
				if(wheel[nextIdx] == c) {
					isSame = false;
				} else {
					break;
				}
			}
			// 삽입하려는 자리가 이미 채워져 있다면
			if(isIn[nextIdx]) {
				isAlready = true; // 이미 있다고 전환
				// 그런데 그 자리가 같은 자리였다면
				if(wheel[nextIdx] == c) {
					isAlready = false;
				} else {
					break;
				}
			}
			
			wheel[nextIdx] = c;
			isIn[nextIdx] = true;
			az[asci] = true;
			
		}	
		
		if(isAlready || isSame) {
			sb.append('!');
		} else {
			int cnt = 0;
			int pushIdx = nextIdx;
			while(true) {
				if(cnt == N) break; // 문자 모두 출력하면 탈출
				// 맨 뒤로 인덱스 넘김
				if(pushIdx < 0) {
					pushIdx = N-1;
				}
				
				if(isIn[pushIdx]) {
					sb.append(wheel[pushIdx]);
				} else {
					sb.append('?');
				}
				
				pushIdx--;
				cnt++;
			}
			
		}
		
		System.out.println(sb);
	}
	
}

정답 풀이

바퀴에 중복된 문자가 있으면 안된다.
바퀴는 시계방향으로 돈다. == 화살표는 반시계방향으로 돈다.
화살표가 지나치는 문자의 갯수 S 가 최대 100이고 바퀴의 칸 N 은 최대 25이므로
한 번에 여러 바퀴를 돌릴 수 있다.
idx 값 처리를 해준다.
배열의 idx 자리에 이미 문자가 차 있고 그 문자가 입력받은 문자와 다르면 "!" 를 출력한다.
배열 arr 을 모두 탐색하며 ? 외에 중복되는 문자가 있다면 "!" 를 출력한다.
배열 arr 을 모두 출력한다.

코드

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

public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken()); // 바퀴 칸의 개수
		int K = Integer.parseInt(st.nextToken()); // 회전 횟수
		
		char[] arr = new char[N];
		Arrays.fill(arr, '?'); // 모든 칸에 '?'를 채운다.
	
		
		int idx = 0;
		for(int i=0; i<K; i++) {
			
			st = new StringTokenizer(br.readLine(), " ");
			// N은 최대 25, S는 최대 100이 나올 수 있으므로 한 번에 여러 바퀴를 돌릴 수 있다.
			int S = Integer.parseInt(st.nextToken());
			char c = st.nextToken().charAt(0);
			
			// 바퀴가 시계방향으로 돈다 == 화살표는 반시계방향으로 돈다
            // 여러 바퀴 돌 수 있으므로 나머지를 구해 idx가 바퀴 칸 갯수를 넘지 않도록 해준다.
			idx -= S % N;
			if(idx < 0) {
				idx += N;
			}
			
			// 이미 차 있는 자리에 다른 문자가 또 등장하면
			if(arr[idx] != '?' && arr[idx] != c) {
				System.out.println("!");
				return;
			}
			
			arr[idx] = c;
		}
		
		// 다른 자리에 같은 문자가 있으면
		for(int i=0; i<N; i++) {
			for(int j=i+1; j<N; j++) {
				if(arr[i] != '?' && arr[i] == arr[j]) {
					System.out.println("!");
					return;
				}
			}
		}
		
		// 출력
		for(int i=0; i<N; i++) {
			sb.append(arr[(idx + i) % N]);
		}
		
		System.out.println(sb);
	}
	
}