문제 링크
문제 요약
주어진 문자열 R이 있을 때, R의 부분 문자열이 아닌 문자열 중에서 사전순으로 가장 작은 문자열을 찾아 출력하는 문제입니다.
문제 설명에서는 최단 공통 상위 문자열(Shortest Common Superstring) 개념에 대해 길게 설명하고 있지만, 본질적으로 실제 해결해야 할 문제는 “주어진 문자열 R에 부분 문자열로 나타나지 않는 문자열 중 사전식으로 가장 작은 문자열”을 찾는 것입니다.
풀이
문제는 주어진 문자열 R에 포함되지 않는 가장 사전순으로 작은 문자열을 찾는 것입니다.
사전식 순서에 따르면, 길이가 짧을수록, 그리고 앞에 오는 문자가 작을수록 더 작은 문자열입니다.
이때 a로 이루어진 문자열을 고려하면 항상 어떤 문자열이든지간에 ‘a’로만 구성된 문자열은 동일한 길이의 다른 문자열보다 사전순으로 작다는 것을 알 수 있습니다. 따라서, 부분 문자열 중 a로 이루어진 문자열의 최대 길이를 k라 했을 때 (k + 1) 개의 a가 연속된 문자열이 답이 되게 됩니다.
정답 코드
def solve():
s = input()
a_cnt = 0
ans = 0
for i in range(len(s)):
if s[i] == 'a':
a_cnt += 1
ans = max(ans, a_cnt)
else:
a_cnt = 0
print('a' * (ans + 1))
if __name__ == "__main__":
tc = 1
for t in range(1, tc+1):
ret = solve()