Baekjoon 32069. 가로등 / Python

문제 링크

 

문제 설명

수직선 도로 위에 여러 개의 가로등이 위치하고 있습니다.
각 위치의 어두운 정도를 그 위치로부터 가장 가까운 가로등까지의 거리로 정의합니다.
제일 밝은 곳부터 어두운 정도를 k개 출력하는 문제

코드 설명

1. 가로등이 k보다 많으면 0을 k번 출력하고 종료
2. 가로등에 대해서, 거리를 1씩 늘려가면서 가로등과의 거리 계산

import sys; input = sys.stdin.readline

l, n, k = map(int, input().split())
arr = list(map(int, input().split()))

# 만약 가로등의 개수가 k 이상이면, 어두운 정도는 항상 0이 최소 k개 이상이다.
if n >= k:
    # 모든 어두운 정도는 0이기 때문에 0을 k번 출력하고 종료
    print('0\n' * k)
    exit()

# 가로등의 개수가 k 미만이면, n개의 어두운 정도는 0이다. 이를 제외한 나머지 어두운 정도 값을 구해야 한다.
k -= n
# 가로등 위치에서 0의 어두운 정도를 출력
print('0\n' * n, end='')

# 초기 거리 1
dist = 1

while True:
    dist_str = str(dist)  # 거리 값 문자열 변환 (출력용)
    
    # 모든 가로등에 대해
    for tmp in range(n):
        # 첫 번째 가로등이거나, 이전 가로등과 현재 가로등 사이의 거리 체크
        if (not tmp and arr[tmp] >= dist) or (tmp and arr[tmp] > arr[tmp - 1] + 2 * dist - 1):
            # 현재 거리 값 출력
            print(dist_str)
            k -= 1  # 출력할 어두운 정도 개수 감소
        if not k:
            exit()  # k개 모두 출력했으면 종료

        # 마지막 가로등이거나, 다음 가로등과 현재 가로등 사이의 거리 체크
        if (tmp == n - 1 and arr[tmp] <= l - dist) or (tmp != n - 1 and arr[tmp] < arr[tmp + 1] - 2 * dist):
            print(dist_str)
            k -= 1  # 출력할 어두운 정도 개수 감소
        if not k:
            exit()  # k개 모두 출력했으면 종료
            
    dist += 1  # 거리 증가

 

시간복잡도를 O(N * K) 로 맞추는 것이 어려운 문제