https://www.acmicpc.net/problem/2230
2230번: 수 고르기
N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어
www.acmicpc.net
처음에 정렬로만 풀었다가 시간초과가 났다.
이후 두 수를 고른다는 조건을 파악하여 투 포인터로 풀었다.
위 문제들이랑 결이 비슷해서 어렵지 않게 풀 수 있었다.
- 입력받은 숫자들을 빈 배열에 추가해 준다.
- 배열을 정렬한다.
- 인덱스를 늘리며 두 수의 차를 구한다.
- 두 수의 차가 m 미만인 경우, right 인덱스에 1을 더하여 더 큰 차이가 나도록 만든다.
- 두 수의 차가 m 이상인 경우, 현재 m 이상인 최소의 차와 비교한다.
- 결과를 출력한다.
정답 코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
arr = []
for idx in range(n):
arr.append(int(input()))
arr.sort()
answer = sys.maxsize
left = right = 0
while left <= right and right < n:
diff = arr[right] - arr[left]
if diff < m:
right += 1
else:
left += 1
answer = min(diff, answer)
print(answer)
'PS > 백준' 카테고리의 다른 글
[백준] 2251번 물통 (python) (1) | 2023.12.03 |
---|---|
[백준] 13904번 과제 (python) (0) | 2023.11.05 |
[백준] 1253번 좋다 (python) (0) | 2023.10.18 |
[백준] 11660번 구간 합 구하기 5 (Python) (0) | 2023.10.16 |
[백준] 4195번 친구 네트워크 (Python) (0) | 2023.08.31 |