백준 6137 : 문자열 생성 (Python)

본문 링크

import sys
input=sys.stdin.readline
from collections import deque

A=int(input())
S=deque()
for i in range(A):
    S.append(input().rstrip())

T="" ; count=0
for i in range(A):
    start=0 ; end=len(S)-1 ; answer=0
    
    while start<=end:
        if ord(S[start])>ord(S[end]):
            answer=0
            break
        elif ord(S[start])<ord(S[end]):
            answer=1
            break
        else:
            start+=1 ; end-=1

    if answer==0:
        T+=S.pop()
    elif answer==1:
        T+=S.popleft()
    count+=1
    if count%80==0:
        T+='\n'
print(T)

📌 어떻게 문제에 접근할 것인가?

$S$ 라는 문자열이 주어졌을때 매번 왼쪽끝과 오른쪽끝 문자 중 하나를 $T$ 문자의 끝에 붙인다.
이때 $T$ 가 사전순으로 가장 빠른 문자열을 만드는 문제이다.

이떄 CDBC 라는 문자를 보자. 여기서 묻고자 하는것은 왼쪽끝과 오른쪽 끝 문자가 같을때 어떤문자를 $T$ 문자에 붙일것인가? 이다.

먼저 문자열을 하나하나 탐색하기 위해서 투 포인터를 사용하였다.
그리고 왼쪽 또는 오른쪽 문자를 바로 제거하기위해 O(1)으로 pop() , popleft() 가 가능한 큐 를 사용하였다.

📌 어떻게 이분탐색할 것인가?

먼저 start= 0 , end=len(S)-1 로 잡는다.
이때 문자를 아스키 코드 값으로 변경해서 ord(S[start]) 와 ord(S[end]) 값중 더 작은 값을 $T$ 문자열 끝에 넣으면 된다.

만약 두 문자가 똑같을때는 start+=1 , end-=1 을 동시에 해준다.
즉 두 문자가 다를때까지 계속 범위를 좁혀나가서 문자가 다른 지점에서 아스키 코드값이 더 적은 값을 $T$ 문자열 끝에 넣는다.

또 이문제에서 귀찮은 점은 문자 길이가 80글자가 넘을때마다 줄바꿈문자("\n") 을 출력해야 한다. 따라서 count 변수를 하나 만들고 T에 문자가 추가될때마다 count 를 증가시킨다.
이때 count%80==0 일때 줄바꿈 문자를 출력한다.

✅ 코드에서 주의해야할 점

• 문자열 $S$ 는 매번 길이가 줄어들기 때문에 end = len(S)-1 로 잡는다.
• 문자를 입력받을때 rstrip 를 사용해줘서 줄바꿈문자를 지워준다.
• 80 번째 문자마다 줄바꿈 문자를 추가해준다.