[백준] 2230번: 수 고르기 (파이썬)

✅문제: 2230번

2230번: 수 고르기

📌개념정리

(1) 투 포인터(Two Pointers)

• 정의: 서로 다른 두 위치의 포인터를 동시에 조작하여 해결하는 알고리즘
• 주로 정렬된 배열에서 두 요소의 특정 관계를 만족시키는 문제에 사용함.

📌문제풀이

주어진 배열에서 두 수의 차가 M 이상이면서 가장 작은 경우를 찾는 문제임. 배열을 정렬한 후, 투 포인터 기법을 사용하여 두 수의 차이를 조절하며 최소 차이를 구함.

1. 주어진 수를 오름차순으로 정렬
2. left와 right를 0과 1로 초기화하여 두 수 사이의 차이를 탐색
3. right 포인터가 배열의 끝에 도달할 때까지 반복
4. 두 수의 차가 M 이상인 경우, 현재 차이를 최소 차이와 비교해 업데이트하고 left 포인터를 이동시킴
5. 두 수의 차가 M 미만인 경우, right 포인터를 이동시킴

n, m = map(int, input().split())
numbers = [int(input()) for _ in range(n)]
numbers.sort()

left, right = 0, 1	# left는 시작 위치, right는 두 번째 위치
min_diff = float('inf')	# 최소 차이

while right < n:
    current_diff = numbers[right] - numbers[left]	# 현재 두 포인터가 가리키는 값의 차이

    if current_diff >= m:
        min_diff = min(min_diff, current_diff)	# 차이가 m 이상이면 최소 차이 업데이트
        if left + 1 < right:
            left += 1	# left 포인터 오른쪽으로 이동
        else:
            right += 1	# left가 right 바로 앞에 있으면 둘 다 오른쪽으로 이동
            left += 1
    else:
        right += 1	# 차이가 m 미만이면 right 포인터를 오른쪽으로 이동(차이 증가)

print(min_diff)

코드를 실행한 과정은 다음과 같음. 예제 입력 1에는 3개의 숫자 (1, 5, 3)와 차이(3)이 주어짐.

# 예제 입력 1
3 3
1
5
3

1) 입력받은 숫자들을 오름차순으로 정렬함.

[1, 3, 5]

2) 투 포인터, 최소 차이 초기화

• left = 0
• right = 1
• min_diff = float('inf')

3) 순차적 탐색

Step	left	right	numbers[right] - numbers[left]	조건	결과	min_diff 업데이트	설명
1	0	1	2	< 3	False	-	차이가 3 미만이므로 right를 오른쪽으로 이동
2	0	2	4	>= 3	True	4	차이가 3 이상이고 현재 min_diff보다 작으므로 업데이트
3	1	2	2	< 3	False	-	left를 오른쪽으로 이동한 후 조건 미충족

최종적으로 min_diff의 값은 4가 됨.

# 예제 출력 1
4

📌후기

• 초기에 right 포인터와 left 포인터의 조건 설정하는 데 많이 고민했음. 몇 번 더 풀어보면 감을 잡을 수 있을 것 같음.
• 투 포인터 기법은 처음 공부했는데, 어떨 때 사용해야 하는지 이해할 수 있었음. 투 포인터 기법 외에도 이진 탐색, 슬라이딩 윈도우 같은 다른 탐색 기법을 학습하고, 적절한 문제에 효율적으로 적용할 수 있도록 노력해야겠음.

📌참고자료

1) 콜드펌킨, "투 포인터 (Two Pointer)", 2020.10.02, https://velog.io/@adorno10/투-포인터-Two-Pointer