백준 1027 고층건물 파이썬 풀이

난이도 : 골드4

풀이일 : 04307

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

1027번: 고층 건물

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

중간 과정

처음에는 이렇게 건물 높이를 그림으로 그려놓고 어떻게 접근해야 할 지 생각했다.

실제 코드에서는 저런 식으로 배열을 만들 게 아니니까 메모리 같은 것들은 고려하지 않았고,

건물의 최대 개수도 50개여서 시간도 고려하지 않았다.

 

# 1. 모든 건물에 대해 좌, 우 방향 탐색
# 2. 볼 수 있는 건물의 개수 세기
#    발견한 옆 건물 높이 기록 buildings[i] > 건물 => h = 0
#    1. 좌측탐색
#       1. h == 0 and buildings[j] < buildings[i]
#          기울기 : (buildings[i]-buildings[j]) / (i-j) 기록
#          기록된 숫자보다 기울기가 작으면 temp += 1, 기울기 재할당
#       2. h == 0 and buildings[j] > buildings[i]
#          temp += 1, h = 1
#          기울기 : (buildings[i]-buildings[j]) / (i-j) 기록
#       3. h == 1 and buildings[j] > buildings[i]
#          기록된 숫자보다 기울기가 작으면 temp += 1, 기울기 재할당
#       4. h == 1 and buildings[j] < buildings[i]
#          그냥 넘어가기
# 3. maxi 보다 크다면 재할당
# 4. 최종 maxi 값 출력

import sys

N = int(sys.stdin.readline().strip())
buildings = list(map(int, sys.stdin.readline().split()))
maxi = 0

for i in range(N):
    temp = 0
    h, r = 0, 1000000001
    for j in range(i-1, -1, -1):
        if h:
            if (buildings[i] - buildings[j]) / (i - j) < r:
                r = (buildings[i] - buildings[j]) / (i - j)
                temp += 1
                print(f'i={i}, j={j}, r={r}')
        else:
            if buildings[j] < buildings[i] and (buildings[i] - buildings[j]) / (i - j) < r:
                r = (buildings[i] - buildings[j]) / (i - j)
                temp += 1
                print(f'i={i}, j={j}, r={r}')
            elif buildings[j] > buildings[i]:
                r = (buildings[i] - buildings[j]) / (i - j)
                temp += 1
                h = 1
                print(f'i={i}, j={j}, r={r}')
            elif buildings[j] == buildings[i]:
                r = 0
                temp += 1
                h = 1
                print(f'i={i}, j={j}, r={r}')
    h = r = 0
    for j in range(i + 1, N):
        if h:
            if (buildings[j] - buildings[i]) / (j - i) > r:
                r = (buildings[j] - buildings[i]) / (j - i)
                temp += 1
                print(f'i={i}, j={j}, r={r}')
        else:
            if buildings[j] < buildings[i] and (buildings[i] - buildings[j]) / (j - i) > r:
                r = (buildings[j] - buildings[i]) / (j - i)
                temp += 1
                print(f'i={i}, j={j}, r={r}')
            elif buildings[j] > buildings[i]:
                r = (buildings[j] - buildings[i]) / (j - i)
                temp += 1
                h = 1
                print(f'i={i}, j={j}, r={r}')
            elif buildings[j] == buildings[i]:
                r = 0
                temp += 1
                h = 1
                print(f'i={i}, j={j}, r={r}')

    print(f'i={i}, temp={temp}')
    if temp > maxi:
        maxi = temp

print(maxi)

며칠 동안 도전하는 족족 실패해서 오늘은 꼭 맞추겠다고 생각부터 하고 코드를 짰다.

완성 됐다 생각하고 확인하는데 마지막 예제 출력이 틀리게 나와서 print문을 찍어보다가 중단

다시 생각해보니까 어차피 기울기는 buildings[j] 값이 buildings[i] 보다 크건 작건 상관 없이 한 조건인데? 싶어져서 수정 시작

---

풀이 코드

# 1. 모든 건물에 대해 좌, 우 방향 탐색
# 2. 볼 수 있는 건물의 개수 세기
#    1. 좌측탐색 -> 기울기 -
#       기울기 : (buildings[i] - buildings[j]) / (i - j)
#    2. 우측탐색 -> 기울기 +
#       기울기 : (buildings[j] - buildings[i]) / (j - i)
# 3. maxi 보다 크다면 재할당
# 4. 최종 maxi 값 출력

import sys

N = int(sys.stdin.readline().strip())
buildings = list(map(int, sys.stdin.readline().split()))
maxi = 0

for i in range(N):
    temp = 0
    r = 1000000001
    for j in range(i-1, -1, -1):    # 좌측탐색
        if (buildings[i] - buildings[j]) / (i - j) < r:
            r = (buildings[i] - buildings[j]) / (i - j)
            temp += 1
    r = -1000000001
    for j in range(i + 1, N):    # 우측탐색 
        if (buildings[j] - buildings[i]) / (j - i) > r:
            r = (buildings[i] - buildings[j]) / (i - j)
            temp += 1

    if temp > maxi:
        maxi = temp

print(maxi)

정신차리고 간결하게 정리한 정답 코드

 

코드 구성

• 모든 건물에 대해 좌, 우 방향 탐색
• 기준 건물의 좌측 탐색 시, 기울기가 작으면 추가
• 우측 탐색은 기울기가 크면 추가 
• 한 기준 건물에서 보이는 건물 수와 최댓값 비교 후 재할당

---

느낀점

최근 며칠 시간을 많이 쏟고도 실패해서 티스토리를 못 올리거나 세이브 된 것들을 올리며 오늘은 꼭 풀겠다는 생각에 괜히 엉뚱한 짓만 함

정신차리고 내가 잘 풀 수 있는 문제는 정확하게, 빠르게 풀 수 있도록 연습하자