문제 정의
숫자 n이 주어졌을 때, 아래와 같은 규칙으로 생성되는 수열에서 n번째 값을 찾아야 합니다.
- xxy
- xxyxxy
- yxxyxx
- xyyxyy
- xyyxyyxyyxyy
- ...
수열 생성 규칙
첫 번째 항은 xxy이며, 다음 항부터는 아래 세 가지 연산을 순서대로 반복 적용해 만듭니다.
- 더블(Double) — 현재 문자열을 자기 자신과 이어 붙여 길이를 두 배로 만듭니다.
- 리버스(Reverse) — 직전 연산이 더블이었다면, 문자열을 거꾸로 뒤집습니다.
- 스왑(Swap) — 직전 연산이 리버스였다면, 모든 x를 y로, y를 x로 바꿉니다.
예를 들어 입력이 n = 5라면 출력은 "yyxyyxyyxyyx"입니다.
처음 몇 항의 변화 과정
- 시작:
xxy - 더블 →
xxyxxy - 리버스 →
yxxyxx - 스왑 →
xyyxyy - 더블 →
xyyxyyxyyxyy - 리버스 →
yyxyyxyyxyyx(5번째 값)
접근 방법
세 가지 연산이 3단계 주기로 반복되므로, 반복 횟수 i를 3으로 나눈 나머지 값에 따라 적용할 연산을 결정하면 간단하게 해결할 수 있습니다.
- i := 0, ret := "xxy"로 초기화합니다.
- i < n인 동안 아래를 반복합니다.
- i mod 3 == 0이면: ret := ret + ret (더블)
- i mod 3 == 1이면: ret := ret을 뒤집은 문자열 (리버스)
- 그 외의 경우: ret의 모든 x와 y를 서로 교환 (스왑)
- 매 반복마다 i를 1씩 증가시킵니다.
- 반복이 종료되면 ret을 반환합니다.
구현 예제
class Solution:
def solve(self, s):
i = 0
ret = "xxy"
while i < s:
if i % 3 == 0:
ret += ret
elif i % 3 == 1:
ret = ret[::-1]
else:
new_stringy = ""
for c in ret:
if c == "x":
new_stringy += "y"
else:
new_stringy += "x"
ret = new_stringy
i += 1
return ret
ob = Solution()
print(ob.solve(5))
입력
5
출력
yyxyyxyyxyyx
성능 개선 팁
스왑 연산은 파이썬의 str.translate()를 활용하면 한 줄로 처리할 수 있어 더 깔끔하고 빠릅니다.
ret = ret.translate(str.maketrans("xy", "yx"))
또한 ret += ret처럼 문자열을 이어 붙일 때마다 새 문자열이 생성되어 비용이 큽니다. n이 커질수록 문자열 길이가 지수적으로 늘어나므로, 입력이 큰 경우에는 필요한 범위까지만 계산하거나 수열의 규칙성을 분석해 수학적으로 답을 유도하는 방식을 고려하는 것이 좋습니다.