백준 알고리즘 문제 풀이 가이드: 코딩 면접 대비 완벽 준비-22942 데이터 체커 편 (python)

문제 살펴보기!!

문제 링크 : https://www.acmicpc.net/problem/22942

반응형

솔루션 살펴보기!!

import sys

def main():
    N = int(sys.stdin.readline())  # 원의 개수 입력
    events = []  # 각 원의 시작점과 끝점을 저장할 리스트

    # 원의 시작점과 끝점을 기록
    for i in range(N):
        x, r = map(int, sys.stdin.readline().split())
        events.append((x - r, i))  # 시작점
        events.append((x + r, i))  # 끝점

    # 시작점과 끝점을 x 좌표 기준으로 정렬
    events.sort()

    active_stack = []  # 현재 활성화된 원들을 관리할 스택

    # 모든 이벤트 처리
    for event in events:
        position, circle_id = event
        
        if active_stack:
            last_position, last_circle_id = active_stack[-1]

            if last_circle_id == circle_id:
                # 같은 원의 시작과 끝을 만나면 스택에서 제거
                active_stack.pop()
            else:
                # 새로운 원의 이벤트를 스택에 추가
                active_stack.append(event)
        else:
            # 스택이 비어있으면 현재 이벤트를 추가
            active_stack.append(event)

    # 스택이 비어있으면 모든 원이 유효함, 그렇지 않으면 겹침 발생
    if active_stack:
        print('NO')
    else:
        print('YES')

if __name__ == "__main__":
    main()

코드 흐름 및 풀이 전략!!

이 코드는 주어진 NNN개의 원들이 서로 겹치지 않는지 확인하는 문제를 해결하는 방식으로 작성되었습니다. 각 원은 xxx축 상의 중심 좌표 xxx와 반지름 rrr을 가지고 있으며, 원들의 교점 여부를 확인하는 것이 목표입니다. 이 코드는 스윕 라인 알고리즘을 사용하여 겹치는 원이 있는지 효율적으로 검사합니다.

풀이 전략

1. 이벤트 리스트 구성:
   • 각 원의 시작점과 끝점을 구하고, 이를 이벤트로 처리합니다.
   • 시작점은 x - r로, 끝점은 x + r로 계산됩니다.
   • 이 두 개의 이벤트를 리스트에 (position, circle_id) 형태로 저장합니다. 여기서 position은 좌표값, circle_id는 원을 구별하는 인덱스입니다.
2. 이벤트 정렬:
   • 이벤트 리스트는 position을 기준으로 오름차순으로 정렬됩니다. 이렇게 하면 각 원의 시작점과 끝점을 순차적으로 처리할 수 있습니다.
3. 스택을 사용한 원의 관리:
   • 정렬된 이벤트를 처리하면서, 원의 시작과 끝을 스택에 쌓고 제거하는 방식으로 교차 여부를 판단합니다.
   • 스택은 현재 활성화된 원들의 끝점을 추적합니다.
     • 시작점이 나오면 스택에 추가하고,
     • 동일한 원의 끝점을 만나면 스택에서 해당 원을 제거합니다.
   • 만약 새로운 시작점이 스택에 있는 다른 원의 끝점 사이에 끼면, 이는 원들이 겹친다는 의미입니다.
4. 교차 여부 판단:
   • 이벤트를 순차적으로 처리하며, 만약 같은 원의 시작점과 끝점이 만나면 스택에서 해당 원을 제거합니다.
   • 끝까지 스택이 비어있으면 모든 원이 겹치지 않는 것이므로 "YES"를 출력합니다. 반대로, 스택이 비어있지 않다면 원이 교차했음을 의미하므로 "NO"를 출력합니다.

728x90

주요 개념

1. 이벤트 기반 스윕 라인 알고리즘:
   • 스윕 라인 알고리즘은 각 원의 시작점과 끝점을 시간 축 또는 공간 축 상에서 하나의 이벤트로 취급해 순차적으로 처리하는 방식입니다.
   • 이 문제에서 스윕 라인은 각 원의 시작점과 끝점을 순차적으로 처리하면서 현재 활성화된 원들의 범위를 관리합니다. 이를 통해 원들이 서로 교차하는지 효율적으로 확인할 수 있습니다.
2. 스택:
   • 스택은 현재 처리 중인 원의 정보를 관리하는 데 사용됩니다.
   • 시작점을 만나면 스택에 쌓고, 동일한 원의 끝점을 만나면 스택에서 제거하는 방식으로 원들의 활성화 상태를 추적합니다. 이를 통해 원이 교차하는지 간단하게 확인할 수 있습니다.
3. 정렬:
   • 원의 시작점과 끝점을 먼저 좌표값 기준으로 정렬하는 것이 중요합니다. 이를 통해 원의 시작점이 언제 나오고 끝점이 언제 나오는지를 순차적으로 처리할 수 있습니다.
   • 정렬된 상태에서 스택을 사용해 교차 여부를 확인하면 시간 복잡도를 효율적으로 유지할 수 있습니다.

시간 복잡도

• 정렬: 2N개의 이벤트를 O(Nlog⁡N)의 시간 복잡도로 정렬합니다.
• 스윕 라인 처리: 모든 이벤트를 한 번 순회하면서 스택에 추가하거나 제거하는 과정이 있으므로 O(N)의 시간이 소요됩니다.

따라서 전체 시간 복잡도는 O(Nlog⁡N)로, 주어진 N의 최대값인 200,000에 대해 제한 시간 1초 내에 해결할 수 있습니다.