두 개의 문자열 s와 t, 그리고 양의 정수 n이 주어졌을 때, 아래 규칙을 따르는 수열 A의 n번째 항을 구하는 문제입니다.
- A[0] = s
- A[1] = t
- n이 짝수일 때: A[n] = A[n-1] + A[n-2]
- n이 홀수일 때: A[n] = A[n-2] + A[n-1]
예를 들어 s = "a", t = "b"라고 하면, 수열 A는 다음과 같이 만들어집니다.
["a", "b", "ba" ("a" + "b"), "bba" ("b" + "ba"), "bbaba" ("bba" + "ba")]
따라서 입력이 s = "pk", t = "r", n = 4라면 결과는 "rrpkrpk"가 됩니다.
문제 해결 접근 방법
이 문제는 반복문으로 차례대로 다음 항을 생성하되, 앞의 두 항만 변수에 저장해 두면 효율적으로 해결할 수 있습니다.
- n이 0이면 s를 그대로 반환합니다.
- n이 1이면 t를 그대로 반환합니다.
- a = s, b = t로 초기화합니다.
- i를 2부터 n까지 반복하며 다음을 수행합니다.
- i가 짝수이면 c = b + a (연결 순서를 뒤집음)
- i가 홀수이면 c = a + b (원래 순서대로 연결)
- a = b, b = c로 값을 갱신합니다.
- 반복이 끝나면 c를 반환합니다.
예제 코드
class Solution:
def solve(self, s, t, n):
if n == 0:
return s
elif n == 1:
return t
a = s
b = t
for i in range(2, n+1):
if i % 2 == 0:
c = b + a
else:
c = a + b
a = b
b = c
return c
ob = Solution()
print(ob.solve("pk", "r", 4))
입력
"pk", "r", 4
출력
rrpkrpk
동작 원리 살펴보기
입력 s = "pk", t = "r", n = 4인 경우를 단계별로 확인해 보겠습니다.
- A[0] = "pk"
- A[1] = "r"
- A[2] = A[1] + A[0] = "r" + "pk" = "rpk" (짝수 인덱스)
- A[3] = A[1] + A[2] = "r" + "rpk" = "rrpk" (홀수 인덱스)
- A[4] = A[3] + A[2] = "rrpk" + "rpk" = "rrpkrpk" (짝수 인덱스)
매 단계에서 필요한 정보는 바로 앞의 두 항뿐이므로, 전체 수열을 저장하지 않고도 두 개의 변수만 유지하면 됩니다. 덕분에 시간 복잡도 O(n), 공간 복잡도 O(1)(결과 문자열 제외)로 문제를 해결할 수 있습니다.