(Python/플5)백준알고리즘 3015번: 오아시스 재결합

문제 바로가기 

오아이스 재결합

 

문제:

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다. 이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다. 두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다. 줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람들이 서 있는 순서대로 입력이 주어진다.

출력:

서로 볼 수 있는 쌍의 수를 출력한다.

 

 

풀이

일단 틀린 내 처음 접근 방법은 이렇다.

 

import sys
from collections import deque

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N = int(input())
lst = deque([int(sys.stdin.readline()) for i in range(N)])

count = 0
stk = deque()
left = 0
right = 0
while left < N and right < N:
    if len(stk) <= 1: # 길이가 2 미만 이면
        stk.append(lst[right])
        right += 1
    else:
        if stk[-1] <= lst[left] and stk[-1] <= lst[right] : # 길이가 2 이상 이면서, 사잇 값 이면 추가됨
            stk.append(lst[right])
            right += 1
            count += 1
        else: # 사잇값이 아님
            stk.popleft()
            left += 1

print(count + N-1 )

 

마주보고 있는 갯수는 N-1 이다. 무조건 가능하고

나머지가 문제인데 투포인터를 사용하여 stk에 쌓아 주는 방식으로 했다. 

하지만 문제에서 

deque([4, 1, 2, 2, 5])
deque([1, 2, 2, 5])
deque([2, 2, 5])

에서 225 가 되는순간 count += 1이 되어야 하는데 안된다.

 

코드2. 이것도 투포인터를 사용한 방법인데 시간초과가 난다.

N = int(input())
heights = [int(input()) for _ in range(N)]

left = 0
right = 0
count = 0
stk = []

while right < N:
    while stk and stk[-1][0] < heights[right]:
        stk.pop()
        count += 1
    stk.append((heights[right], right))
    count += len(stk) - 1
    right += 1

print(count)

 

 

https://lotuslee.tistory.com/105

[백준 3015번] 오아시스 재결합 (java)

https://nahwasa.com/entry/%EB%B0%B1%EC%A4%80-3015-%EC%9E%90%EB%B0%94-%EC%98%A4%EC%95%84%EC%8B%9C%EC%8A%A4-%EC%9E%AC%EA%B2%B0%ED%95%A9-BOJ-3015-JAVA

백준 3015 자바 - 오아시스 재결합 (BOJ 3015 JAVA)

이분들의 블로그를 참고하여 이해하고 작성하였다.

 

import sys

n = int(sys.stdin.readline().rstrip())
arr = [int(sys.stdin.readline().rstrip()) for i in range(n)]

stk = []
cnt = 0

for i in range(n):
    top = arr[i]
    ans = 1

    while stk and stk[-1][0] <= top:
        if stk[-1][0] == top:
            cnt += stk[-1][1]
            ans = stk[-1][1] + 1
            stk.pop()
        else:
            cnt += stk[-1][1]
            stk.pop()

    if stk:
        cnt += 1

    stk.append((top, ans))

print(cnt)

 

스택 어렵다. 내일 또 다시 풀어봐야겠다..