[알고리즘] 백준 2840번 행운의 바퀴 문제 풀이

문제

상덕이는 최근에 행운의 바퀴를 구매했다. 상덕이는 바퀴의 각 칸에 알파벳 대문자를 아래 그림과 같이 적었다

 

바퀴에 같은 글자는 두 번 이상 등장하지 않는다. 또, 바퀴는 시계방향으로만 돌아간다. 바퀴 옆에는 화살표가 있는데, 이 화살표는 항상 한 곳을 가리키고 있으며, 돌아가는 동안 가리키는 글자는 바뀌게 된다. 위의 그림에서는 H를 가리키고 있다.

상덕이는 바퀴를 연속해서 K번 돌릴 것이다. 매번 바퀴를 돌릴 때 마다, 상덕이는 화살표가 가리키는 글자가 변하는 횟수와 어떤 글자에서 회전을 멈추었는지를 종이에 적는다.

희원이는 상덕이가 적어놓은 종이를 발견했다. 그 종이를 바탕으로 상덕이가 바퀴에 적은 알파벳을 알아내려고 한다.

상덕이가 종이에 적어놓은 내용과 바퀴의 칸의 수가 주어졌을 때, 바퀴에 적어놓은 알파벳을 알아내는 프로그램을 작성하시오

 

입력

첫째 줄에 바퀴의 칸의 수 N과 상덕이가 바퀴를 돌리는 횟수 K가 주어진다. (2 ≤ N ≤ 25, 1 ≤ K ≤ 100)

다음 줄부터 K줄에는 바퀴를 회전시켰을 때 화살표가 가리키는 글자가 몇 번 바뀌었는지를 나타내는 S와 회전을 멈추었을 때 가리키던 글자가 주어진다. (1 ≤ S ≤ 100)

출력

첫째 줄에 마지막 회전에서 화살표가 가리키는 문자부터 시계방향으로 바퀴에 적어놓은 알파벳을 출력한다. 이때, 어떤 글자인지 결정하지 못하는 칸은 '?'를 출력한다. 만약, 상덕이가 적어놓은 종이에 해당하는 행운의 바퀴가 없다면 "!"를 출력한다. 

 

 

백준 2840 행운의 바퀴 문제는 순환배열을 얼마나 잘 사용을 하느냐의 문제 입니다. 

1차원 배열에서 N만큼의 Index를 벗어났을때 다시 0번으로 Index를 처리할 수 있는지를 확인 하는 문제 입니다. 

 

아래는 해당 문제의 코드를 정리한 것입니다. 

import java.util.*; import java.io.*; public class Solution{ static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static StringTokenizer st; // 화전판의 칸의 수 N static int N; //회전판을 돌리는 횟수 static int K; public static void main(String[] args) throws IOException{ st = new StringTokenizer(br.readLine()); //회전판의 칸 N = Integer.parseInt(st.nextToken()); //N칸의 회전판을 ?로 채우기 char[] wheel = new char[N]; //wheel이라는 문자 배열을 ?로 초기회 한다.  for(int i =0; i <N; i++) { wheel[i] = '?'; } //화전파을 돌리는 횟수를 입력 받는다.   K = Integer.parseInt(st.nextToken()); //현재의 시작 배열 인덱스를 0으로 초기화 한다.  int currentIndex =0; //입력 받은 K만큼 반복 한다.  while(K-- > 0) { //이동 칸수와 이동 후 나타나는 문자를 입력을 스트링 토크나이저로 입력  받는다.  st = new StringTokenizer(br.readLine()); //이동할 회전파읜 칸수를 step이라는 변수에 입력 받는다.  int step = Integer.parseInt(st.nextToken()); //step만큼 이동 했을때 나오는 문자를 입력 받는다. char cha = st.nextToken().charAt(0); //STEP 만큼 이동 했을때 다음 Index를 계산한다, 이때 회전판의 칸수 N을 넘어 나면 안되니 보정한다.   int nextIndex = ((currentIndex - step) % N + N) %N; //step만큼 입력 했을때 해당 인덱스의 값이 초기화 값인 ?면 현재 입력 받은 문자 값을 wheel 배열에 입력 if(wheel[nextIndex] == '?') { wheel[nextIndex] = cha; } //step만큼 이동 했을때 입력받은 cha와 wheel 배열의 값이 다르면 "!"를 출력 하과 while문 종료. else if(wheel[nextIndex] != cha) { System.out.println("!"); return; } //currentIndex에 구해진 nextIndex값을 입력 하고 다음 step과 문자를 입력 받는다.  currentIndex = nextIndex; } //k만큼의 회전판을 돌린 후 currentIndex의 배열에서 부터 시계 방향으로 wheel의 입력 밧을 출력한다. %N은 인덱스값을  //보정하기 위해 사용한다.  for(int i =0; i <N; i++) { Systehttp://m.out.print(wheel[(currentIndex + i) %N]); } System.out.println(); } }