[Python][백준 6137][투 포인터] 문자열 생성 - 컴도리돌이

반응형

6137번: 문자열 생성

---

풀이 과정

아이디어가 떠오르지 않은,,,,, 너무나 어려운 문제였다.😂

 

1. 먼저 주어진 s 값을 받아 준다. (필자는 배열로 받아서 join 함수를 사용하였다.)

 

2. t 값을 빈 문자열 값으로 초기화 해준다.

 

3. 해당 문제는 투 포인터로 풀었기에 i,j 각각 0, n-1 설정하여 탐색한다.

 

4 투포인터 알고리즘

• 4-1) 왼쪽 인덱스와 오른쪽 인덱스의 s 값을 비교해서 왼쪽이 사전 순으로 빠르면 t에 왼쪽 인덱스 값을 더해주고, 왼쪽 인덱스를 +1 시켜준다. 오른쪽이 빠르면 동일하게 작업해준다.( 오른쪽 인덱스 -1)
• 4-2) 두 인덱스의 값들이 사전 순이 동일할 경우 새로운 ii,jj 라는 투포인터 알고리즘을 사용해준다.
• 4-3) 새로운 반복문에서 ii는 왼쪽 인덱스(현재 탐색하여 i번째까지 온 왼쪽 인덱스), jj는 오른쪽 인덱스(현재 탐색하여 j번째까지 온 오른쪽 인덱스)로 설정해주고, 동일하게 4-1 처럼 진행해주고 사전 순으로 빠른 인덱스를 찾으면 두번째 반복문은 break 해준다. 하지만 사전순으로 같을 경우 ii,jj를 각각 +1,-1시켜준다.
• 두번째 반복문에서 탐색하였는데 사전순으로 빠른 것을 못찾았으면 왼쪽 인덱스의 값을 t에 더해주고, 왼쪽 인덱스 값을 +1 (i+=1)시켜준다. (이 부분때문에 한참 해맸다. 🤦‍♂️)
• 4-4)  80글자마다 새 줄로 출력해줘야 한다!! cnt라는 변수를 만들어 카운팅 해주었다. 

---

풀이 코드

import sys; n = int(sys.stdin.readline())
s,t,i,j,cnt= ''.join([sys.stdin.readline().strip() for _ in range(n)]),'', 0,n-1,0
while i <= j :
  if s[i] < s[j] : t += s[i] ; i+= 1
  elif s[i] > s[j] : t += s[j] ; j -= 1
  else :
    ii,jj = i,j
    while ii <= jj :
      if s[ii] < s[jj] : t += s[i]; i += 1; break
      elif s[ii] > s[jj] : t += s[j]; j -= 1 ; break
      else : ii += 1 ; jj -= 1
    else : t += s[i] ; i += 1
  cnt += 1
  if cnt % 80 == 0 :
    t += '\n'
print(t)