Skip to content

Latest commit

 

History

History
336 lines (251 loc) · 10.1 KB

1863.md

File metadata and controls

336 lines (251 loc) · 10.1 KB

Index

스카이라인 쉬운거

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

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

입력

첫째 줄에 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

권준혁

접근법 (생각의 흐름 설명)

문제의 예제를 계속 관찰하면서 패턴을 파악해야 했던 문제다.
주어진 입력에 맞춰 왼쪽부터 빌딩 높이를 탐색한다.
현재 확인하는 빌딩 높이가 이전까지 발견한 가장 높은 빌딩 높이보다:

  • 낮은 경우: stack의 마지막 값이 현재 높이와 같아질 때까지 pop
  • 높은 경우: push

상세한 해설

본 문제는 빌딩 높이에 대해 제한 조건을 두고 stack을 활용해서 push와 pop을 진행한다.

  • pop을 진행하는 상황:
    • 현재까지 탐색한 가장 높은 높이보다 낮은 높이가 발견된 경우 -> 현재 높이보다 높은 빌딩들이 x방향으로 가장 넓게 만들 수 있는 상황. 즉, 빌딩 개수가 최소가 되게 하는 상황
        while (stk and stk[-1] > y):
            answer += 1
            stk.pop()
  • push를 하는 상황:
    • 현재까지 탐색한 가장 높은 높이보다 높은 높이가 발견된 경우 -> 지금까지 발견된 빌딩들이 x방향으로 계속 확장 및 새 빌딩 추가해야 함.
        if not (stk and stk[-1] == y):
            stk.append(y)
  • 시간 복잡도:
    • O(N)
for문 -> N번
while문 -> 1~N사이인데,
while문이 N번 시행되는 경우는 지금까지 모든 빌딩들이 계단식으로 하니씩 증가한 것  
    -> 이러면 그동안은 while문이 한번도 동작을 안하게 됩니다.  
    -> 그래서 마지막에만 while문이 동작하고 N번 연산이 되서  
    -> 1 + 1 + 1 + ... + 1 + N = 2N -> O(N)됩니다.

회고

자료구조에서 stack 유형은 스택인지 파악이 좀 어려운 편인 것 같다.

  1. 처음부터 해법이 생각나면 좋겠지만, 바로 떠올리기는 어려워서, 문제 상황을 보고 자료 구조를 대입해서 생각해보는 훈련을 하면 좋을 듯하다.
  2. 따라서, 무언가 자료를 저장하다가 flush하는 형태가 나오면 stack, queue를 의심해보는 행동이 필요할 것 같다.

Solution

import sys
input = sys.stdin.readline

if __name__ == '__main__':
    N = int(input().strip())
    stk = []
    answer = 0
    for _ in range(0, N):
        x, y = map(int, input().split())
        while (stk and stk[-1] > y):
            answer += 1
            stk.pop()
        if not (stk and stk[-1] == y):
            stk.append(y)
    print(answer + len([val for val in stk if val > 0]))

안지완

접근법 (생각의 흐름 설명)

단순히 고도가 바뀔 때마다 빌딩의 갯수를 늘려나가면 되는 것 아니냐할 수 있지만, 고도가 더 낮은 빌딩이 밑에 있을 수 있다.

따라서, 스택을 이용해서 입력값이 만일 스택의 맨 앞 원소보다 높을 때만 바로 push한다.

허나, 고도가 더 낮은 빌딩이 밑에 있는 것은 따로 한번 더 고려해야 한다.

상세한 해설

건물이 하나 더 있는 것은, 기존의 건물보다 높거나, 아니면 가장 고도가 낮은 기존의 건물보다 더 낮고 최소 1층이 있을 때 빌딩의 갯수를 증가시켜야 한다.

이를 조건문으로 나타내면 다음과 같다.

while len(stack) > 0 and arr[i] < stack[-1]:
    stack.pop()
if len(stack) == 0 or stack[-1] != arr[i]:

즉, 기존 건물보다 낮을 때만 그동안 있던 stack을 모조리 pop하고, 1층 이상일 경우 push를 하는 것이다. 만일 기존 건물과 같다면 당연히 stack에 push되지 않을 것이다.

회고

보통 이런식으로 최대, 최소가 나오면 대게 stack을 사용하는 경우가 많다. 이를 인지를 하고 있으면 자료구조 문제는 웬만하면 쉽게 풀린다.

Solution

n = int(input())
arr = [0 for _ in range(n)]
stack = []
ans = 0

