1464. [Python]뒤집기 3

1. 문제

 

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

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 덱

 

3. 파이썬 코드

 

from collections import deque
# 단어 길이 체크
word = input()
word_length = len(word)
# 뒤집을 리스트 생성
stack = deque([word[0]])
# 단어 끝까지 탐색하며
for i in range(1,word_length):
    # 단어가 이전의 단어보다 큰 경우 그대로 추가
    if word[i] >= stack[-1]:
        stack.append(word[i])
    # 외의 경우 처음 단어랑 비교해서 작으면 그 앞에 추가 아닌경우 맨뒤에 추가
    else:
        if word[i] <= stack[0]:
            stack.appendleft(word[i])
        else:
            stack.append(word[i])
# join을 통한 정답출력
print("".join(stack))

 

4. 문제를 풀고난 후 생각

 

• 문제를 읽고 문자를 마음대로 정렬하여 사전순 앞인 것을 찾아내는 문제로 인식하여 처음에는 단순히 sort 처리만 하여 정답을 제출하였는데 바로 틀리는 것을 확인하고 다시 살펴 보았다.
• 문자를 지나가며 값이 작은지 큰지를 판단하여 작으면 문자를 뒤집이서 확인해 보고 아닌 경우 맨 뒤에 추가를 해주는 접근방법으로 처리하였다.
• 문자를 중간에 끼울 수 없는 이유는 앞의 문자를 통채로 뒤집어야 하기 때문에 각 양끝의 값들만 비교해주면 쉽게 풀 수 있는 문제였다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 덱