문제 개요
문자열 S가 주어졌을 때, 이 문자열에서 사전 순(lexicographically)으로 가장 큰 회문(palindrome) 부분 수열을 찾는 문제입니다.
예를 들어, 입력이 "tutorialspointtutorial"이라면 출력은 "uu"가 됩니다.
핵심 아이디어
이 문제의 핵심은 매우 간단합니다. 단일 문자 자체도 회문에 해당하므로, 문자열에서 가장 큰 문자를 모두 이어 붙인 것이 곧 사전 순으로 가장 큰 회문 부분 수열이 됩니다. 다른 어떤 부분 수열도 최대 문자보다 사전 순으로 앞선 첫 글자를 가질 수 없기 때문입니다.
해결 절차는 다음과 같습니다:
- 정답을 저장할 변수 ans를 빈 문자열로 초기화합니다.
- max_val을 문자열의 첫 번째 문자로 설정한 뒤, 나머지 문자를 순회하며 최댓값을 갱신합니다. 즉, 문자열 내에서 가장 큰 문자를 찾습니다.
- 문자열을 다시 한 번 순회하면서, 현재 문자가 max_val과 같으면 ans에 해당 문자를 추가합니다.
- ans를 반환합니다.
구현 예시
아래 파이썬 코드를 통해 동작 과정을 더 잘 이해할 수 있습니다.
def largest_palindromic_substr(s):
ans = ""
max_val = s[0]
for i in range(1, len(s)):
max_val = max(max_val, s[i])
for i in range(0, len(s)):
if s[i] == max_val:
ans += s[i]
return ans
s = "tutorialspointtutorial"
print(largest_palindromic_substr(s))
입력
"tutorialspointtutorial"
출력
uu
동작 원리와 성능 분석
입력 문자열 "tutorialspointtutorial"에는 'u'가 두 번 등장하며, 이 문자열에서 'u'가 가장 큰 문자입니다. 따라서 'u'를 모두 모은 "uu"가 사전 순으로 가장 큰 회문 부분 수열이 됩니다.
이 알고리즘은 문자열을 두 번 선형 순회하면 되므로 시간 복잡도는 O(n)이며, 결과 저장을 위한 공간 복잡도 역시 O(n)으로 매우 효율적입니다. 정렬이나 동적 계획법 없이도 간단한 최댓값 탐색만으로 문제를 해결할 수 있다는 점이 이 접근법의 장점입니다.