문제 - 일렬 연결망
Source
Google Keep/문제 - 일렬 연결망.md
Summary
좌우 일렬로 배치된 N개 컴퓨터(0/1 타입)의 네트워크 연결 문제입니다. 타입 1 컴퓨터는 좌측에 있는 타입 0 컴퓨터 중, 사이에 최대 4개의 타입 0이 존재하는(즉, 인접한 0 포함 최대 5개 이내) 대상들과 직접 연결됩니다. 이 규칙에 따라 필요한 총 케이블 길이와 최종적으로 형성되는 클러스터(연결 요소)의 수를 계산해야 합니다. N이 최대 200,000 이므로 O(N^2) 접근이 필요하며, 타입 0을 기준으로 우측의 타입 1을 탐색하며 연결 관계를 갱신하는 알고리즘이 제시되어 있습니다.
Key Points
- 입력: N개 컴퓨터의 타입 배열 (0 또는 1)
- 연결 규칙: 타입 1은 좌측의 타입 0 중, 사이에 최대 4개의 타입 0이 있는 대상과 연결
- 출력: 총 케이블 길이, 클러스터 수
- 제약: N <= 200,000, 시간 제한 1초
- 알고리즘: 타입 0을 기준으로 우측을 탐색하며 연결 및 클러스터 병합 수행 (Union-Find 유사 로직)