하효닝
log(hahyun ^ B)
하효닝
전체 방문자
오늘
어제
  • 분류 전체보기 (140)
    • Diary (0)
    • Web (7)
    • Frontend (8)
    • Python (44)
      • Python (1)
      • Algorithm (13)
      • Coding Test (30)
    • Django (3)
      • Django (2)
      • Django Rest (1)
    • Java (14)
      • Java (10)
      • Java Tuning (4)
    • Spring (34)
      • Spring (7)
      • Spring MVC (5)
      • DB 접근기술 (1)
      • JPA (10)
      • Spring Security (3)
      • Rest API (8)
    • Computer Science (26)
      • Operating System (8)
      • Linux (2)
      • Network (2)
      • Database (9)
      • SQL Tuning (5)
    • AWS (2)
    • Git (0)
    • etc (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
하효닝

log(hahyun ^ B)

Python/Coding Test

1863 스카이라인 쉬운거

2022. 2. 26. 20:54

문제

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

 

접근

  • 건물 겉넓이, 빗물 트래핑, 주식 매매 같은 문제랑 비슷한 거 같아서 스택으로 풀이했다.

 

풀이

  • 입력받은 y에 대해 스택에는 y보다 낮은 높이의 건물만 있도록 pop하면서 ans에 1씩 더한다.
  • y가 스택에 있는 마지막 요소랑 같거나 0인 경우에는 스킵하고, 더 작은 경우 append한다.
  • 모든 입력을 처리한 후 스택에 남아있는 원소들을 pop하면서 ans에 1씩 더한다.
n = int(input())
stack = []

ans = 0
for _ in range(n):
    x, y = map(int, input().split())

    while stack and stack[-1] > y:
        stack.pop()
        ans += 1

    if y == 0:
        continue

    if not stack or stack[-1] < y:
        stack.append(y)

while stack:
    stack.pop()
    ans += 1
print(ans)

 

'Python > Coding Test' 카테고리의 다른 글

22871 징검다리 건너기 (large)  (0) 2022.02.27
22869 징검다리 건너기 (small)  (0) 2022.02.27
20182 골목 대장 호석 - 효율성 1  (0) 2022.02.25
21277 짠돌이 호석  (0) 2022.02.24
10703 유성  (0) 2022.02.24
    'Python/Coding Test' 카테고리의 다른 글
    • 22871 징검다리 건너기 (large)
    • 22869 징검다리 건너기 (small)
    • 20182 골목 대장 호석 - 효율성 1
    • 21277 짠돌이 호석
    하효닝
    하효닝

    티스토리툴바