[Gold IV] 데이터 체커 - 22942 (스택)

[Gold IV] 데이터 체커 - 22942

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

- 접근 방법

처음 문제를 보면 원의 내접, 외접, 두 점 사이의 거리 등의 수식이 주어져서 수학 문제인가 싶었지만, 문제를 다 읽고보니 x 좌표에 원점을 중심으로 원이 겹치지 않게 구분하는 문제임을 알 수 있었다.

해당 문제를 해결하려면 하나의 원을 기준으로 다른 원이 아예 바깥 쪽에 위치하거나, 안쪽에 위치해야 하므로 원의 왼쪽 끝 x좌표와 오른쪽 끝 x좌표에 다른 원이 지나가면 안된다는 점을 알 수 있었다.

결국 이렇게 구현하려면 원의 왼쪽 끝, 오른쪽 끝 x좌표의 정보를 알고 있어야 했다. 그래서 각 원의 양쪽 지점을 동일한 수로 지정해주어 같은 원인지 다른 원인지 구분해주었다.
구분하고 보니 프로그래머스에서 풀어보았던 괄호 문제와 비슷한 그림이 나와서 스택을 생각해낼 수 있었다.

ex ) 1 0 0 1 2 0 2 3 0 3
리스트에 각각의 1번 원, 2번 원, 3번 원 양쪽의 끝 점을 표시

-해결 방법 ( 소요 시간 : 1시간 )

스택을 이용하여 풀기 위해 리스트에 각각의 원 번호를 표시해주었고, 원이 겹치지 않고 잘 그려졌는지 체크하기 위해 x 좌표의 제일 처음 올 수 있는 지점인 -1,000,000지점부터 순서대로 확인하였다. 주의해야 할 점은 x 좌표가 음수인 -1,000,000부터 있을 수 있으므로 리스트의 인덱스가 음수로 넘어갈 경우 맨 뒤 인덱스부터 탐색한다는 것을 이용했다.

리스트의 1,000,001인덱스(-1,000,000)부터 2,000,000인덱스(-1) 까지 순서대로 본 후, 리스트의 0인덱스(0)부터 1,000,000인덱스(1,000,000)까지 for문을 돌려서 -1,000,000 ~ 1,000,000 범위의 x 좌표를 확인했다. 

스택에서의 마지막 값이 탐색한 값과 같을 경우 원이 겹치지 않고 정상적으로 위치한 것이므로 스택에서 빼준다.
최종적으로, 스택을 확인했을 때 스택에 값이 남아있을 경우 겹치는 원이 있다는 것을 알 수 있다.

 

import sys
input = sys.stdin.readline
n = int(input())
v = [-1 for _ in range(2000001)]
stack = [-1]

for i in range(n):
    a, b = map(int,input().split())
    v[a-b], v[a+b] = i, i

for i in range(1000001, 2000001): # 음수부터 시작
    if v[i] != -1:
        if stack[-1] == v[i]: stack.pop()
        else: stack.append(v[i])

for i in range(1000001): # 0부터 시작
    if v[i] != -1:
        if stack[-1] == v[i]: stack.pop()            
        else: stack.append(v[i])
            
if len(stack)==1: print("YES")
else: print("NO")