백준 문제 풀이 - 수 고르기 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)
🤔 회고
정렬과 투 포인터를 활용하면 부분합 문제가 아니더라도 활용할 수 있다는 걸 깨달은 문제였다.
Author And Source
이 문제에 관하여(백준 문제 풀이 - 수 고르기 2230번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@delicate1290/백준-문제-풀이-수-고르기-2230번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)