[백준] 16120 PPAP (파이썬 python)

 

 

문제 링크

 

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

16120번: PPAP

 

 

문제 풀이

 

def check(input_str):
    stack = []
    flag = False
    for str in input_str:
        # if str == 'A' and (len(stack) < 2 or stack[-2:] != ['P', 'P']):
        #     return flag
        stack.append(str)
        if len(stack) >= 4 and stack[-4:] == ['P', 'P', 'A', 'P']:
            for _ in range(3):
                stack.pop()
    if len(stack) == 1 and stack[0] == 'P':
        flag = True
    return flag

input_str = list(input())
if check(input_str):
    print('PPAP')
else:
    print('NP')

 

 

시간 제한은 1초인데, 입력 문자열의 크기가 최대 100만까지로 커서

시간 초과에 중점을 두고 풀어야 하는 문제였습니다.

입력받은 전체 문자열을 체크하는 과정에서

처음에는 평소 deque를 사용할 때처럼 습관적으로 pop(0)을 해서

입력받은 string이 존재하지 않을 때까지 while문을 돌렸는데,

생각해보니 pop(0)은 시간복잡도 O(n)으로 pop(0)만 하더라도 시간이 터지는 문제가 있었습니다.

주의해서 기존 문자열은 건드리지 않고, 하나씩 체크만 하는 방법으로 변경했습니다.

 

이를 인지하고 나니, 해결 방법은 간단해졌습니다.

stack에 입력받은 문자열을 앞에서부터 하나씩 추가해주고

stack의 길이가 4 이상일 경우 최근 추가된 4개가 'PPAP'인지를 확인한 후 맞으면 뒤 3개를 지워 'P'로 대치시켜줍니다.

이런식으로 반복할 경우 만약 입력 문자열이 PPAP 문자열일 경우

결국 'P'만 남게 됩니다.

마지막에 stack에 남은 문자열이 'P'인지 확인하고 그에 따라 출력해주면 됩니다.