위 문제는 주어진 입력을 받았을 때 PPAP 문자열인지 아닌지 구분하는 문제입니다.
처음에 이 문제를 봤을때 if문을 여러개 해서 케이스에 맞게 구현을 시도했었는데 고려해야할 사항들도 많고 입력 값이 길어질 때의 케이스를 구현하기가 어려워서 최대한 스택을 활용해서 풀어보기로 했습니다.
먼저 예를 들어 PPPAPAP를 하나씩 나눠서 입력받는다고 가정하고 하나씩 stack에 입력합니다. stack에 입력하다가 stack을 뒤에서부터 4개를 잘랐을때 그 문자열이 PPAP일경우 PPAP를 pop해주고 p를 append해줍니다.
처음에는 stack을 앞에서부터 자를려고 시도했었다가 성립이 안되는 몇가지 반례를 발견하고 뒤에서부터 자르는걸로 방법을 바꿨습니다.
from sys import stdin as s
s = open('input.txt','rt')
arr = list(s.readline().rstrip())
stack = []
for i in range(len(arr)):
stack.append(arr[i])
if stack[-4:] == ['P','P','A','P']:
for j in range(4):
stack.pop()
stack.append('P')
if stack==['P'] or stack ==['P','P','A','P']:
print('PPAP')
else:
print('NP')
위의 코드가 전체코드입니다.
stack[-4:] 이 부분이 stack을 뒤에서부터 4개를 자른다는 뜻이고 만약 그 4개의 값이 PPAP일경우 반복문을 통해 pop을 해주는 과정을 나타냈습니다.
이 코드를 제출했을 때 계속 3%에서 틀렸다고 나와서 반례를 계속 찾았지만,,, 결국 틀린곳은 처음에 arr를 입력받을때 rstrip()을 안써줬었는데 rstrip()을 추가해주니 바로 맞았다고 바꼈습니다.. 덕분에 앞으로 list로 입력받을 때에는 rstrip()쓰는 것을 까먹지 않을 것 같네요 ㅎ
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 1916 최소비용 구하기 [Python] (0) | 2023.04.25 |
---|---|
[백준] 2573 빙산 [Python] (0) | 2023.04.25 |
[백준] 3190 뱀 [Python] (0) | 2023.04.18 |
[백준]13334 철로 [Python] (0) | 2023.04.18 |
[백준]8983 사냥꾼 [Python] (0) | 2023.04.17 |