[PS | 한 번에 맞자!] 백준 1863

0. 문제

스카이라인 쉬운거

1863번: 스카이라인 쉬운거

 

1. 문제 생각

처음에는 스카이라인이라고 해서 라인스위핑이겠거니 하고 달려들었다! 하지만 예제를 보면 처참히 깨질 수 있는데.. 하나씩 순차적으로 파악하는 형태의 로직이 아니다. 

즉, 앞에서의 상황이 뒤에 의존될 수 있다.

입력값에서 주어지는 것은 '스카이라인의 고도가 바뀌는 지점의 좌표 x와 y' 이다. 즉, 이 곳에서는 무조건! 고도가 바뀌어야 한다. 그렇다면 위 그림의 상황을 한 번 보자. 같은 높이에 찍혀 있는 두 점은 절대 같은 건물일 수 없다. 왜냐하면 가운데에서 고도가 한 번 무조건 바뀌어야 하기 때문!

2. 문제 풀이 (종이)

3. 문제 구현

N=int(input())
ans=0
Lines=[0]
for _ in range(N):
    a,b=map(int,input().split())
    while Lines and Lines[-1]>=b:
        if Lines[-1]>b:     
            ans+=1
            Lines.pop()
        else:
            Lines.pop()
    Lines.append(b)
    # print('답',ans)
a,b=1000001,0;
while Lines and Lines[-1]>=b:
    if Lines[-1]>b:     
        ans+=1
        Lines.pop()
    else:
        Lines.pop()
Lines.append(b)
print(ans)

4. 한 번에 풀었는가? X

처음에는 Dictionary로 건물을 그룹짓는 것으로 로직을 생각하여 틀렸고, 두 번째에는 마지막에 건물이 무조건 끝나는 것을 고려하지 않아 틀렸다(이는 마지막 입력값으로 1000001, 0의 좌표가 들어가는 것을 가정하여 풀 수 있다.)