문제
오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.
이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.
두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.
줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.
풀이
기존의 스택 풀이와 크게 다르지 않다고 생각해서 스택에 저장된 top값 보다 큰 값이 있다면 answer에 1을 더해주고 stack에 남은 값이 있다면 answer에 1을 더해주는 방식으로 풀려고 시도를 했다.
그러나 문제에서 A, B보다 큰 사람이 없어야 한다는 조건을 보면 키가 같은 사람에 대한 풀이도 추가해주어야 한다.
이 부분에서 시간을 많이 잡아먹으면서 살짝 힌트를 보고 왔더니 중복횟수를 센 다음 그 횟수만큼 정답 값에 더해주면 된다고 한다.
그래서 stack에 초기값으로 (height, 1)값을 넣어주고 (한 번 반복된 거니까) 스택의 top값을 계속 비교해가면서 top값보다 현재 인덱스의 height값이 크다면 중복값을 저장해둔 top의 1번째 인덱스 값을 더해준다.
만약 같다면 정답값에 중복값을 더해주고 추가로 스택에 추가될 중복횟수를 증가시켜주어야 한다.
코드
import sys
input = sys.stdin.readline
N = int(input().rstrip())
CNT = 1
HEIGHT = 0
stack = []
answer = 0
for idx in range(N):
height = int(input().rstrip())
cnt = 1
while stack and stack[-1][HEIGHT] <= height:
top = stack.pop()
answer += top[CNT]
if (top[HEIGHT] == height):
cnt += top[CNT]
if stack: answer +=1
stack.append((height, cnt))
print(answer)피드백
사고를 좀 더 유연하게 할 필요가 있다. 생각해보면 중복값의 갯수를 카운팅해서 정답에 더하는 건 꽤나 쉽게 떠올릴 수 있는 건데 숙고하기 전에 코드부터 치는 습관을 좀 더 버리고 수도코드에 집중하자.
목표로 했던 문제를 한 번에 풀어내지 못해서 아쉽다. 새로운 문제를 다시 목표로 삼고 풀어낸 다음에 다음 알고리즘으로 넘어가야겠다.
