0. 문제 링크
https://www.acmicpc.net/problem/21925
1. 풀이 방법
- 스택이 비어있다면, 매 숫자마다 스택에 넣는다. 그리고 다음 숫자로 이동한다.
- 만약에 스택에 숫자가 들어가 있다면, 스택의 길이를 측정한다 -> l
- 현재 숫자의 위치인 cur과 스택의 마지막 숫자를 비교하며 좌우로 넓혀가며 팰린드롬을 만족하는지 확인한다.
- 이때 스택의 길이가 남은 숫자의 길이보다 길다면 이 또한 팰린드롬을 만들 수 없다.
- 만약 스택에 들어있는 숫자 3개와 현재 숫자의 위치인 cur에서 cur + 2까지의 3개의 숫자가 팰린드롬을 만족한다면, 스택을 모두 비운다. 그리고 True와 cur + l을 반환한다.
- 만약 아니라면 False를 반환한다.
- 현재 숫자의 위치인 cur과 스택의 마지막 숫자를 비교하며 좌우로 넓혀가며 팰린드롬을 만족하는지 확인한다.
- 최종적으로 스택에 숫자가 남아있다면 -1을 반환, 남아있지 않다면 정답을 출력하면 된다.
2. 코드
import sys
input = sys.stdin.readline
def check(cur):
l = len(stack)
for i in range(l):
if cur + i >= n:
print(-1)
exit(0)
if stack[-i - 1] != maps[cur + i]:
return False, 0
stack.clear()
return True, cur + l
if __name__ == "__main__":
n = int(input())
maps = list(map(int, input().split()))
stack = []
ans = 0
i = 0
while i < n:
if len(stack) == 0:
stack.append(maps[i])
i += 1
else:
flag, next = check(i)
if flag:
ans += 1
i = next
else:
stack.append(maps[i])
i += 1
if len(stack) > 0:
print(-1)
else:
print(ans)
3. 마무리
'Computer Science > 알고리즘' 카테고리의 다른 글
[백준 - Python] 1577 - 도로의 개수 (0) | 2023.07.19 |
---|---|
[백준 - Python] 2110 - 공유기 설치 (0) | 2023.07.19 |
[백준 - Python] 1484 - 다이어트 (1) | 2023.05.19 |
[백준 - Python] 2015 - 수들의 합 4 (1) | 2023.05.19 |
[백준 - Python] 2665 - 미로만들기 (0) | 2023.05.19 |