17266. 어두운 굴다리

17266 문제 보기

접근 방식

1. 구현
2. 이분 탐색

첫 접근은 세상에 구현도 아니오 이분 탐색도 아닌 신기한 방법으로 풀이했다.
두번째 예제에서 무한루프가 돌아서 다시 풀이한 코드를 아래 최종 코드에 첨부한다.

접근 방식은 다음과 같다.
N개의 길이 모두 밝혀져야 하므로 밝혀지지 않은 길은 0으로 초기화해 path 배열에 넣어줬다.
반복 종료 조건을 path.count(0) == 0으로 설정해 가로등의 높이인 light_length를 업데이트해줬더니, 뭔가 이상함 😅

하지만 배운 것!
path 배열의 left~right까지 값을 갱신해주고 싶었는데,
이 때 리스트 컴프리헨션을 사용해 path[left:right] = [light_length for _ in path[left:right]]와 같은 방식으로 갱신하면 된다!

import sys
input = sys.stdin.readline

N = int(input().rstrip()) # 굴다리 길이
M = int(input().rstrip()) # 가로등 개수
pos = list(map(int, input().rstrip().split())) # 가로등의 위치 x(M개의 값)
light_length = 0 # 가로등 높이

path = [0 for _ in range(N)]
while True:
  if path.count(0) == 0: # 밝혀지지 않은 길이 없는 경우
    break
  else: # 밝혀지지 않은 길이 있는 경우
    light_length += 1 # 가로등 높이 + 1
    for i in range(M):
      left, right = 0, 0
      if pos[i] - light_length <= 0:
        left = 0
      elif pos[i] + light_length > N:
        right = N
      else:
        left, right = pos[i] - light_length, pos[i] + light_length
      path[left:right] = [light_length for _ in path[left:right]]
      light_length: {light_length}, path: {path}')

print(light_length)

최종 코드

구현 풀이

• 가로등이 밝혀야 하는 최대 거리 계산
• 최소 높이값 계산

import sys
input = sys.stdin.readline

N = int(input().rstrip()) # 굴다리 길이
M = int(input().rstrip()) # 가로등 개수
pos = list(map(int, input().rstrip().split())) # 가로등의 위치 x(M개의 값)

max_gap = max(pos[0], N - pos[-1]) * 2 # 좌우 포함 가로등이 밝혀야 하는 최대 거리
for i in range(1, M):
  max_gap = max(max_gap, pos[i] - pos[i-1])

light_height = (max_gap + 1) // 2 # 최소 높이값 계산
print(light_height)

이분탐색 풀이

1. 리스트 오름차순 정렬
2. 중간값(mid)이 찾으려는 값(target)인지 비교
3. mid != target의 경우 대소관계에 따라 탐색 범위 좁힘
   mid == target까지 아래 조건에 맞춰 2, 3번 과정 반복

• target < mid : end를 mid 왼쪽 값으로 변경(end = mid - 1)
  • 절반의 왼쪽 탐색
• target > mid : start를 mid 오른쪽 값으로 변경(start = mid + 1)
  • 절반의 오른쪽 탐색

def binary_search(arr, mid):
    if arr[1] - arr[0] > mid:
        return 0
    if arr[-1] - arr[-2] > mid:
        return 0
    for i in range(1, len(arr) - 2):
        if (arr[i+1] - arr[i]) / 2 > mid:
            return 0
    return 1

N, M = int(input()), int(input())
arr = [0] + list(map(int, input().split())) + [N]
start, end = 0, N
res = 0
while start <= end:
    mid = (start + end) // 2
    if binary_search(arr, mid):
        end = mid - 1
        res = mid
    else:
        start = mid + 1
print(res)

배운점

▶️ 리스트 컴프리헨션으로 데이터의 일정 범위 값만 갱신해주는 방법

• path 배열의 left~right까지 값을 갱신
• path[left:right] = [light_length for _ in path[left:right]]와 같은 방식으로 갱신

▶️ 이분탐색 관련 참고 자료