[백준/Baekjoon] 2840번: 행운의 바퀴

1. 문제

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

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

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

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

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

2. 입력

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

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

3. 출력

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

4. 예제 입력 1

8 8
4 V
3 I
7 T
7 A
6 R
5 N
1 O
9 H

5. 예제 출력 1

HONITAVR

6. 풀이

상당히 어려운 문제인데, 문제 자체의 난이도보다는 문제를 이해하는 것과 문제가 요구하는 조건을 모두 만족하는 데에 어려움이 있다. 문제의 조건을 정리해보면 다음과 같다.

1. 이미 알파벳이 존재하는 곳에 다른 알파벳이 존재하려 하면 안된다. (즉, 종이에 해당하는 행운의 바퀴가 없다.)
   • 이미 존재하는 알파벳이 입력한 알파벳과 같다면 상관없다. 이는 바퀴가 한 바퀴 돌아서 같은 자리에 오는 경우를 떠올려보면 쉽게 이해할 수 있다.
2. 같은 글자는 두 번 이상 등장하지 않는다.
   • 그러나 ‘?’는 해당되지 않는다.
3. 1번 또는 2번을 만족하지 못하면 ‘!’를 출력한다.

이제 이를 구현해보자. 우선, 리스트의 모든 값을 ‘?’로 초기화한다.

data = ['?'] * n

1번에 해당되는 경우를 구현하면 다음과 같다.

for i in range(k):
    num, alphabet = input().split()
    idx = (idx + int(num)) % n  # 리스트가 원형이므로 n으로 나누었을 때의 나머지로 인덱스를 설정
    if data[idx] != '?':  # 이미 알파벳이 존재하는 경우
        if data[idx] == alphabet:  # 그러나 같은 알파벳이라면 상관없다.
            continue
        check = False  # 해당하는 행운의 바퀴가 없는 것으로 처리
    else:
        data[idx] = alphabet  # 위의 경우가 아니라면 알파벳을 삽입

2번에 해당되는 경우를 구현하면 다음과 같다.

for i in range(n):
    if data[i] == '?':  # '?'는 중복으로 존재할 수 있으므로 예외
        continue
    for j in range(i + 1, n):
        if data[i] == data[j]:  # 중복된 값이 존재하는 경우
            check = False  # 해당하는 행운의 바퀴가 없는 것으로 처리
            break

7. 코드

n, k = map(int, input().split())
data = ['?'] * n
idx = 0
check = True

for i in range(k):
    num, alphabet = input().split()
    idx = (idx + int(num)) % n
    if data[idx] != '?':
        if data[idx] == alphabet:
            continue
        check = False
    else:
        data[idx] = alphabet

for i in range(n):
    if data[i] == '?':
        continue
    for j in range(i + 1, n):
        if data[i] == data[j]:
            check = False
            break

if check:
    for _ in range(n):
        print(data[idx], end='')
        idx = (idx - 1) % n
else:
    print('!')