import sys
input = sys.stdin.readline
N = int(input())
Q = []
for _ in range(N):
x,y = map(int,input().split())
if not Q:
if y!=0:
Q.append((x,y))
continue
if y==0 and Q[-1][1]>0:
Q.append((x,-1))
elif y*Q[-1][1]<0:
Q.append((x,y))
if Q[0][1]*Q[-1][1]>0:
Q.pop(0)
if Q[0][1]<0:
Q.append(Q.pop(0))
stack = []; N = len(Q)//2
for i in range(N):
stack.append(sorted([Q[i*2][0],Q[i*2+1][0]]))
stack.sort()
big=small=0; end=last=-1e10
for i in range(N):
s,e = stack[i]
if s>last:
small += 1
if s>end:
big += 1
end = e
last = e
print(big,small)문제를 잘못읽어서 약간 더 어렵게 해결한 문제.
아이디어 자체는 매우 간단한 문제인데 구현이 까다로울 수 있다.
풀이를 설명하면,
1. 입력되는 좌표가 음수에서 양수, 혹은 양수에서 음수로 바뀌는 경우에 저장한다.
2. 양수에서 음수, 음수에서 양수로 바뀌는 한 쌍이 곧 봉우리이다. 이를 stack에 x좌표만 튜플로 저장한다. (y좌표는 다각형의 특성상 겹치지 않기 때문에 저장할 필요 없다)
3. 봉우리를 시작좌표에 대해서 정렬한다.
4. 정렬한 봉우리에 대해서 앞에서부터 체크해나간다. 체크하면서 이전 봉우리의 끝점을 last로 저장한다.
5. 만약 현재 봉우리의 시작점이 end보다 클 경우, big(다른 봉우리에 포함되지 않는 봉우리) 의 개수를 1 늘리고 end를 현재 봉우리의 끝점으로 갱신한다.
6. 만약 현재 봉우리의 시작점이 last보다 클 경우, small(다른 봉우리를 포함하지 않는 봉우리) 의 개수를 1 늘린다.
이때 1,2에서 봉우리를 탐사할 때 고려해야할 요소가 있다. 중간에는 양수에서 음수, 음수에서 양수로 바뀔때만 삽입하면 되지만 맨 처음이 문제이다. 맨 처음에는 일단 입력을 받되, 만약 맨 마지막 좌표와 맨 처음 좌표의 y값의 부호가 같다면 맨 처음 좌표는 버려준다. 또, 양수>>음수가 한 쌍의 봉우리이기 때문에, 맨 처음 좌표의 y좌표가 음수인 경우 가장 뒤로 보내준다.
참고로 나는 이 문제에서 y좌표의 값이 0인 입력값이 있다고 가정하고 풀어서 입력하는 조건문이 좀 더 복잡하다.
이 조건을 없애면 아래와 같이 좀 더 간략하게 코드를 짤 수 있다.
import sys
input = sys.stdin.readline
N = int(input())
Q = [[*map(int,input().split())]]
for _ in range(N-1):
x,y = map(int,input().split())
if Q[-1][1]*y<0:
Q.append([x,y])
if Q[0][1]*Q[-1][1]>0:
Q.pop(0)
if Q[0][1]<0:
Q.append(Q.pop(0))
stack = []; N = len(Q)//2
for i in range(N):
stack.append(sorted([Q[i*2][0],Q[i*2+1][0]]))
stack.sort()
big=small=0; end=last=-1e10
for i in range(N):
s,e = stack[i]
if s>last:
small += 1
if s>end:
big += 1
end = e
last = e
print(big,small)
오늘의 교훈) 항상 문제를 꼼꼼히 읽자