[백준 2840] 행운의 바퀴

최민길(Gale)·2023년 5월 31일
1

알고리즘

목록 보기
72/172

문제 링크 : https://www.acmicpc.net/problem/2840

이 문제는 문제의 조건을 구현하는 구현 문제입니다. 문제에서는 원판이 돌아가고 바늘이 고정되어 있는데 배열에서 이를 편하게 사용하기 위해 바늘을 움직이고 원판을 고정하는 방식으로 진행하면 됩니다. 즉 문제에서 화살표가 가리키는 글자가 몇 번 바뀌었는지는 다시 말하면 바늘이 얼마나 움직였는지를 의미하고, 그 글자는 움직인 위치의 글자가 됩니다.

여기서 주의할 점은 !를 출력하는 경우의 수 입니다. 크게 다음과 같습니다.

  1. 배열이 ?가 아닌데 입력받은 문자 역시 아닌 경우
  2. 입력받은 문자가 이미 다른 곳에서 사용되었는데 현재 인덱스의 문자와 다른 경우

여기서 1번째는 쉽게 추론할 수 있지만 2번째의 경우 쉽게 알아채기 힘듭니다. 보통 1번에 포함된다고 생각하기 쉬운데요, 2번의 경우도 가능하니 꼭 관련 처리를 해주셔야 합니다.

다음은 코드입니다.

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

class Main{

    public static void main(String[] args) throws Exception{
        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());

        String[] wheel = new String[N];
        Arrays.fill(wheel,"?");
        boolean[] check = new boolean[26];

        int idx = 0;
        for(int i=0;i<K;i++){
            st = new StringTokenizer(br.readLine());

            int n = Integer.parseInt(st.nextToken());
            String s = st.nextToken();

            idx += (n%N);
            if(idx >= N) idx -= N;

            if(!wheel[idx].equals(s) && !wheel[idx].equals("?")){
                System.out.println("!");
                return;
            }

            int ascii = s.charAt(0)-'A';
            if(check[ascii] && !wheel[idx].equals(s)){
                System.out.println("!");
                return;
            }
            wheel[idx] = s;
            check[ascii] = true;
        }



        int cnt = N;
        while(cnt-- >0){
            System.out.print(wheel[idx]);
            idx--;
            if(idx<0) idx=N-1;
        }
    }
}

profile
저는 상황에 맞는 최적의 솔루션을 깊고 정확한 개념의 이해를 통한 다양한 방식으로 해결해오면서 지난 3년 동안 신규 서비스를 20만 회원 서비스로 성장시킨 Software Developer 최민길입니다.

0개의 댓글