1. 문제
오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.
이 역사적인 순간을 맞이하기 위해 줄에서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해졌다.
두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.
줄에 서 있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)
둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.
사람들이 서 있는 순서대로 입력이 주어진다.
출력
서로 볼 수 있는 쌍의 수를 출력한다.
2. 정답 코드
# @Date : 2024-09-13 10:14:51
# @Author : ecodev
# @Link : http://ecodev-blog.vercel.app
import sys
input = sys.stdin.readline
############ ---- Input Functions ---- ############
def inp():
return(int(input()))
def inlt():
return(list(map(int, input().split())))
def insr():
s = input()
return(list(s[:len(s) - 1]))
def invr():
return(map(int, input().split()))
n = inp()
ls = [inp() for _ in range(n)]
stack = []
ans = 0
for i in range(n):
cnt = 1
while stack and stack[-1][0] <= ls[i]:
ans += stack[-1][1]
if stack[-1][0] == ls[i]:
cnt = stack[-1][1] + 1
else:
cnt = 1
stack.pop()
if stack:
ans += 1
stack.append((ls[i], cnt))
print(ans)
3. 생각한 방향 및 설명
될 듯 안 될 듯 해서 계속 디버깅을 거듭했던 문제이다. 플래티넘 문제여서 그런지 아직은 쉽지 않은 것 같다.
우선 예전에 풀었던
탑https://www.acmicpc.net/problem/2493 문제가 연상되었다. 또한 N이 50만이기 때문에 완전탐색으로는 힘들듯 해서 스택을 이용하기로 생각을 했었다. 이 문제에서는 하나 더 생각을 해야 하는 것이 중간중간 몇 쌍이 생성되었는지를 dp문제 푸는 것 처럼 메모이제이션을 해야된다는 점이었다.
그래야 시간제한 안에 처리할 수 있기 때문이다. 그래서 stack안에 (키, 이 키로 만들 수 있는 쌍의 개수) 이런식으로 넣어주었다.
스택의 가장 윗 부분에는 순서를 돌면서 가장 큰 키를 가진 사람이 있을 것이다.
1. while문 밖에서
가장 큰 키를 가진 사람을 만나서 while문을 들어가지 못했다는 의미는 곧 자신과 그 가장 큰 사람 서로밖에 볼 수 없다는 뜻이므로 cnt = 1이 되겠다. 그래서 처음에 cnt를 1로 초기화시켰다.
2. while문 안에서
만약 이제 비교할 사람과 가장 큰 사람의 키가 동일하다면 가장 큰 사람이 볼 수 있는 사람의 순서쌍 + 1(이제 비교할 사람과 가장 큰 사람이 붙는 1가지 경우)이 되겠다.
만약 이제 비교할 사람이 가장 큰 사람보다 더 크다는 의미는 그 가장 큰 사람이 만들 수 있었던 순서쌍은 이제는 의미가 없어진다는 것(
의미가 없어진 순서쌍 = 이제 비교할 사람보다 작고, 현재 가장 큰 사람보다도 작은 사람들이기 때문에 이제 비교할 사람이 그 작은 사람들을 볼 수 없다.)이고 그러므로 이제 비교할 사람과 가장 큰 사람이 붙는 1가지 경우밖에 존재할 없다. 우선은 이렇다. 이것이 최적의 해는 아니다. 왜냐하면 4 2 3 라고 가정했을 때 3이 들어왔을 때 2랑 비교해서 cnt = 1이 되지만 이론적으로는 4까지 비교해서 4와도 순서쌍을 맺을 수 있기 때문이다.이것을 어떻게 처리했느냐? 바로
if stack:
ans += 1이 코드가 이 문제풀이의 핵심이 되겠다.
4 2 3의 경우 3이 들어왔을 때 stack은 [4]가 있을 것이고, 아직도 이 스택안에 무엇인가 있다는 의미는 그 사람과도 서로 볼 수 있다는 의미가 된다. 따라서 +1만 해주면 될 것이다.