백준 문제 풀이 - 수 고르기 2230번

📜 문제 이해하기

N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.
예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.

💡 문제 재정의

M 이상이면서 가장 작은 차이를 출력하라.

✏️ 계획 수립

• 먼저 들어온 입력들을 정렬한다. 정렬하는 이유는 투 포인터를 사용하기 위해서는 정렬된 데이터를 사용해야 하기 때문이다.

• 정렬이 되면 투 포인터를 사용해서 start 인덱스와 end 인덱스의 합이 M 이상이 되는지 확인하고 M 이상이라면 start를 늘려주고 가장 작은 차인지를 확인한 뒤 min difference를 갱신한다. 만약 M 미만이라면 end를 늘려줘서 다음 입력과의 합을 구한다. 위 과정을 start와 end가 모두 N이 될 때까지 반복하면 된다.

• 이 때 항상 start와 end간의 인덱스 차이가 넓어질수록 값의 차이가 커지고 인덱스 차이가 좁아질수록 값의 차이가 작아지기 때문에 투 포인터를 사용할 수 있기 때문에 정렬을 한다.

💻 계획 수행

import sys

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    nums = []
    min_difference = float("inf")
    for i in range(N):
        nums.append(int(sys.stdin.readline().rstrip()))

    nums.sort()
    start = 0
    end = 1

    while start < end:
        difference = nums[end] - nums[start]
        if difference >= M:
            if min_difference > difference:
                min_difference = difference
            start += 1
            if start == end and end != N - 1:
                end += 1
        else:
            if end == N - 1:
                start += 1
            else:
                end += 1

    print(min_difference)

🤔 회고

정렬과 투 포인터를 활용하면 부분합 문제가 아니더라도 활용할 수 있다는 걸 깨달은 문제였다.