풀이 날짜:2025-03-23

💡Github URL

: https://github.com/ejjem/coding-test/tree/main/SWEA/D3/1206.%E2%80%85%EF%BC%BBS%EF%BC%8FW%E2%80%85%EB%AC%B8%EC%A0%9C%ED%95%B4%EA%B2%B0%E2%80%85%EA%B8%B0%EB%B3%B8%EF%BC%BD%E2%80%851%EC%9D%BC%EC%B0%A8%E2%80%85%EF%BC%8D%E2%80%85View

💡문제에서 구해야 할 것

문제 조건 :

• 양쪽 모두 거리 2 이상의 공간이 확보될 때 조망권이 확보된다고 말함.
• 빌딩들의 정보가 주어질 때, 조망권이 확보된 세대의 수를 반환하는 프로그램을 만들어야함.
  [제약 사항]
• 가로 길이는 항상 1000이하.
• 맨 왼쪽 두 칸과 맨 오른쪽 두 칸에는 건물이 지어지지 않음.
• 각 빌딩의 높이는 최대 255.

---

• 입력
  • 총 10개의 테스트케이스가 주어짐.
  • 각 테스트케이스의 첫 번째 줄에는 건물의 개수 N이 주어짐 (4 ≤ N ≤ 1000).
  • 그 다음 줄에는 N개의 건물의 높이가 주어짐 (0 ≤ 각 건물의 높이 ≤ 255).
  • 맨 왼쪽 두 칸과 맨 오른쪽 두 칸에 있는 건물은 항상 높이가 0.
• 출력
  • #부호와 함께 테스트케이스의 번호를 출력하고, 공백 문자 후 조망권이 확보된 세대의 수를 출력.
  • Ex)

			#1 111
			#2 60
			#3 165

💡알고리즘 설계

1. 10번 반복하는 for문 선언 (테스트케이스가 10번 주어짐)
2. 매 시행마다 입력되는 건물 갯수 N과 N개의 건물 높이를 각각 변수 N, 리스트 tower에 저장
3. 리스트의 인덱스를 따라갈 for문 선언, 이 때 건물 높이 항상 0인 좌우 맨 끝 2개씩은 제외( range(2, N - 2) )
   • tower[i]가 좌우 2개보다 클 경우 탐색. 이는 조망권이 확보될 수 있는 tower[i]를 찾는 것.
   • 조망권이 존재하는 tower[i]는 좌우 2개의 건물 중 높이의 최댓값을 tower[i]의 높이에서 뺌 → 조망권 계산.
   • 각 시행마다 모든 조망권을 계산하여 저장함.
4. 결과를 정해진 형식에 맞춰 출력

💡코드

메모리: 59,520 KB, 시간: 77 ms, 코드길이: 400 Bytes

answer = []
for n in range(1, 11):
  N = input()
  tower = [int(x) for x in input().split()]
  count = 0
  for i in range (2, N - 2):
    if (tower[i] > tower[i-2]) and(tower[i] > tower[i-1]) and (tower[i] > tower[i + 1]) and (tower[i] > tower[i + 2]):
      count += tower[i] - max(tower[i-1], tower[i-2], tower[i+1], tower[i+2])
  answer.append(f"#{n} {count}")

print("\n".join(answer))

💡시간 복잡도

• 외부 시간 복잡도
  • for문 → O(M), M = 10이므로 O(10)

• 내부 시간 복잡도
  • for문 → O(N - 4) ≈ O(N)
  • 각 시행 시 조건문 ≈ O(1)

• 최종 시간 복잡도
  • O(10) * ( O(N) + O(1) ) ≈ O(N)

💡 틀린 이유 & 틀린 부분 수정

맞음.

💡 다른 풀이 or 기억할정보

• all() 함수 적용

if (tower[i] > tower[i-2]) and(tower[i] > tower[i-1]) and (tower[i] > tower[i + 1]) and (tower[i] > tower[i + 2]):

를 아래와 같이 바꿀 수 있음.

if all(tower[i] > tower[i+j] for j in [-2, -1, 1, 2]):

if all(tower[i] > tower[j] for j in [i-2, i-1, i+1, i+2]):

• 함수 최적화 by GPT

answer = []

for n in range(1, 11):
    input()  # N은 사용하지 않으므로 생략 처리
    tower = list(map(int, input().split()))
    count = 0

    for i in range(2, len(tower) - 2):
        if all(tower[i] > tower[j] for j in [i-2, i-1, i+1, i+2]):
            count += tower[i] - max(tower[i-2], tower[i-1], tower[i+1], tower[i+2])

    answer.append(f"#%d %d" % (n, count))

print("\n".join(answer))