[Do-it! 코딩 테스트-기초편] 010. 최소값 찾기 1 - 시간초과

문제

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

11003번: 최솟값 찾기

---

접근

데이터 크기: 5,000,000

시간 제한: 2.4초

 

O(N^2) 무조건 시간 초과.

O(NlogN)도 나오면 안됨.

O(N)으로 해결 가능?

 

슬라이딩 윈도우 사용

윈도우의 크기는 L로 고정되어있지만 위도우 크기보다 작은 범위를 탐색하는 경우를 고려해야함.

---

코드

import sys

N, L = map(int, sys.stdin.readline().split(' '))
A = list(map(int, sys.stdin.readline().split(' ')))
D = []

window_start = 0  # window_start 가 (L - 1)이 되기 전 까지의 window 는 0 ~ start
window_end = L - 1
index = 0

if L == 1:
    for i in range(N):
        print(A[i], end=' ')
else:
    for i in range(N):  # N이 12면 end 11까지
        if window_start < L:  # L이 3이면 window_start 가 0, 1, 2 일 때
            start = 0
            end = window_start
        else:
            start = window_start - (L - 1)
            end = window_end - (L - 1)
            
        print(min(A[start:end + 1]), end=' ')
        window_start += 1
        window_end += 1

---

설명 & 피드백

우선 시간 제한을 해결하지 못했다.

단순하게 윈도우를 슬라이딩 하며 각 구간의 최소값을 구하는 알고리즘을 작성했다.

하지만 반복문 안에 파이썬 내장함수 min()을 사용하면서 시간 복잡도가 O(N^2)을 초과하게 되어 시간이 초과되었다.

 

이 문제를 해결하기 위해 min() 함수를 사용하지 않고 최소값을 구하는 방법을 생각해보았지만 찾지 못했다.

 

ChatGPT의 힘을 빌려 heapq 모듈을 사용해 최소값을 구하는 코드를 제출했더니 '틀렸습니다'를 보게 되었다..

결국 시간 초과 문제가 아닌 코드 자체가 오답이었다.

 

결론: 미해결로 남기고 추후 다시 글을 작성해보겠다..

import sys
import heapq

def find_min(input_list):
    if not input_list:
        return None  # 빈 리스트에 대한 예외 처리
    min_value = heapq.heappop(input_list)  # 입력 리스트를 최소 힙으로 변환하고 최소값을 추출
    return min_value

N, L = map(int, sys.stdin.readline().split(' '))
A = list(map(int, sys.stdin.readline().split(' ')))
D = []

window_start = 0  # window_start 가 (L - 1)이 되기 전 까지의 window 는 0 ~ start
window_end = L - 1
index = 0

if L == 1:
    for i in range(N):
        print(A[i], end=' ')
else:
    for i in range(N):  # N이 12면 end 11까지
        if window_start < L:  # L이 3이면 window_start 가 0, 1, 2 일 때
            start = 0
            end = window_start
        else:
            start = window_start - (L - 1)
            end = window_end - (L - 1)
            
        print(find_min(A[start:end + 1]), end=' ')
        window_start += 1
        window_end += 1