[Python] 백준 15881번_Pen Pineapple Apple Pen

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

15881번: Pen Pineapple Apple Pen

 

• 여러 개의 사과, 파인애플, 그리고 펜이 일렬로 세워져 있음
• 이 물건들의 순서를 바꾸지 않고 옆에 있는 물건끼리 연결했을 때, 펜-파인애플-애플-펜을 몇 개나 만들 수 있을지 세어보기
• 단, 펜, 파인애플, 사과, 펜 순서로 연결된 네 개의 물건만을 펜-파인애플-애플-펜으로 인정하며, 하나의 펜이 두 개의 펜-파인애플-애플-펜에 포함될 수 없음
• 또한 펜, 사과, 파인애플, 펜 순서로 연결된 네 개의 물건은 펜-파인애플-애플-펜이 아님

• 입력
  • 첫 번째 줄에 물건의 총 개수 n이 주어짐 (1 ≤ n ≤ 1,000,000)
  • 두 번째 줄에 물체의 목록이 길이 n의 문자열로 주어짐
  • 사과는 A로, 파인애플은 P로, 펜은 p로 대소문자를 구분하여 표기
• 출력
  • 만들 수 있는 펜-파인애플-애플-펜의 최대 개수를 출력
• 시간 제한: 1초
• 메모리 제한: 32 MB

 

"""
입출력 예시)

(예제 입력 1) 
15
ApPApPpAPpApPAp
                -> 2

(예제 입력 2)
7
pPApPAp
        -> 1
"""

 

 

## 의사코드 ##

# 물건의 순서 바꿀 수 없음

# 펜-파인애플-애플-펜 -> pPAp

# 하나의 펜이 두 개의 펜-파인애플-애플-펜에 포함될 수 x
# i+3 인 값을 0으로 바꾸기

 

 

 

통과한 코드

 

n = int(input())
s = list(input())
s.extend([0] * 1000000)
 
i, cnt = 0, 0
 
while(i < n):
    if(s[i] == 'p' and s[i+1] == 'P' and s[i+2] == 'A' and s[i+3] == 'p'):
        s[i+3] = 0
        cnt += 1
    i += 1
 
print(cnt)

 

 

• 하나의 펜이 두 개의 '펜-파인애플-애플-펜'에 포함될 수 없음
  • -> '펜-파인애플-애플-펜'에 포함된 마지막 펜의 값을 0으로 바꿈
• 리스트를 n의 최대 개수만큼 extend 하지 않으면 index error 발생

 

 

• 과정 확인

n = 15
s = ['A', 'p', 'P', 'A', 'p', 'P', 'p', 'A', 'P', 'p', 'A', 'p', 'P', 'A', 'p'] 

"""
s: ['A', 'p', 'P', 'A', 'p', 'P', 'p', 'A', 'P', 'p', 'A', 'p', 'P', 'A', 'p'] 

i: 0
i+1 = 1
--------------------------------------------------------------------------------
i: 1
변경 전 s[i+3]: p 

<pPAp>
변경된 s[i+3]: 0
변경된 s: ['A', 'p', 'P', 'A', 0, 'P', 'p', 'A', 'P', 'p', 'A', 'p', 'P', 'A', 'p'] 

cnt: 1 

i+1 = 2
--------------------------------------------------------------------------------
i: 2
i+1 = 3
--------------------------------------------------------------------------------
i: 3
i+1 = 4
--------------------------------------------------------------------------------
i: 4
i+1 = 5
--------------------------------------------------------------------------------
i: 5
i+1 = 6
--------------------------------------------------------------------------------
i: 6
i+1 = 7
--------------------------------------------------------------------------------
i: 7
i+1 = 8
--------------------------------------------------------------------------------
i: 8
i+1 = 9
--------------------------------------------------------------------------------
i: 9
i+1 = 10
--------------------------------------------------------------------------------
i: 10
i+1 = 11
--------------------------------------------------------------------------------
i: 11
변경 전 s[i+3]: p 

<pPAp>
변경된 s[i+3]: 0
변경된 s: ['A', 'p', 'P', 'A', 0, 'P', 'p', 'A', 'P', 'p', 'A', 'p', 'P', 'A', 0] 

cnt: 2 

i+1 = 12
--------------------------------------------------------------------------------
i: 12
i+1 = 13
--------------------------------------------------------------------------------
i: 13
i+1 = 14
--------------------------------------------------------------------------------
i: 14
i+1 = 15
--------------------------------------------------------------------------------

2
"""

 

n = 7
s: ['p', 'P', 'A', 'p', 'P', 'A', 'p'] 

"""
s: ['p', 'P', 'A', 'p', 'P', 'A', 'p'] 

i: 0
변경 전 s[i+3]: p 

<pPAp>
변경된 s[i+3]: 0
변경된 s: ['p', 'P', 'A', 0, 'P', 'A', 'p'] 

cnt: 1 

i+1 = 1
--------------------------------------------------------------------------------
i: 1
i+1 = 2
--------------------------------------------------------------------------------
i: 2
i+1 = 3
--------------------------------------------------------------------------------
i: 3
i+1 = 4
--------------------------------------------------------------------------------
i: 4
i+1 = 5
--------------------------------------------------------------------------------
i: 5
i+1 = 6
--------------------------------------------------------------------------------
i: 6
i+1 = 7
--------------------------------------------------------------------------------

1
"""

 

 

 

 

 

참고)

 

https://bgeun2.tistory.com/12

그리디: 백준 15881 파이썬