Algorithm (Python, Java, SQL)/BaekJoon

[백준 1863번] 스카이라인 쉬운거 (Python)

sanadoing_ 2023. 11. 13. 20:27
728x90

> 파이썬, 자료 구조, 스택

 

 

 

 

📖 문제 : 스카이라인 쉬운거 (Python)

 

 

 

도시에서 태양이 질 때에 보이는 건물들의 윤곽을 스카이라인이라고 한다. 스카이라인만을 보고서 도시에 세워진 건물이 몇 채인지 알아 낼 수 있을까? 건물은 모두 직사각형 모양으로 밋밋하게 생겼다고 가정한다.

정확히 건물이 몇 개 있는지 알아내는 것은 대부분의 경우에 불가능하고, 건물이 최소한 몇 채 인지 알아내는 것은 가능해 보인다. 이를 알아내는 프로그램을 작성해 보자.

 

 

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 번째 지점의 x좌표는 항상 1이다.

 

출력

첫 줄에 최소 건물 개수를 출력한다.

 

예제 입력 1 

10
1 1
2 2
5 1
6 3
8 1
11 0
15 2
17 3
20 2
22 1
 

 

예제 출력 1 

6

 

 

 

 

내 코드

N = int(input())
buildings = []
result = 0
for _ in range(N):
    x, y = map(int, input().split())
    if y == 0:
        result += len(buildings)
        buildings = []
    else:
        if len(buildings) == 0:
            buildings.append(y)
        else:
            while len(buildings) > 0 and buildings[-1] > y:
                buildings.pop()
                result += 1
            if len(buildings) > 0 and buildings[-1] == y:
                continue
            else:
                buildings.append(y)
print(len(buildings) + result)

 

 

 

Point ! ⭐️ 

  • 이 문제의 예제 1번을 보고는 
    0이 나오면 리스트를 비워주고, 그게 아니라면 그 리스트에 모든 수를 다 넣어서 set (집합)의 길이를 결과값에 계속 더해주는 방법을 생각해서 구현하니 7%에서 틀리더라구요 

    하지만 ! 반례가 있다는 것
    4
    1 4
    2 3
    3 5
    4 4
    의 경우 건물의 높이를 보면
    4 3 5 4 이렇게 되는데 저의 처음 방법대로라면 결과값이 3이 나오지만, 나와야하는 값은 4 입니다. 
    왜냐하면, 위치 1과 4의 4높이의 건물이 하나의 건물이라고 생각하면 2위치에 있는 3높이의 건물은 보이지 않을 것입니다. 
    그러므로 위치 1과 4의 건물은 각각 하나씩 총 2개의 건물이라고 생각해야하기 때문에 총 4개의 건물이 되는 것입니다. 

    이 반례를 토대로 저는 stack 을 사용하여 구현하였습니다. 
    stack 쌓이는 기준은 기존 stack 안에 있는 수보다 무조건 커야 그 스택에 들어갈 수 있으며
    들어오는 수가 스택의 가장 위의 수보다 작으면 기존 스택에 있는 수를 들어오는 수보다 작을 때까지 pop 해주면서 결과값에 +1씩 해줍니다. 그러곤 마지막에 스택에 남아있는 수들의 갯수와 합해 결과값에 더하여 출력합니다. 

    참고로 들어오는 수와 스택의 가장 위의 수와 값이 같을 경우는,
    그냥 스택에 들어오는 수를 넣지 않습니다. 

 

 

 

 

 

백준

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

 

1863번: 스카이라인 쉬운거

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫

www.acmicpc.net

 

728x90