투 포인터 문제집 : https://www.acmicpc.net/workbook/view/8709
문제: https://www.acmicpc.net/problem/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 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.
제한
- 1 ≤ N ≤ 100,000
- 0 ≤ M ≤ 2,000,000,000
- 0 ≤ |A[i]| ≤ 1,000,000,000
예제 출력 1
4
문제 요약
목표: M 이상이면서 가장 작은 차이를 출력한다.
- [1, 5, 3] 에서 두 숫자를 골라 차이를 구하는 모든 경우의 수는 다음과 같다.
- (1, 5) : 5 - 1 = 4
- (1, 3) : 3 - 1 = 2
- (5, 3) : 5 - 3 = 2
- (1, 1), (3, 3), (5, 5) : 0
- 이 중 문제 예시에서 주어진 M = 3이상이면서, 차이가 가장 작은 경우는 4이다.
- 이렇게 주어진 수열에서 구할 수 있는 M 이상의 차이 값 중 최소값을 구해 출력하면 된다.
우선 정렬을 해야한다.
예시
A = [5, 3, 9, 10, 1]
M = 3
정렬을 안했을 때
5를 기준으로 나머지 값들과 비교해가면서 차이를 구한다고 했을 때
- 5 - 5 = 0
- 5 - 3 = 2
- 5 - 9 = -4
- 5 - 12 = -7
- 5 - 1 = 4
이렇게 나오는 값이 뒤죽 박죽이라 모든 경우의 수를 탐색해야하고 O(N^2)의 탐색을 거쳐야 한다.
또한 결과가 양수일지 음수일지 알 수 없어 abs()를 씌워줘야 한다.
정렬을 했을 때
수열을 정렬한다면 [1, 3, 5, 9, 12]의 형태가 되는데, 1을 고정하고 나머지 수와 차이를 구할 때
- 1 - 1 = 0
- 3 - 1 = 2
- 5 - 1 = 4 -> 4 저장
여기까지만 계산하면 된다.
왜냐하면 이미 주어진 M = 3보다 차이가 커진 상황이고, 배열이 오름차순 정렬되어있기 때문에 뒤의 수를 탐색해 봤자 차이가 더 커질 것이기 때문이다.
현재 찾은 'M보다 큰 최소값'인 4를 저장하고 다음 순서로 넘어간다.
'1' 다음 위치인 '3'에서 마지막 탐색시점부터 탐색하면 된다.
6이 M보다 크기 때문에 더 이상 확인할 필요 없이 다음 순서로 넘어간다.
이 때, 기존에 저장된 정답인 4보다 작다면 갱신해주는 절차가 필요하다.
def solution(A, N, M):
A.sort() # 수열을 오름차순으로 정렬
left = 0
right = 1
answer = float('inf') # 가장 작은 차이를 무한대로 초기화
while right < N:
diff = A[right] - A[left]
if diff > M:
answer = min(answer , diff)
left += 1 # 차이가 M 이상이면 더 작은 차이를 찾기 위해 left를 오른쪽으로 이동
elif diff < M:
right += 1 # 차이가 M 미만이면 right를 더 오른쪽으로 이동하여 차이를 키움
else: # diff == M 가장 이상적 더 이상 할 필요도 없다.
return M
return answer
if __name__ == "__main__":
N, M = map(int, input().split())
A = [int(input()) for _ in range(N)]
# 답변 구하기
answer = solution(A, N, M)
print(answer)
간단하게 생각해보는거다.
1. 정렬을 하고
2. 왼쪽 화살표, 오른쪽 화살표 만들고
3. 오른쪽 화살표가 범위 N을 넘어가기 전까지 진행해본다.
4.1. 각 화살표가 가르키는 수의 차이가 목표 값 M보다 크면 기존 저장된 최소 차 diff랑 비교해서 갱신
4.2 차이가 목표 값 M보다 작으면 조건 만족 안되므로 오른쪽 화살표 오른쪽으로 한칸 이동
4.3 만약 차이가 딱 목표값인 M이 있으면 더 볼 필요도 없이 M을 출력하면 된다.
목표: M 이상이면서 가장 작은 차이를 출력한다.
