[코딩테스트] 어두운 굴다리

출처: https://www.acmicpc.net/problem/17266

문제 분석부터 해볼게요

일단 시간 제한은 1초이고, 메모리 제한은 256MB입니다. 그리고 N의 경우 100000까지, M은 이론상 100000까지 가능합니다. 따라서, 가능한 복잡도는 최대가 $O(NlogN)$ 까지 가능하다고 보시면됩니다.

그리고 이 문제에서 요구하는 바는, 가로등의 높이로 가능한 최소한의 숫자 입니다. 투포인터 기법을 사용해야하는 냄새가 짙게납니다.

일단, 문제풀이 전략부터 세워보겠습니다.

어떻게 풀까요?

일단 투포인터 기법으로 풀어야하는 것은 기정사실입니다. 그런데 투포인터 기법을 어떻게 적용해야할까요?

일단 문제를 보시면, 가로등이 비추는 도로는 범위 의 형태로 나타낼 수 있다는 것을 눈치챌 수 있습니다. 따라서 저는 튜플 자료형을 적극적으로 사용할겁니다.

그리고 x를 풀스캔하면서 가로등이 비추는 범위를 매번 저장을 할겁니다. 그리고 그 다음이 중요합니다. 임의의 i에 대하여 x[i], x[i + 1] 사이에 음영 지역이 발생하는지 검사를 해야합니다. 만일 음영지역이 발생했다면 그거는 잘못된 높이 값이기 때문에, 오히려 높이를 늘려주는게 맞는 경우입니다.

임의의 i에 대하여 x[i], x[i + 1] 사이에 음영 지역이 발생 안 했다고 합시다. 그런데 사실 그게 끝이 아닙니다. 저희는 아직 도로의 양 끝에 음영 지역이 발생했는지 검사를 한 적이 없습니다. 따라서 도로의 양 사이드에 음영이 발생했으면 높이를 늘리고, 음영이 없다면 높이를 좀 더 작게 해도 괜찮다는 뜻일겁니다.

그런데, 문제가 하나 있습니다. x가 딱 1개만 제공된 경우에는 i, i + 1을 검사할 수가 없다는 것인데, 이 경우에는 어차피 양 사이드만 검사를 수행하면 되기 때문에, i, i + 1 사이의 검사는 len(x)가 2 이상인 경우만 하고, 양 사이드 검사는 마지막에 해주면 될겁니다.

위의 분석을 토대로 문제를 풀어봅시다.

코드를 봅시다.

import sys

input = sys.stdin.readline

# 17266 어두운 굴다리
N, M = int(input()), int(input())
location_list = list(map(int, input().split()))
    
start, end = 1, N

while start <= end:
    mid = (start + end) // 2
    light_info_list = []
    is_not_possible = False
    
    # 불빛이 비춰지는 범위를 튜플로 저장
    for location in location_list:
        light_info_list.append((location - mid, location + mid))    
        
    if M > 1:
        for index in range(M - 1):
            light_end = light_info_list[index][1]
            light_next_start = light_info_list[index + 1][0]
            
            # 다음 가로등이 비춰지는 부분에서 음영이 발생시 True로 값 치환
            if light_next_start > light_end:
                is_not_possible = True
    
    # 양 끝을 탐색하여 음영지역이 발생하는지 파악
    if light_info_list[0][0] > 0 or light_info_list[M - 1][1] < N:
        is_not_possible = True
        
    if is_not_possible == True:
        start = mid + 1
    else:
        end = mid - 1
        
print(start)

윗 문단에서 많은걸 설명했으니, M > 1인 경우만 설명을 하겠습니다.

M > 1인 경우에는 i, i + 1 사이를 검색해야한다고 위에서 언급한 바 있습니다. 이 같은 경우는, i번째 가로등이 비추는 마지막 좌표와 i + 1번째 가로등이 비추는 첫 좌표를 비교하면됩니다.

만일 i번째 가로등이 비추는 마지막 좌표가 i + 1번째 가로등이 비추는 첫 좌표에 미치지 못하는 경우, 음영이 발생했다는 뜻입니다. 따라서 그런 경우에는 반복문을 바로 끝내고 start를 mid + 1로 맞춰서 높이 탐색 범위를 뒤로 보내버립니다.

위의 코드에는 for문에 break를 걸지 않았는데, 제 실수입니다.
is_not_possible이 True가 될 때 break를 해주면 더 작은 복잡도로 구현이 가능할겁니다!

그리고 마지막에는 start를 출력시켜서 문제를 해결합니다.