백준 2230번 <수 고르기>

백준 알고리즘 2230번

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

2230번: 수 고르기

---

2230번

N개의 정수로 이루어진 수열이 있을 때, 이 수열에서 두 수를 골라서 그 차이가 M 이상이면서 제일 작은 경우를 구하여라. (고른 두 수가 같은 수일 수 있다.)

 

입력으로 첫 줄에 정수의 개수 N과 M이 주어지고 그 다음 N개의 줄에 걸쳐 수열을 이루는 정수가 들어온다.

 

출력으로 M 이상이면서 가장 작은 차이르르 출력한다.

---

문제 해결

수열을 정렬한 후 투 포인터로 차이를 구해 문제를 해결한다.

 

start는 for문을 돌려서 0부터 시작하여 N-1까지 간다.

end 또한 0부터 시작하는데 이는 start 인덱스의 숫자 값과 end 인덱스의 숫자 값의 차이에 따라 변한다.

1. 만약 start와 end가 같으면 end에 1을 더한다. 
2. end < N보다 작고 start 인덱스의 숫자 값과 end 인덱스의 숫자 값의 차이가 M보다 작다면 end에 1을 더한다.
3. end가 N이라면 더 이상 M 이상의 차이를 가질 수 있지 않기 때문에 for문을 멈춘다.
4. 현재 저장되어있는 answer 값과 start 인덱스의 숫자 값과 end 인덱스의 숫자 값의 차이를 비교하여 더 작은 값을 answer 값으로 업데이트 한다.
5. 만약 answer의 값이 N이라면 더 작은 값이 나올 수 없기 때문에 for문을 멈춘다.

---

코드

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
num = [int(input()) for _ in range(N)]
num = sorted(num)
answer = sys.maxsize

end = 0
for start in range(N):
    if start == end:
        end += 1
    while(end < N and num[end] - num[start] < M):
        end+=1
    if end == N:
        break
    answer = min(answer, num[end]-num[start])
    if answer == M:
        break
print(answer)

---

결과

---

answer의 초기 값을 int(1e9)로 하면 틀렸습니다가 뜬다...

그래서 sys.maxsize로 해야 할 수 있다.