문제 개요
숫자로만 이루어진 문자열 s와 두 개의 정수 a, b가 주어졌다고 가정해 봅시다. 우리는 문자열 s에 대해 다음 두 가지 연산을 원하는 만큼, 임의의 순서로 적용할 수 있습니다.
문자열 s의 홀수 인덱스(0부터 시작)에 위치한 모든 자릿수에 a를 더합니다. 만약 더한 결과가 9를 초과하면 0부터 다시 순환(cycle)됩니다.
문자열 s를 오른쪽으로 b칸 회전시킵니다.
이때 위 연산들을 몇 번이든 적용했을 때 얻을 수 있는 문자열 중 사전순(lexicographically)으로 가장 작은 문자열을 찾아야 합니다.
예제 확인
예를 들어 s = "5323", a = 9, b = 2가 입력으로 주어지면 출력은 2050이 됩니다. 과정을 살펴보면 다음과 같습니다.
- 회전: "5323"
- 덧셈: "5222"
- 덧셈: "5121"
- 회전: "2151"
- 덧셈: "2050"
풀이 접근 방법
이 문제는 BFS(너비 우선 탐색) 방식으로 해결할 수 있습니다. 각 상태에서 가능한 두 연산(덧셈, 회전)을 모두 수행하며 도달 가능한 모든 문자열을 탐색한 뒤, 그중 최솟값을 반환하는 것입니다. 구체적인 단계는 다음과 같습니다.
- 방문 여부를 기록하기 위한 집합(seen)을 새로 생성합니다.
- 시작 문자열 s를 담은 큐(deq)를 생성합니다.
- 큐가 빌 때까지 다음을 반복합니다.
- 큐에서 맨 앞 요소 curr를 꺼내고, seen 집합에 삽입합니다.
- curr에 덧셈 연산(ad)을 수행하고, 아직 seen에 없다면 큐와 seen에 추가합니다.
- curr에 회전 연산(ro)을 수행하고, 아직 seen에 없다면 큐와 seen에 추가합니다.
- seen 집합에서 최솟값을 반환합니다.
구현 코드
아래 예제 구현을 통해 더 잘 이해해 보겠습니다.
from collections import deque
def add_(s, a):
res = ''
for idx, i in enumerate(s):
if idx % 2 == 1:
num = (int(i) + a) % 10
res += str(num)
else:
res += i
return res
def rotate_(s, b):
idx = len(s) - b
res = s[idx:] + s[0:idx]
return res
def solve(s, a, b):
seen = set()
deq = deque([s])
while deq:
curr = deq.popleft()
seen.add(curr)
ad = add_(curr, a)
if ad not in seen:
deq.append(ad)
seen.add(ad)
ro = rotate_(curr, b)
if ro not in seen:
deq.append(ro)
seen.add(ro)
return min(seen)
s = "5323"
a = 9
b = 2
print(solve(s, a, b))
입력
"5323", 9, 2
출력
2050
마무리
이 풀이의 핵심은 두 연산이 만들어낼 수 있는 모든 문자열 상태를 중복 없이 탐색하는 것입니다. 시간 복잡도는 상태의 수에 비례하며, 문자열 길이가 n일 때 회전 상태는 최대 n개이고 각 상태마다 덧셈 결과만큼 추가되므로 전체 탐색 공간이 제한적입니다. seen 집합을 활용해 이미 방문한 문자열을 건너뛰면 불필요한 계산을 줄여 효율적으로 최솟값을 찾을 수 있습니다.