[BOJ] 2230번 수 고르기 (Python)

Kyeongmin·2023년 7월 24일
0

알고리즘

목록 보기
22/24

📃 문제

[BOJ] 수 고르기 🔗링크

투 포인터라는 개념을 공부하고, 익힐 겸 풀어본 문제이다.


🧠❓ 문제 접근 및 풀이

🐶 1번째 접근

완전탐색 O(n2)O(n^2) 으로 모든 수의 조합을 확인해서도 풀 수 있는 문제이지만,
투 포인터 개념을 이용하면 O(n)O(n) 으로 풀 수 있는 문제다.

수열 NN을 오름차순으로 정렬한 뒤, 2개 수의 차이 gg를 구해 MM과 비교한다면
아래 3가지 경우의 수가 나오게 된다.

각 경우의 수마다 아래와 같은 동작을 하면,
모든 숫자의 조합을 확인하지 않고 O(n)O(n) 으로 문제를 풀 수 있다.

g<Mg < M : gg 를 증가시키기 위해 2번째 수를 더 큰 수로 사용한다.
g>Mg > M : gg 를 감소시키기 위해 1번째 수를 더 큰 수로 사용한다.
g=Mg = M : 문제에서 요구하는 가장 작은 차이이기 때문에 탐색을 종료한다.

import sys
input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())
    A = sorted(list({int(input()) for _ in range(N)}))
    len_A = len(A)

    ans, st, en = float('inf'), 0, 0
    while st < len_A and en < len_A:
        g = A[en] - A[st]
        if g < M:
            en += 1
        else:
            if g == M:  return g
            st += 1
            ans = min(ans, g)
    return ans
print(solve())

profile
개발자가 되고 싶은 공장장이🛠

0개의 댓글