반응형
https://www.acmicpc.net/problem/16120
16120번: PPAP
첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다.
www.acmicpc.net
소스코드
풀이
그리디 알고리즘 분류를 보다가 제목이 재밌어서 한번 풀어봤슴당 !
처음엔 스택을 사용할 생각을 하지 않았고, 알파벳이 나오는 순서에 따라 PPAP를 치환해주는 식의 방법으로 문제를 해결하려고 했습니다.
근데 생각보다 시간 초과가 계속 떠서 구글링을 해보니, 다들 스택으로 푸셨더라구요 !
처음 생각해봤던 방법은 계속해서 연구해볼 생각입니당 !
제가 생각하는 문제의 핵심은 PPAP가 P와 동일하다는 것입니다 !
처음엔 PPAP를 발견하면 해당 PPAP는 사라져도 되는 줄 알았습니다. 하지만 PPAP를 제거할 때 P를 남기고 제거해줘야 하는데 그 이유는 P는 PPAP문자열이기 때문입니다. (문제에서 설명)
입력 받은 문자를 스택에 추가하고, 스택의 뒤에서부터 4자리 (stack[-4:])가 ppap라면 p만 남기고 pap는 제거해줍니다 !
다음과 같은 과정을 계속 반복하여 주고, 반복이 끝났을 때 stack에 어떤 문자가 남아있는지 확인하여 결과 값을 출력해주시면 됩니다 ㅎㅎ
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준 알고리즘] 1546번: 평균 (Python) (0) | 2023.03.30 |
|---|---|
| [백준 알고리즘] 1541번: 잃어버린 괄호 (Python) (0) | 2023.03.30 |
| [백준 알고리즘] 10812번: 바구니 순서 바꾸기 (Python) (0) | 2023.03.28 |
| [백준 알고리즘] 10988번: 팰린드롬인지 확인하기 (Python) (0) | 2023.03.28 |
| [백준 알고리즘] 25206번: 너의 평점은 (Python) (0) | 2023.03.28 |