[백준] 6137번: 문자열 생성 풀이

사용한 기술 스택들:  

 

6137번: 문자열 생성 (acmicpc.net)

6137번: 문자열 생성

 

코드:

import sys

input = lambda: sys.stdin.readline().rstrip()
n = int(input())
s=""
for _ in range(n):
    s+=input()
l=0
r=n-1
ans=""
while l<=r:
    if s[l]<s[r]:
        ans+=s[l]
        l+=1
    elif s[l]>s[r]:
        ans+=s[r]
        r-=1
    else:
        t_l=l+1
        t_r=r-1
        front=True
        while t_l<=t_r:
            if s[t_l]<s[t_r]:
                front=True
                break
            elif s[t_l]>s[t_r]:
                front=False
                break
            else:
                t_l+=1
                t_r-=1
        if front:
            ans+=s[l]
            l+=1
        else:
            ans+=s[r]
            r-=1
print(*[ ans[i:i+80] for i in range(0, n, 80) ],sep="\n")

 

풀이:

 

이 문제에서는 문자열 $s$로 사전적으로 제일 작은 문자열 $t$를 만들려고 한다. 이 문제를 그냥 s로 만들 수 있는 모든 조합을 찾으려고 하면 경우의 수가 $O(2^N)$이 되기 때문에 제한이 2000까지인 이 문제는 $2^{2000} = 1.148e+602$ 정도이기 때문에 절대 시간내에 돌수가 없다.

 

그렇다면 여기에서 가능한 풀이는 그리디적인 풀이라고 추측을 해볼 수 있다. PS에서는 제한을 아는 것이 참 중요한데, 왜냐하면 제한을 알면 어느정도의 시간복잡도를 예측할 수 있기 때문이다.

 

while l<=r:
    if s[l]<s[r]:
        ans+=s[l]
        l+=1
    elif s[l]>s[r]:
        ans+=s[r]
        r-=1

여기서 그리디적인 사고를 사용하자면, $s$의 앞이나 뒤에있는 문자를 $t$에 붙인다면, 사전적으로 제일 작은 문자열을 만든다면, 그냥 앞이나 뒤에서 제일 알파벳적으로 작은 것부터 꺼내오면 된다는 사실을 알게된다. 어짜피 앞에서부터 차근차근 $t$가 만들어지기 때문에 그냥 작은것들로 먼저 채워주는게 해답이라는 것을 알게 된다.

 

t_l=l+1
t_r=r-1
front=True
while t_l<=t_r:
    if s[t_l]<s[t_r]:
        front=True
        break
    elif s[t_l]>s[t_r]:
        front=False
        break
    else:
        t_l+=1
        t_r-=1
if front:
    ans+=s[l]
    l+=1
else:
    ans+=s[r]
    r-=1

 

하지만, 여기서 문제가 발생한다. $s$가 만약에 acba같은 상황이라면 어떻게 해야 하는가? 이를 위해 예외처리를 해줘야 한다. 이 예시에서의 해답은 aabc이다. 이와 같이 앞뒤가 다 같은 상황이라면 그 다음 문자를 확인해 주면 된다는 것이다. 다음 문자들에서 비교하고 그문자들 중에 앞에게 더 작으면 그쪽으로 가는게 최적이기 때문에 front를 True로 설정해주고 그 반대라면 False로 설정해준다. 하지만 다음 문자들도 같을 수가 있기 때문에 이는 반복문 처리를 해줘서 다른 점을 찾을때까지 돌리면 된다. 

 

예시: s=ACDBCB

1. s=ACDBCB t=None
   1. A가 B보다 작기 때문에 A를 붙여준다
2. s=CDBCB t=A
   1. C가 B보다 크기 때문에 B를 붙여준다
3. s=CDBC t=AB
   1. 앞뒤가 C로 같기 때문에 그 다음 문자를 확인 한다 D와 B 중에서는 B가 작기 때문에 뒤에 있는 C를 붙여준다
4. s=CDB t=ABC
   1. 여기서부터는 크기대로 붙여주는 걸 반복한다
5. t=ABCBCD

 

현재 이 코드에선 $l$이 현재 s의 앞의 문자의 위치,  $r$이 뒤의 문자의 위치로 설정이 되었다. $l$은 앞에 문자를 사용할 때마다 1씩 올려주면 되고 뒤에 문자를 사용하면 $r$을 하나씩 내려주면 될 것이다(투포인터 알고리즘). $t{\_}l$은 당연히 temporary한 변수로 그 다음 문자를 저장 할 것이고,  $t{\_}r$도 마찬가지로 작동한다. 이 알고리즘을 그대로 적용하여 코드를 구현을 하면 정답을 받게 된다.

 

이 문제의 최악의 시간 복잡도는 $O(N^2)$이다. 이 사례는 aaaaaa같이 각 문자마다 안에 있는 반복문을 하나 더 돌려주어야 하기 때문이다.

 

 

소스코드:

baekjoonProblems/볼_모으기.py at main · LimePencil/baekjoonProblems (github.com)

GitHub - LimePencil/baekjoonProblems: 백준 코딩문제 자바&파이썬 해답