[코딩테스트 공부] 수 고르기

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

일단 문제를 어떻게 풀어야할지부터 생각을 해볼게요

위의 문제는 두 수의 차를 매번 계산을 해서, 차이가 M 이상이면서 가장 차이가 최소인 경우 그 차이를 출력하는게 문제의 요구사항입니다.

위의 문제는 아래와 같이 풀면 꽤 괜찮은 풀이가 되는데요, 제가 생각한 풀이는 아래와 같습니다.

• 일단 number_list를 sort 시킵니다.
• 일단 차이가 M 이상이 될 때까지 그 구간을 찾습니다. 차이가 M 이상이 되면 first를 유지시킨 상태에서 다음 수를 찾아봐야 차이만 벌어지기 때문에, 구간을 sliding 시키면 됩니다.

위의 방법대로 한 번 이 문제를 풀어보겠습니다.

코드를 봅시다

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
number_list = []

for _ in range(N):
    number_list.append(int(input()))
    
number_list.sort() # 정렬

start, end = 0, len(number_list) - 1
last = 0
minv = 2e9

while start <= end and last <= end:
    diff = number_list[last] - number_list[start]
    
    # diff가 M 미만인 경우 -> last를 키워서 다음의 diff를 기대한다
    if diff < M:
        last += 1
    
    # diff가 M 초과인 경우 -> minv를 업데이트하고 start를 키운다
    elif diff > M:
        minv = min(diff, minv)
        start += 1
    # diff가 M인 경우 -> minv를 업데이트하고 break
    else:
        minv = diff
        break
        
print(minv)

위 코드에서는 start, last 인덱스를 통해서 구간을 지정합니다.

이 문제에서는 경우의 수가 3가지가 있는데요, 그 경우의 수는 다음과 같습니다.

• diff가 M 미만인 경우 -> last를 키우게되면 다음의 수까지 읽어내기 때문에 다음의 diff에서 M 이상이 되기를 기대한다
• diff가 M인 경우 -> 더 이상 계산할 필요도 없다. while문을 탈출한다.
• diff가 M 초과인 경우 -> 일단은 minv를 갱신한다. 그리고 start를 키워서 다음의 diff의 크기를 줄여준다.

위의 방식을 이용해서 문제를 해결할 수 있습니다.