백준 1027번: 고층 건물 (G4) - Python, Swift 풀이

문제 설명

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

세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 빌딩의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 1번 빌딩부터 그 높이가 주어진다. 높이는 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1

15
1 5 3 2 6 3 2 6 4 2 5 7 3 1 5

예제 출력 1

7

예제 입력 2

1
10

예제 출력 2

0

예제 입력 3

4
5 5 5 5

예제 출력 3

2

예제 입력 4

5
1 2 7 3 2

예제 출력 4

4

예제 입력 5

10
1000000000 999999999 999999998 999999997 999999996 1 2 3 4 5

예제 출력 5

6

풀이 과정

빌딩의 수는 제일 많아도 50이기 때문에 그냥 하나씩 다 살펴보는 완전탐색 문제입니다. 다만 수학적 개념도 좀 필요합니다.

건물의 꼭대기를 좌표 평면의 (i, 높이) 라는 점으로 본다면, 건물 A에서 다른 건물들의 꼭대기를 이었을 때 이전 선분의 기울기보다 기울기가 큰 선분이 되는 경우에만 A에서 보이는 건물이 됩니다.

이게 무슨 소리냐면, 그림으로 보겠습니다.

데이터가 1 5 3 2 6 3 일 때 높이 5인 건물에서 다른 건물들의 꼭대기를 이은 그림입니다. 5와 6을 이은 선분의 기울기보다 5와 3을 이은 점선으로 이은 선분의 기울기가 더 작기 때문에 5에서 3은 보이지 않습니다.

여기서 기울기 비교가 이해 안 되시면 참고하시라고 그림 그려왔습니다.

마지막 사진에서 알 수 있듯이 더 오른쪽에 등장하는 점이 이전 점의 기울기랑 같거나 작으면 가려져서 안 보입니다. 무조건 더 오른쪽에 등장하는 점이 이전의 점들보다 기울기 값이 더 커지는 범위에 있어야 합니다.

i=1번째 건물부터 다른 건물로 선분을 그어서 이전까지의 최대 기울기보다 j번째 건물까지의 기울기가 더 크다면 건물 i에서 보이는 건물의 개수를 1 증가시키고, 건물 j에서 보이는 건물의 개수 또한 1 증가시킵니다. 건물 i에서 건물 j가 보인다는 것은 건물 j에서도 건물 i가 보인다는 뜻이기 때문입니다.

이런 로직으로 진행되기 때문에 항상 건물 i의 오른쪽 범위만 확인하면 됩니다. 건물 i의 왼쪽 범위는 이전 i 값에서 구해졌기 때문입니다. 위의 그림으로 설명하자면, i가 가장 왼쪽에 있는 1번일 때 5번과의 관계를 확인하며 ‘우리 서로 볼 수 있구나’ 하고 이미 ‘5번에서 보이는 건물의 개수’를 +1 했기 때문에 i가 5번이 되면 1번 점은 확인하지 않고, 바로 오른쪽의 3번부터 확인하면 됩니다.

정답 코드

import sys

# 입력
N = int(input())
heights = list(map(int, input().split()))

# 각 위치에서 보이는 빌딩의 수를 저장하기 위한 1차원 배열
answers = [0 for _ in range(N)]
# i는 0부터 N-2까지
for i in range(N-1):
  # 초기값을 최솟값으로 세팅
  max_slope = -sys.maxsize
  # j는 i+1부터 N-1까지
  for j in range(i+1, N):
    # 건물 i 꼭대기와 건물 j 꼭대기를 잇는 선분의 기울기 계산
    slope = (heights[j] - heights[i]) / (j-i)
    # 이전의 최대 기울기보다 현재 선분의 기울기가 더 크면 i와 j는 서로 볼 수 있는 건물!
    if max_slope < slope:
      # i에서 볼 수 있는 건물 개수 증가
      answers[i] += 1
      # j에서 볼 수 있는 건물 개수 증가
      answers[j] += 1
      # 최대 기울기 갱신
      max_slope = slope

# answers 배열의 최댓값이 정답
print(max(answers))

import Foundation

let N = Int(readLine()!)!
var heights: [Int] = readLine()!.split(separator: " ").map { Int($0)! }

var answers: [Int] = Array(repeating: 0, count: N)
for i in 0..<N-1 {
    var maxSlope:Double = Double(Int.min)
    for j in i+1..<N {
        let slope: Double = Double(heights[j] - heights[i]) / Double(j - i)
        if maxSlope < slope {
            answers[i] += 1
            answers[j] += 1
            maxSlope = slope
        }
    }
}

print(answers.max() ?? 0)

순서대로 Python, Swift 풀이입니다.

이상입니다.