숫자만 있는 문자열 s가 있고 두 개의 값과 b가 있다고 가정합니다. 다음 두 작업 중 하나를 s −
에 원하는 횟수와 순서로 적용할 수 있습니다.-
s(0-인덱싱)의 홀수 위치에 있는 모든 항목에 'a'를 추가합니다. 숫자가 9인 경우 무언가를 추가하면 0으로 다시 순환됩니다.
-
''를 오른쪽으로 b만큼 회전합니다.
따라서 위의 연산을 s에 여러 번 적용하여 얻을 수 있는 사전식으로 가장 작은 문자열을 찾아야 합니다.
따라서 입력이 s ="5323" a =9 b =2와 같으면 다음을 따르기 때문에 출력은 2050이 됩니다.
- 회전:"5323"
- 추가:"5222"
- 추가:"5121"
- 회전:"2151"
- 추가:"2050"
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 본 :=새로운 세트
- deq :=하나의 요소가 's'인 새 대기열
- deq가 비어 있지 않은 동안 do
- curr :=deq의 첫 번째 삭제된 요소
- 본 세트에 curr 삽입
- ad :=curr에 대해 주어진 추가 작업 수행
- 광고가 표시되지 않으면
- deq 끝에 광고 삽입
- 본 세트에 광고 삽입
- ro :=curr에 대해 회전 작업 수행
- ro가 보이지 않으면
- deq 끝에 ro 삽입
- 본 세트에 ro 삽입
- 최소값 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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