for i in range(n):
    x,y = map(int,input().split())
    arr[i] = y

stack.append(arr[0])
if arr[0] > 0:
    ans += 1
for i in range(1,n):
    if arr[i] > stack[-1]:
        stack.append(arr[i])
        ans += 1
    else:
        while len(stack) > 0 and arr[i] < stack[-1]:
            stack.pop()
        if len(stack) == 0 or stack[-1] != arr[i]:
            stack.append(arr[i])
            if arr[i] != 0:
                ans += 1
print(ans)

오효근

접근법 (생각의 흐름 설명)

처음에는 정렬 혹은 heapq를 사용하나 싶었지만 순서가 중요한 문제이기 때문에 list 혹은 deque을 사용해야한다고 생각했다. 현재 deque의 마지막 값보다 큰 입력이 입력되면 append, 작은 입력이 입력되면 pop을 사용하는 것으로 생각했다.

상세한 해설

문제에서 x는 사용하지 않기에 버려준다. (어차피 순서대로 들어오기 때문) 접근법에서 언급한 것과 같이 아래와 같이 구현하면 끝이다.

while 1 < len(height) and y < height[-1]:
    height.pop()
    cnt += 1
if not height[-1] == y:
    height.append(y)

시간 복잡도는 $O(n^2)$이다.

회고

무난한 문제였지만 처음 풀이에서 while문을 당연히 안쓸거라는 선입견에 생각보다 시간이 걸렸다.

Solution

import sys

read = sys.stdin.readline

if __name__ == "__main__":
    n = int(read())
    cnt = 0
    height = [0]
    for i in range(n + 2):
        if i in [0, n + 1]:
            x, y = 0, 0
        else:
            x, y = map(int, read().split())
        while 1 < len(height) and y < height[-1]:
            height.pop()
            cnt += 1
        if not height[-1] == y:
            height.append(y)
    print(cnt)

조은학

접근법 (생각의 흐름 설명)

  • 처음엔 잘못 풀었다.
  • 처음에는 집합 자료구조로 0으로 구분해서 12131, 2321 로 묶어서 각각 집합으로 처리해 123, 123 총 6개로 답을 도출했다.
  • 하지만 반례로, 22114422 이런식으로 되어 있을 경우에는 4개가 필요하기 때문에 문제가 있는 풀이다.

잘못된 풀이

import sys

n = int(sys.stdin.readline().strip())
buildings = []
tmp = []
for i in range(n):
    # print(buildings)
    x, y = map(int, input().split())
    if(y!=0):
        tmp.append(y)
    else:
        buildings.append(set(tmp))
        tmp=[]

buildings.append(set(tmp))

answer = 0
for i in range(len(buildings)):
    answer += len(buildings[i])
# print(buildings)
print(answer)
  • 따라서 다시 생각하다보니 스택으로 풀어야겠다는 생각을 하게 되었다.

상세한 해설

  • while( stack and (buildings[i] < stack[-1])):: 스택이 비어있지 않고 현재 건물의 높이가 스택의 맨 위 건물보다 작은 경우 반복

  • stack.pop(): answer += 1: answer를 더해주면서 스택의 건물 제거

  • if(stack and (buildings[i] == stack[-1])):: 스택이 비어있지 않고 현재 건물의 높이가 스택의 맨 위 건물과 같은 경우 continue

  • stack.append(buildings[i]): 현재 건물을 스택에 추가 (스택의 맨위 건물과 같은 경우에는 추가 안함)

  • 마지막 while 문에서 0일 경우를 제외시켜줘야 한다.

  • 최악일 경우 O(n^2)이라고 생각한다.

회고

  • 스택 문제 같은 경우에 스택이란 것을 알아도 접근을 잘못하면 늪에 빠지는 경우가 있는 것 같다...
  • 따라서 스택에 넣는 조건과 빠지는 조건을 미리 생각한다음에 코딩을 시작하는 것이 좋을 것 같당

Solution

import sys

n = int(sys.stdin.readline().strip())
stack = []
buildings = []
answer = 0
for i in range(n):
    x, y = map(int, input().split())
    buildings.append(y)

stack.append(buildings[0])

for i in range(1,len(buildings)):
    while( stack and (buildings[i] < stack[-1])):
        stack.pop()
        answer += 1
    if(stack and (buildings[i] == stack[-1])):
        continue
    stack.append(buildings[i])

while(stack):
    if(stack[-1]>0):
        answer += 1
    stack.pop()

print(answer)