[백준] 6137번 문자열 생성

💡문제접근

• 문자열의 양끝에서 적합한 연산을 통해서 사전순으로 가장 앞선 문자열을 출력하는 문제였다.
• 양끝에서 적합한 연산을 수행하기 위해서는 투 포인터로 문제를 접근해야했다.

---

• 만약 왼쪽 포인터가 가리키는 문자가 오른쪽 포인터가 가리키는 문자보다 사전 순으로 앞선다면? → 왼쪽 문자를 추가

• 만약 오른쪽 포인터가 가리키는 문자가 왼쪽 포인터가 가리키는 문자보다 사전 순으로 앞선다면? → 오른쪽 문자를 추가

  • 여기서 문제가 있다. 만약 왼쪽 포인터가 가리키는 문자와 오른쪽 포인터가 가리키는 문자가 동일하다면 어떤 것을 추가해야할지 파악하기 힘들다. 그래서 별도의 투 포인터를 더 만들어 인덱스의 증감을 처리하여 동일한 문자의 이후 문자로 사전 순 정렬을 완성하면 해결이 된다.

• 테스트케이스가 부족하여 직접 테스트케이스를 만들었다. 이 테스트케이스가 시간을 줄일 수 있었던 가장 큰 공을 했다.

💡Input :

7
A
C
D
F
D
C
B

💡Output :

ABCCDDF

💡코드

import sys
input = sys.stdin.readline

res = ""
N = int(input())
for _ in range(N):
    Str = input().strip()
    res += Str

ans = ""
left = 0
right = len(res) - 1
while left < right:
    if res[left] < res[right]:
        ans += res[left]
        left += 1
    elif res[left] > res[right]:
        ans += res[right]
        right -= 1
    # 이 문제의 핵심 : 사전순으로 앞선 출력(새로운 포인터를 만들어줌)
    else:
        left_next, right_next = left, right
        flag = True
        while left_next < right_next:
            if res[left_next] < res[right_next]:
                ans += res[left]
                left += 1
                flag = False
                break
            elif res[left_next] > res[right_next]:
                ans += res[right]
                right -= 1
                flag = False
                break
            else:
                left_next += 1
                right_next -= 1
        if flag:
            ans += res[right]
            right -= 1
ans += res[left]

result = list(ans)
for i in range(1, len(result)+1):
    print(result[i-1], end = "")
    if i % 80 == 0:
        print()

💡소요시간 : 1h 24m