[알고리즘/투 포인터] 2230번 : 수 고르기 - python

링크 : https://www.acmicpc.net/problem/2230

2230번: 수 고르기

 

---

• 문제
• 소요시간: 28분 7초

---

• 설계하기(접근방법) 

1. 입력받기

숫자를 입력받는다

 

2. 구현하기

투 포인터를 사용하기 위해서 먼저 리스트를 정렬한다

 

처음 시작 지점을 리스트의 인덕스

 

p1 = 0번 인덱스

p2 = 1번 인덱스로 지정한다

 

먼저 p2 -p1이 m 이상인 경우

그 뒤의 p2는 증가시켜줄 필요가 없다

p2가 커질 수록 둘의 차이가 커지기 때문에

현재 p1에서는 p2의 값이 최소값이다

 

따라서 p1의 위치를 p1 + 1로 갱신시켜준다

만약 p1과 p2가 같다면 p2 = p1 + 1로 갱신시켜준다

 

그 후 이 두 개의 포인터를 옮기면서 연산을 수행할 것인데,

 

문제에서 알 수 있는 점은 m 이상의 차이 중에서 최소를 구한다고 했으니

최소값 m이 나타나는 경우 즉시 break해도 된다(종료조건)

 

그리고 우리는 리스트를 정렬해 놓았다

즉 p2의 인덱스 넘버가 끝 list[-1]까지 갔다면

 

p1, p2가 list[-2] list[-1] 즉 리스트를 모두 순회 한 경우(역시 종료조건)

or m 이상의 차이가 나타나지 않아서 p2의 값이 갱신이 안되었다면

 

다음 p1 부터는 이전의 p1보다 숫자가 커지기 때문에

차이가 줄어든다. 즉 m 이상의 차이를 리스트에서 더 이상 구할 수 없다는 의미이니

break를 해주면 된다

 

 

3. 출력하기

나타난 m 이상의 최소값을 구한다

 

---

• 코드(출력)

import sys

input = sys.stdin.readline

n , m = map(int, input().split())

n_list = []

for i in range(n):
    n_list.append(int(input()))

n_list.sort()


min_diff = 10e9
p1 = 0
p2 = 1
while p2 < n:
    diff = n_list[p2] - n_list[p1]
    if diff >= m :
        if diff < min_diff:
            min_diff = diff
        p1 += 1
        if p1 == p2:
            p2 = p1 + 1
    else:
        p2 += 1
    if min_diff == m :
        break


print(min_diff)

---

• 얻어갈 부분

1. 투 포인터의 기본적인 개념을 익혔다. 종료조건을 잘 찾아내자