[코드트리] 개발자들의 거리두기 - 자바(Java)

문제

https://www.codetree.ai/training-field/search/problems/developers-keeping-distance?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

N명의 개발자들은 일직선상에 서있습니다. 그들 중 일부는 전염병에 감염되었고, 감염된 개발자는 양수 거리 R 이내에 있는 개발자들을 곧바로 감염시킵니다. 거리 R은 알 수 없는 상황에서, 처음에 감염된 개발자 수의 최솟값을 구하는 프로그램을 작성해 보세요.

 

입력 예시

6
7 1
1 1
15 1
3 1
10 0
6 1

 

출력 예시

3

 

 

코드

첫 번째 줄에는 정수 N이 주어집니다.

두 번째 줄부터는 N개의 줄에 걸쳐 한 줄에 하나씩 각 개발자의 위치와 감염 여부가 주어집니다.

감염 여부는 1 또는 0으로 표현되며, 1이 감염되었음을 뜻합니다. 모든 개발자의 위치는 다름을 가정해도 좋습니다.

• 1 ≤ N ≤ 1,000
• 0 ≤ 위치 ≤ 1,000,000

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[][] matrix = new int[n][2];
        StringTokenizer st;

        // 거리와 감염 여부를 담은 2차원 배열 초기화
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            matrix[i][0] = Integer.parseInt(st.nextToken());
            matrix[i][1] = Integer.parseInt(st.nextToken());
        }
        br.close();
        
        // 거리를 기준으로 오름차순 정렬
        Arrays.sort(matrix, Comparator.comparingInt(arr -> arr[0]));

        // 최소 감염 거리 R 구하기
        int r = Integer.MAX_VALUE;
        for (int i = 1; i < n - 1; i++) {
            // 현재 감염여부가 0이고 직전 감염여부가 1인 경우
            if (matrix[i][1] == 0 && matrix[i + 1][1] == 1) {
                r = Math.min(r, matrix[i + 1][0] - matrix[i][0]);
            }

            // 현재 감염여부가 0이고 다음 감염여부가 1인 경우
            if (matrix[i][1] == 0 && matrix[i - 1][1] == 1) {
                r = Math.min(r, matrix[i][0] - matrix[i - 1][0]);
            }
        }

        // 첫 감염자 위치와 인덱스 찾기
        int idx = 0;
        int beforeLocation = 0;
        for (int i = 0; i < n; i++) {
            if (matrix[i][1] == 1) {
                idx = i;
                beforeLocation = matrix[i][0];
                break;
            }
        }

        int count = 1;
        // 첫 감염자 다음 인덱스부터 순회
        for (int i = idx + 1; i < n; i++) {
            // 현재 사람이 감염자인 경우
            if (matrix[i][1] == 1) {
                // 직전 감염자와의 거리가 r보다 작은 경우 위치만 갱신
                if (matrix[i][0] - beforeLocation < r) {
                    beforeLocation = matrix[i][0];
                } else { // r보다 크거나 같은 경우 count 증가 및 위치 갱신
                    count++;
                    beforeLocation = matrix[i][0];
                }
            }
        }
        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
    }
}