[파이썬]baekjoon 6137: 문자열 생성

https://www.acmicpc.net/problem/6137

6137번: 문자열 생성

---

투 포인터 문제

 

투 포인터를 이용하지 않으면 시간 상 풀릴 수 가 없다

 

초기에 재귀와 리스트의 pop을 섞어서 풀었는데 시간초과가 나옴..

 

정답은 투포인터로 이용해서 st 지점과 ed 지점을 옮기며 계산을 하면 된다

n = int(input())
s = []
for i in range(n):
    s.append(input())
result = ''

st, ed = 0, n-1
while st <= ed:
    if s[st] < s[ed]:
        result += s[st]
        st +=1
    elif s[st] > s[ed]:
        result += s[ed]
        ed -=1
    # 투 포인터 에 투포인터
    else:
        ST, ED = st, ed
        tf = False
        while ST <= ED:
            if s[ST] < s[ED]:
                result +=s[st]
                st +=1
                tf = True
                break
            elif s[ST] > s[ED]:
                result += s[ed]
                ed -=1
                tf = True
                break
            else:
                ST +=1
                ED -=1
        if not tf:
            result += s[st]
            st +=1
    if len(result) >=80:
        print(result)
        result = ''
print(result)