BOJ2840 행운의 바퀴

 

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

2840번: 행운의 바퀴

 

 

 

• 문자를 칸에 대입하면서 위치가 겹치는 것에 대한 예외체크만 했었다.
• 문제 조건에 각 칸은 다른 문자라는 조건을 예외처리를 하지 않아서 원인을 찾느라 시간이 오래걸렸다.

원인을 찾은 반례
#input
4 4
1 A
1 A
1 A
1 A

#output
!

 

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));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] input = br.readLine().split(" ");
		int n = Integer.valueOf(input[0]);
		int m = Integer.valueOf(input[1]);
		
		String[] ans = new String[n];
		Arrays.fill(ans,"?");
		boolean[] visit = new boolean[n];
		boolean err = false;
		
		
		
		
		int point=0;
		for(int i=0; i<m; i++){
		    String[] temp = br.readLine().split(" ");
            int move= n-Integer.valueOf(temp[0])%n;
		    point+=move;
		    point%=n;
		    if(visit[point] && !ans[point].equals(temp[1])){
		        err=true;
		        break;
		    }
		    visit[point] = true;
		    ans[point] = temp[1];
        }
        
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n;j++){
                if( !ans[i].equals("?") && ans[i].equals(ans[j]) ) err = true;
            }
        }    
        
        
        
		if(err) bw.write("!");
		else{
		    for(int i=point;i<n;i++){
		        bw.write(ans[i]);
		    }
		    for(int i=0;i<point;i++){
		        bw.write(ans[i]);
		    }
		}
		
		
		
		bw.flush();
	}
}

 

 

import java.util.Arrays;
import java.util.Scanner;

class Main
{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int K = sc.nextInt();
        char[] ans = new char[N];
        Arrays.fill(ans, '?');

        int curIndex = 0;
        while (K-- > 0) {
            int backStep = sc.nextInt();
            char backAlphabet = sc.next().charAt(0);
            int nextIndex = ((curIndex - backStep) % N + N) % N;
            if (ans[nextIndex] == '?') ans[nextIndex] = backAlphabet;
            else if (ans[nextIndex] != backAlphabet) {
                System.out.println("!");
                return ;
            }
            curIndex = nextIndex;
        }

        boolean[] chk = new boolean[26];
        for (int i = 0; i < N; i++) {
            if (ans[i] == '?') continue;
            if (chk[ans[i] - 'A']) {
                System.out.println("!");
                return ;
            }
            chk[ans[i] - 'A'] = true;
        }

        for (int i = 0; i < N; i++)
            System.out.print(ans[(curIndex + i) % N]);
        System.out.println();
    }
}