Ohttps://www.acmicpc.net/problem/16719
16719번: ZOAC
2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로
www.acmicpc.net
문제
2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다.
앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로운 규칙을 고안해냈다!
규칙은 이러하다. 아직 보여주지 않은 문자 중 추가했을 때의 문자열이 사전 순으로 가장 앞에 오도록 하는 문자를 보여주는 것이다.
예를 들어 ZOAC를 보여주고 싶다면, A → AC → OAC → ZOAC 순으로 보여주면 된다.
바쁜 성우를 위하여 이 규칙대로 출력해주는 프로그램을 작성하시오.
입력 / 출력
예제 입력 / 출력
STARTLINK에서 L보다 R이 사전 순으로 앞에 오는데, 왜 L이 먼저 추가되는건지 이해가 가지 않았었는데, 추가되어 완성된 문자열이 사전순으로 앞에 올 수 있도록 한다고 하여 이해 완료했다.
그럼 가장 먼저 앞에 둘 문자를 고르고, 해당 문자의 오른쪽 부분을 먼저 처리하고 그 후 왼쪽 부분을 처리해야 한다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| S | T | A | R | T | L | I | N | K |
파이썬으로 리스트 슬라이싱을 통해 출력된 문자들을 찾아나가보자면,
- [ : ], n[2] = 'A' 추가
- 'A'의 오른쪽 부분인 [ 3 : ], n[6] = 'I' 추가
- 'I'의 오른쪽 부분인 [ 7 : ], n[8] = 'K' 추가
- [ 7 : 8 ], n[7] = 'N' 추가
- [ 3 : 6 ], n[5] = 'L' 추가
- [ 3 : 5 ], n[3] = 'R' 추가
- 'R'의 오른쪽 부분인 [ 4 : 5 ], n[4] = 'T' 추가
- [ 0 : 2 ], n[0] = 'S' 추가
- 'S'의 오른쪽 부부인 [ 1 : 2 ], n[1] = 'T' 추가
사전순으로 맨 앞에 올 문자를 찾으면, 해당 문자의 다음인 오른쪽 부분에서 문자를 찾아나가야 한다. 그러다가 맨 끝에 도달하게 될 경우, 방문하지 않았던 왼쪽 부분으로 돌아가야 한다.
초록색 체크 표시는, 찾은 문자의 오른쪽 부분으로 이동하지 못해 왼쪽 부분으로 넘어가야하는 부분이다.
n[8]인 'K'를 추가하고, 오른쪽 부분으로 슬라이싱을 이어가고자 한다면, [ 9 : 9 ]를 슬라이싱하게 되고, 그러면 아무런 값도 담을 수 없게 된다. 따라서 왼쪽 부분으로 이동해야 한다. ( start와 end가 동일할 경우, 왼쪽 이동 )
왼쪽 부분으로 이동하기 위해서는 기존에 이동해오면서 설정했던 start 값들을 이용해야 한다. start 값을 스택 혹은 덱에 보관한 후, 후입선출을 이용하여 왼쪽으로 슬라이싱할 수 있도록 한다.
if start == end: # start와 end가 같다면, 리스트 슬라이싱으로 아무 값도 담을 수 없다.
end = prev.pop() - 1 # 이전 end에서 1을 빼주고, 이전 start값을 가져온다. (왼쪽 부분으로 이동)
start = prev.pop()
prev.append(start)
추가할 문자의 오른쪽 부분이 남아있는 경우, start를 해당 문자의 인덱스에 1을 추가한 값으로 하여 오른쪽 부분을 슬라이싱할 수 있도록 한다. ( end는 유지한다. )
for i in range(start, end): # 정렬로 사전 순 가장 첫 문자와 동일하고, 방문한 적이 없는지 확인
if arr[0] == n[i] and visit[i] == 0:
visit[i] = 1 # 방문 표시
start = i + 1 # 시작 지점 업데이트 후 덱에 담기
prev.append(start)
break
✅[ CODE ]
from collections import deque
def print_result(): # 방문한 문자만 출력
for i in range(len(n)):
if visit[i] == 1:
print(n[i], end='')
print()
n = input()
visit = [0] * len(n) # 방문한 곳 확인
prev = deque() # 시작 지점인 start 인덱스값을 모아둔다.
prev.append(0)
start = 0
end = len(n)
while 0 in visit: # 모든 문자가 방문될 때까지 반복
arr = n[start: end]
arr = sorted(arr)
if start == end: # start와 end가 같다면, 리스트 슬라이싱으로 아무 값도 담을 수 없다.
end = prev.pop() - 1 # 이전 end에서 1을 빼주고, 이전 start값을 가져온다. (왼쪽 부분으로 이동)
start = prev.pop()
prev.append(start)
else:
for i in range(start, end): # 정렬로 사전 순 가장 첫 문자와 동일하고, 방문한 적이 없는지 확인
if arr[0] == n[i] and visit[i] == 0:
visit[i] = 1 # 방문 표시
start = i + 1 # 시작 지점 업데이트 후 덱에 담기
prev.append(start)
break
print_result()
처음에는 덱도, visit도 이용하지 않고 코드를 짰다.
.index를 이용하여 주어진 문자열에서 인덱스를 가져오는 방식을 이용해주었었는데, 동일한 값이 있을 경우 최초의 인덱스를 출력하므로 반복되는 문자를 넣게 되면 제대로 출력되지 않았었다.
따라서, 방문을 표시해주는 visit 리스트를 추가해주었고, 슬라이싱하는 방식을 위해 덱을 통해 start로 기준점을 보관하여 사용할 수 있도록 하였다.
✅[ CODE ]
n = input()
visit = [0] * len(n)
def zoac(start, end):
if start == end:
return
idx = start
arr = n[start: end]
arr = sorted(arr)
for i in range(start, end):
if arr[0] == n[i] and visit[i] == 0:
visit[i] = 1
start = i + 1
break
for i in range(len(n)):
if visit[i] == 1:
print(n[i], end='')
print()
zoac(start, end)
zoac(idx, start - 1)
zoac(0, len(n))재귀 함수를 이용하여 풀어줄 수도 있다.!