[Algorithm] 2230. 수 고르기

2230: 수 고르기(투포인터)

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

• 문제 티어 : G4
• 풀이 여부 : Failed
• 소요 시간 : 38:10

정답 코드

# 투포인터 - worst case : O(N) + 정렬(O(NlogN) => O(NlogN)
import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
arr = sorted(int(input().rstrip()) for _ in range(N)) # O(NlogN)
ans = 10e9
left, right = 0, 1

while left <= right and right < N:
  diff = arr[right] - arr[left]

  if diff >= M:
    ans = min(ans, diff)
    left += 1
  else:
    right += 1
print(ans)

접근 방식

투포인터의 초기화를 left = 0, right = 1로 설정해준다.
left와 right를 인접하게 두어, 차이가 M 미만인 경우 right의 증가 처리를.
차이가 M 이상인 경우 left의 증가 처리를 해준다.
투포인터의 초기화를 위와 같이 해준 가장 큰 이유는 모든 가능한 조합을 탐색하기 위함이다.

이 때, 원래의 투포인터 문제와 달리 right가 1에서 시작해 증가하는 방식이므로, while문의 조건으로 right < N을 추가해 계산을 진행한다.

  if diff >= M:
    ans = min(ans, diff)
    left += 1
  else:
    right += 1

잘못된 접근 방식(+ 코드)

# 투포인터 : O(logN) ?? 맞나?
import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
arr = sorted(int(input().rstrip()) for _ in range(N)) # O(NlogN)
ans = 10e9

left, right = 0, len(arr)-1
while left <= right:
  diff = arr[right] - arr[left]
  if diff >= M: # 두 값의 차가 M 이상인 동시에, 차의 값 중 최대인 경우
    if diff < ans:
      ans = diff
    right -= 1
  if diff < M:
    left += 1

print(ans)

지금까지 풀어왔던 투포인터 방식으로 left와 right를 설정해줬더니
ex) N = 5, M = 3, A = [1, 2, 3, 4, 5]에 대해서 [(1, 5), (1, 4)]의 차만 구하게 되었다. ((2, 5) 누락)

즉 내가 설정한 투포인터의 방식은 "정렬된 배열에서 합이 특정 값이 되는 두 원소를 찾기"에 최적한 방법이지, 위 문제처럼 "두 수의 차이가 M 이상이면서 가장 작은 경우"에는 적합하지 않은 방법이었다.

배운점 또는 느낀점

투포인터의 left, right 설정을 아예 다른 방식으로 접근해본 문제라 되게 신선했다.
항상 left = 0, right = len(arr) - 1로 풀이해왔는데, 다양한 문제를 많이 접해봐야겠다고 생각하게 한 코드!