[골드 IV] 16120번. PPAP

 문제 

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

16120번: PPAP

 사용 언어 

Python3

 풀이 과정 

처음에는 막 항상 끝이 PAP로 끝나야 하니까 그런 조건들을 생각하다가...

절대 모든 조건을 고려할수도 없고 그렇게 푸는 문제가 아닌 것 같아서 더 생각해봤다.

 

그런데 문제 조건에서 다음과 같이 명시했으므로

1. P는 PPAP 문자열
2. PPAP 문자열에서 P 하나를 PPAP로 바꾼 문자열은 PPAP 문자열

반대로 PPAP를 다시 P로 바꿔도 PPAP 문자열이 된다는 사실을 깨달아야 했다.

 

저 로직을 깨닫고 나면 코드를 짜는건 어렵지 않지만, PPAP를 비교할 때 슬라이싱을 하는 방법과 join을 하는 방법, 그리고 인덱스로 접근하는 방법 세 가지가 있었고 나는 그 중 그래도 시간이 제일 짧을 것 같은 인덱스 접근 방식을 선택했다.

문제는 PPAP를 만났을 때 pop을 세 번 해야 P만 남는다는 것이었는데 아래와 같이 처음에 짠 코드가 마음에 들지 않았다.

# PPAP를 다시 P로 치환하기 위해 PAP를 pop
if stack[-4] == "P" and stack[-3] == "P" and stack[-2] == "A" and stack[-1] == "P":
    stack.pop()
    stack.pop()
    stack.pop()

그래서 구글링을 통해 아래 제출 답안과 같이 한 줄로 바꾸었더니 미세하게 시간이 줄어들었다.항상 기분 좋은 맞았습니다!!

조건을 나누면 좀 더 시간이 빠를 것 같았지만 코드가 지저분해질 것 같아 이번에는 그냥 깔끔함을 택하기로 했다.

 제출 답안 

from sys import stdin

# p는 PPAP 문자열
# PPAP 문자열에서 p 하나를 PPAP로 바꾼 문자열은 PPAP 문자열
string = stdin.readline().strip()
stack = []
for i in string:
    if len(stack) >= 4:
        # PPAP를 다시 P로 치환하기 위해 PAP를 pop
        if stack[-4] == "P" and stack[-3] == "P" and stack[-2] == "A" and stack[-1] == "P":
            del stack[-3:]

    stack.append(i)

result = "".join(stack)
if result == "P" or result == "PPAP":
    print("PPAP")
else:
    print("NP")

 공부한 내용 

del

파이썬에서 리스트 요소를 제거하는 방법은 크게 4가지가 있다.

• pop(x) : x번째 인덱스의 요소 하나를 삭제하면서 추출, 괄호 안이 비어있으면 맨 마지막 값을 삭제하면서 추출
• del x : pop과 비슷한 기능으로 x값을 삭제, x로는 list[i]와 같이 요소가 들어갈수도 있고 list[1:3]과 같이 슬라이싱이 들어갈수도 있음
• remove(x) : 리스트에서 맨 처음 x값을 삭제
• clear(x) : 리스트 x의 모든 요소를 삭제

 

위에서 나는 pop을 세 번 사용하는 것이 싫어서 슬라이싱을 한 번 하더라도 del로 바꿔서 제출해봤는데,3번 pop하는 걸 기준으로 del이 살짝 더 빨랐다.

 

다만 del은 사용방법이 일반적인 메소드랑은 다르고 if문 for문처럼  del x[i] 와 같은 식으로 사용한다는 점을 기억해야 한다.

 

출처: https://jinisbonusbook.tistory.com/34

for i in list / for x in list / while문 속도 차이

파이썬에서 반복문으로 배열의 요소에 접근할 때 보통 3가지 방법을 사용한다.

 

①  for i in range(len(arr)) 을 써서 인덱스로 접근하는 방법

②  for x in arr 을 써서 요소를 하나씩 받아오는 방법

③  while 을 써서 인덱스로 접근하는 방법

 

출처에 있는 블로그 포스팅 작성자분께서 심심해서 이 세 가지 방법의 속도를 테스트해보셨다고 하는데,그 결과 ③ << ① < ②의 순서대로 빨랐다고 한다.while문은 같은 로직이라도 for문보다 현저히 느렸고, 인덱스로 요소에 한 번 더 접근하는 방법보다는 요소에 한 번에 접근하는 ②번 방식이 가장 빠른 것 같다.

 

결론은 코딩테스트에서는 요소 직접 접근 방식을 애용하자는 것!

 

출처: https://blog.naver.com/PostView.naver?blogId=tai15515&logNo=222468640173&parentCategoryNo=&categoryNo=8&viewDate=&isShowPopularPosts=true&from=search 

[Python] 반복문 실행 속도 비교