[백준] 스카이라인 쉬운거 (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

힌트

입력은 다음과 같은 스카이라인을 나타낸다.

..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....XXXXXXXXXXXX

다음과 같이 여섯 개의 빌딩이 있을 때가 최소 개수의 빌딩이 있는 상황이다.

..........................
.....22.........333.......
.111.22.......XX333XX.....
X111X22XXX....XX333XXXXXXX
..........................
.....XX.........XXX.......
.XXX.XX.......5555555.....
4444444444....5555555XXXXX
..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....666666666666

최종 코드

import sys

data = sys.stdin.readline

# 총 입력 줄
n = int(input())
# 초기 빌딩 리스트(값 비교 위해 0)
building = [0]
# 결과 빌딩 수
result = 0

# n만큼 반복
for _ in range(n):
  # x좌표 현재 y좌표
  x, cur_h = map(int, input().split())
  
  # 만약 현재 y좌표가 building에 담긴 값보다 크면?(높이가 있는 빌딩이 있는 경우)
  if cur_h > building[-1]:
    # 빌딩 수 +1
    result += 1
    # 해당 빌딩의 높이 리스트에 추가
    building.append(cur_h)
  # 현재 높이 cur_h가 기존에 담아놓은 building에 가장 최근에 담은 [-1]의 값보다 작으면
  elif cur_h < building[-1]:
    # 빌딩의 -1인덱스 값이 현재 높이보다 크다면?
    while building[-1] > cur_h:
      #마지막 요소 제거 반복
      building.pop()
    if building[-1] < cur_h:
      result += 1
      building.append(cur_h)
print(result)

코드 분석

일단 문제를 분석해보면, 건물에 대한 그림이 위의 힌트에 나와있고, 첫번째 x부터 비교해보면서 y의 값이 최소 건물 수에 영향을 주고 있는데,
만약 앞의 y가 뒤의 y보다 값이 작으면 건물이 추가되었다는 느낌은 아니고,

• 앞의 y보다 낮은 수가 등장하면 무조건 건물 +1
• 대신 앞의 y보다 높은 수가 등장할때도 건물 +1

이 두 조건을 잘 융화시키는게 문제이다.
어떤 관점으로 초점을 맞출지가 중요한데,
나는 이전 y값보다 현재 y값이 더 크면 건물 +1을 기본적으로 해주었고,
예외 처리로 이전 y값이 더 크면 이전 y값을 제거해주면서 어떻게든 현재 y값이 이전 값들보다 더 크도록 진행해주었다.
그러다 다시 이제 현재 y값이 이전 y값보다 높아졌을때 빌딩 +1을 추가해주었는데, 이렇게 글로 쓰면 헤깔릴 수 있다.
예제 입력처리로 예시를 들어야 확실히 이해가 될 수 있을랑 말랑하니 체크해보자

초기 값 building=[0], result=0 // [0]으로 해놓은 이유는 이전 값 비교위해
(1,1) // 현재 y 1이 이전 y 0보다 크므로 building=[0,1], result = 1
(2,2) // 현재 y값이 더 큼 building=[0,1,2], result= 2
(5,1) // 현재 y값이 더 작음 building=[0,1] 이제 이전 값이 현재 y값보다 큰게 없음, result=2
(6,3) // 현재 y값이 더 큼 building=[0,1,3], result=3
(8,1) // 현재y 더 작음 building=[0,1], result=3
(11,0)//현재 y 더 작음 building=[0], result=3
(15,2)//현재 y 더 큼 building=[0,2], result=4
(17,3)//현재 y 더 큼 building=[0,2,3], result=5
(20,2)//현재 y 더 작음 building=[0,2], result = 5
(22,1)//현재 y 더 작음 building=[0], 근데 이후 조건엔 현재 y가 더 커지게 됨 building=[0,1], result=6

이런식으로 처리를 해야하는 이유는 중간 y값이 0이되어서 건물이 나뉘어서 보여지는 상황이 있었고, 초기값 building=[0]보다 1이라도 크면 무조건 건물로 잡아야하는 상황이였다. 그래서 0 기준 1이라도 크면 building이 1개라도 있는거구나 인식했던 것이고, 무지성으로 앞의 y값보다 뒤의 y값이 크면 빌딩 수를 늘려버리면, 맨 마지막에 숫자 1에 대해선 처리가 되질 않는다.
그래서 맨 처음 생각엔 앞의 y보다 뒤의 y가 더 크면 건물+1해주고 break로 반복문을 멈춘 후, 마지막 값이 0이 아니면 +1을 해주는 식으로 접근했었는데, 틀린 코드라고 나왔다. 원인을 파악중인데...
애초에 for문을 세번이나 써야하고 정답도 이상하게 나왔다.
그리고 중간에 pop을 해줘야하는게 맞는게, 1321이런식으로 되어있는 수치가 3 이후로는 계속 현재 y값이 3보단 작으므로 2에 대해서는 건물을 더해줄 로직을 구현을 못해주는 상황인 셈이다. 그래서 이전에 넣었던 큰값을 제거하고나서야 2에 대에서도 1보단 크네? 그럼 너도 건물 1개 추가 이렇게 구현할 수 있는 것이다. 이걸 코드만 보고 하면 쉽지만 이해하고 그걸 로직짜는건 천지 차이 같다 ㅠㅠ

import sys

data = sys.stdin.readline

# 총 입력 줄
n = int(input())
# 초기 빌딩 리스트(값 비교 위해 0)
building = [0]
# 결과 빌딩 수
result = 0

n과 이전값과 비교위한 [0]을 담은 building 그리고 총 빌딩 수 담을 result 선언

# n만큼 반복
for _ in range(n):
  # x좌표 현재 y좌표
  x, cur_h = map(int, input().split())

n만큼 반복 시키며 x, cur_h 선언(계속 값이 바뀔 예정)

  # 만약 현재 y좌표가 building에 담긴 값보다 크면?(높이가 있는 빌딩이 있는 경우)
  if cur_h > building[-1]:
    # 빌딩 수 +1
    result += 1
    # 해당 빌딩의 높이 리스트에 추가
    building.append(cur_h)

현재 h가 이전 building에 담긴 최신 값보다 크면 빌딩이 추가된거고, 그 값을 building에 담아준다
여기까진 너무 쉬움!!

  # 현재 높이 cur_h가 기존에 담아놓은 building에 가장 최근에 담은 [-1]의 값보다 작으면
  elif cur_h < building[-1]:
    # 빌딩의 -1인덱스 값이 현재 높이보다 크다면?
    while building[-1] > cur_h:
      #마지막 요소 제거 반복
      building.pop()
    if building[-1] < cur_h:
      result += 1
      building.append(cur_h)

이 부분이 요물인건데
아까 말한 13211 경우 2에 대해서도 건물 추가시켜주기 위해서,
이전 빌딩의 -1 값이 현재 h보다 크면 현재 cur_h가 building의 -1보다 같거나 커질때까지 pop으로 제거시킨 다음에???
이제 다시 한번 if문을 통해 2에 대해서도 건물 +1을 추려낼 수 있는 것이다.
쉽지 않다 쉽지 않아....
개발자의 길은 멀고도 험하구나...!!