[알고리즘/그리디] 1863번 : 스카이라인 쉬운거 - python

링크 : https://www.acmicpc.net/problem/1863

1863번: 스카이라인 쉬운거

 

---

• 문제
• 소요시간: 35분

 

---

• 설계하기(접근방법) 

1. 입력받기

입력이 많기 때문에

sys로 입력받는다

 

 

2. 구현하기

이 문제를 가로로 살펴보면 알 수 있는 포인트가 있다

1층을 기준으로 설명하면 건물이 끝나는 지점까지는

1층은 얼마나 확장하든 한 건물로 취급할 수 있다.

 

즉 한번 올라간 n층은 n-1층으로 스카이라인이 하강하지 않는다면 유지된다

반대로 처음 올라간 n층은 항상 한 건물을 추가해야 스카이라인을 만들 수 있다

 

즉 리스트 내에 건물의 층수를 넣어준다

 

height = [1] 처음엔 1층이 들어간다고 하자

 

2층이 생겼으면 건물의 개수를 추가하고

height = [1,2]가 될 것이다.

다음에 어떤 건물이 와도 1,2,층은 고려하지 않아도 된다

 

4층이 생겼으면 건물의 개수를 추가하고

height = [1,2,4]가 될것이다

 

만약 다음 스카이라인이 1층이라면

리스트 내에 1층이 있으니 건물을 추가하지 않아도 되지만

height = [1]로 바뀌면서 2,4 층의 확장은 더 이상 건물의 추가없이는 불가능하다

 

 

 

 

3. 출력하기

이 조건을 구현해서 건물의 최소 개수를 출력한다

 

 

---

• 코드(출력)

import sys

input = sys.stdin.readline

n = int(input())



height = []
building = 0

for i in range(n):
    x, y = map(int, input().split())
    if y == 0:
        height = []
        continue
    elif len(height) != 0 and height[-1] > y:
        temp = []
        for j in height:
            if j > y:
                temp.append(j)
        for k in temp:
            height.remove(k)
    if y not in height:
        height.append(y)
        building += 1
    else:
        continue

print(building)

---

• 얻어갈 부분

1. 조건문을 복잡하게 구성해서 독해하기 어려웠다. continue break pass 지점을 정확히 파악해서 넣지 않으면 구현이 잘못되니 주의하자