악곱 == 악성곱슬

정렬, 두 포인터

---

해당 문제는 입력의 개수가 10만개 이므로 O(N^2) 알고리즘을 사용할 경우 시간초과가 난다. 따라서 O(NlogN)이하 알고리즘을 사용해야겠다고 판단.

O(NlogN) 중 어떤 알고리즘을 사용하는게 좋을지 고민해보았다. 10만개의 데이터를 순회하며 해당 데이터 +-m을 타겟으로 하여 이진 탐색을 해서 풀어도 좋을 것 같아서 시도를 해보았으나 구현의 까다로움이 있어 다른 방법을 모색해보았다.

이진 탐색을 하기위해 앞서 데이터를 정렬했는데, 정렬하고 보니 head, tail 두 개의 포인터를 사용하여 두 데이터의 차이를 계속 비교하며 10만의 데이터를 2번 순회하도록 구현할 수 있다는 것을 깨달았고 코드는 아래와 같다.

import sys

def solution(numbers, n, m):
    _min = 2000000001
    numbers.sort()
    head, tail = 0, 0
    while True:
        tmp = numbers[head] - numbers[tail]
        if tmp == m:    # m이랑 똑같은 경우는 stop
            _min = tmp
            break
        if tmp < m:     # 만약 기준 미달이면 헤드 이동
            if head == n-1:     # head 가 끝인데 기준미달이면 종료
                break
            head += 1
        elif tmp > m:   # 기준에 부합하는 경우
            if tmp < _min:      # 기존 최소값보다 작은 경우
                _min = tmp
            tail += 1

    return _min

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().rstrip().split())
    A = [0] * N
    for i in range(N):
        A[i] = int(sys.stdin.readline().rstrip())
    print(solution(A, N, M))