[백준/파이썬]16120번 PPAP

오랜만에 백준 문제를 풀었다.

 

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

16120번: PPAP

 

낼 수 있는 오류는 다 내고 풀었다 ㅋㅋ

정답

string = input()

stack = []

for c in string : 
    stack.append(c)
    ppap = ['P', 'P', 'A', 'P']
    if stack[-4:] == ppap :
        stack.pop()
        stack.pop()
        stack.pop()
        stack.pop()
        stack.append("P")
string = ''.join(stack)

if string == 'P' or string == "PPAP" :
    print("PPAP")
else :
    print("NP")

정답코드

 

처음에 감이 안 잡혀서 구글링 좀 했다. 이런 간단한 방법이.

 

입력받은 문자열에서 문자 하나하나 stack에 집어넣으면서 끝에서부터 4자리를 ppap리스트와 비교한다. 만약 PPAP문자열이라면 P로 바꿔준다.

 

저 과정을 거친 후, 만들어진 문자가 P이거나 PPAP이면 PPAP문자열 이므로 PPAP출력. 아니면 NP출력

 

 

오답

string_change = False
def find_ppap(string) :
    global string_change 
    for i in range(0, len(string)-3, 1) :
        if string[i:i+4] == "PPAP" :
            string_change = True
            return string[:i] + 'P' + string[i+4:]

def is_ppap(string) :
    if string == "P" :
        return "PPAP"
    global string_change
    string = find_ppap(string)
    if string_change :
        string_change = False 
        return is_ppap(string)
    else :
        return "NP"        
string = input()
print(is_ppap(string))

첫 번째 오답이다.

 

그냥 끌리는 대로 재귀 함수로 풀어 봤다.

 

알고리즘은

1. 문자열에서 처음부터 4자리씩 "PPAP"인지 비교한다. 맞다면 PPAP를 P로 바꿔준 후 return

2. 변경되었는지 여부 또한 전역 변수로 알려주는데 이는 변경 되었다면 다시 한번 재귀 함수로 위의 과정을 반복한다.

2-2. 변경되지 않았다면 이는 PPAP문자열이 아니므로 NP출력.

3. 재귀 함수를 돌다가 P만 남게된다면 이는 PPAP문자열이므로 PPAP출력.

 

그러나 개같이 런타임 에러

 

재귀함수 때문에 찾아보니

이런 말이 있길래 저거 넣고 제출하니 메모리 초과.

 

그래서 재귀 함수를 사용하지 않고 구현해봤다.

string_change = False
def find_ppap(string) :
    global string_change 
    for i in range(0, len(string)-3, 1) :
        if string[i:i+4] == "PPAP" :
            string_change = True
            return string[:i] + 'P' + string[i+4:]

      
string = input()


while True :
    string = find_ppap(string)
    if not string_change or not string:
        print("NP")
        break
    if string == "P" :
        print("PPAP")
        break

두 번째 오답.

똑같은 알고리즘에 재귀를 반복으로 돌렸다.

안될걸 알았지만 혹시나 하는 마음에 제출해봤지만 역시나 시간초과

 

---

 

재귀함수 코드도 나름 생각을 한 알고리즘이지만 공간, 시간 복잡도를 생각 못해서 틀렸다. 앞으로 생각을 하고 문제를 풀도록 하자