BOJ 2840 - 행운의 바퀴

문제

BOJ 2840 - 행운의 바퀴

N칸짜리 원형 바퀴가 있다. K번의 회전 정보(회전 칸 수, 해당 위치의 문자)가 주어질 때, 바퀴에 적힌 글자를 화살표 위치부터 시계 방향으로 출력하라. 모순이 발생하면 !를 출력한다.

입력

첫 줄에 N, K가 주어진다. 이후 K줄에 회전 칸 수와 문자가 주어진다.

출력

바퀴의 글자를 화살표부터 시계 방향으로 출력한다. 모순이 있으면 !를 출력한다. 알 수 없는 칸은 ?이다.

예제

풀이

원형 배열을 시뮬레이션하면서 회전과 문자 배치를 처리한다.

1. N칸의 배열을 ?로 초기화한다
2. 각 회전마다 배열을 회전시킨 뒤 현재 위치(인덱스 0)의 문자를 확인한다
3. 현재 위치가 ?이면 새 문자를 배치하되, 같은 문자가 다른 칸에 이미 있으면 모순(!)이다
4. 현재 위치에 이미 같은 문자가 있으면 넘어간다
5. 현재 위치에 다른 문자가 있으면 모순(!)이다
6. 모든 회전을 처리한 후 배열을 이어 출력한다

핵심 아이디어: 배열 슬라이싱으로 원형 회전을 구현하고, 두 가지 모순 조건(같은 위치에 다른 문자, 다른 위치에 같은 문자)을 검사한다.

코드

n, k = map(int, input().split())
circle = ["?"] * n
 
for i in range(k):
    spin = input().split()
    s = int(spin[0]) % n
    s_char = str(spin[1])
    circle = circle[-s:] + circle[:-s]
    if circle[0] == "?":
        if s_char in circle:
            print("!")
            break
        circle[0] = s_char
    elif circle[0] == s_char:
        continue
    else:
        print("!")
        break
else:
    print("".join(circle))

복잡도

• 시간: O(K * N) — 각 회전마다 배열 슬라이싱 및 문자 탐색
• 공간: O(N) — 바퀴 배열