[백준 14746] Closest Pair (Python)

www.acmicpc.net/problem/14746

14746번: Closest Pair

 

문제풀이

N, M : 입력값

c1, c2 : 입력값 => 두 점의 X 좌표

P, Q : 입력 배열

left, right : 투 포인터 변수

ans : P, Q 원소 간 최소 거리

cnt : P, Q 원소 간 최소 거리일 때의 개수

 

정렬 후 투 포인터(Two Poiner)를 이용해 값을 비교해보면서 두 원소 간 최소 거리를 찾아내면 해결할 수 있다.

 

1. P, Q 집합 정렬하기

 

2. 투 포인터를 이용해 원소를 비교하여 두 원소 간 최소 거리를 찾는다.

- 정렬 후 P의 원소가 Q의 원소보다 크다면, Q에서 P의 원소보다 큰 원소가 나올때 까지 Q의 인덱스(right) 를 증가시키면서 서로 간 차이 비교 => 두 원소 차이의 절대값은 점점 감소하게 된다.

- Q의 원소가 P보다 크다면 서로 간 차이 비교 후 left 증가

- P나 Q의 마지막 원소에 도달할때까지 반복

 

3. 한번 더 투 포인터를 진행하면서 2번 과정에서 찾은 최소 거리를 가진 쌍의 개수를 세준다.

 

4. 2번 과정에서 찾은 최소 거리에 입력값 c1과 c2의 차이의 절대값을 더하여서 최소거리 쌍과 함께 출력한다. (출력 조건)

  

코드

import sys

# 음수 - 음수 : 절대값 감소
# 음수 - 양수 : 절대값 증가
# 양수 - 양수 : 절대값 감소
# 양수 - 음수 : 절대값 증가

if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    c1, c2 = map(int, sys.stdin.readline().split())
    P = list(map(int, sys.stdin.readline().split()))
    Q = list(map(int, sys.stdin.readline().split()))
    P.sort(); Q.sort() # 투 포인터를 위해 정렬

    right = 0
    ans = sys.maxsize
    cnt = 0

    # c1, c2는 고정되어 있기 때문에 P와 Q 안에 있는 원소만 비교하면 된다.
    # P, Q 원소 사이 가장 가까운 거리 찾기
    for left in range(N):
        # P의 원소가 더 클 경우 right 를 증가시키면서 Q의 원소와의 차이 비교
        while right < M and P[left] >= Q[right]:
            ans = min(ans, abs(P[left] - Q[right]))
            right += 1
        # Q의 원소가 더 클 경우 left 를 증가
        if right < M and P[left] < Q[right]:
            ans = min(ans, abs(P[left] - Q[right]))
    right = 0 # right 초기화
    # P, Q 원소 사이 가장 가까운 거리를 가진 좌표의 개수 세기
    for left in range(N):
        # 투 포인터를 이용해 P, Q 원소 비교
        while right < M and P[left] >= Q[right]:
            # 가장 가까운 거리일 경우 개수 증가
            cnt += 1 if ans == abs(P[left] - Q[right]) else 0
            right += 1
        if right < M and P[left] < Q[right]:
            cnt += 1 if ans == abs(P[left] - Q[right]) else 0
    print(ans + abs(c1 - c2), cnt)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!