[코드트리/NOVICE MID] 악수와 전염병의 상관관계 2 (JAVA)

🔺 문제

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

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
class Person implements Comparable<Person> {
    int t, x, y;
 
    public Person(int t, int x, int y) {
        this.t = t;
        this.x = x;
        this.y = y;
    }
 
    // 시간 기준 오름차순 정렬
    @Override
    public int compareTo(Person p) {
        return this.t - p.t;
    }
}
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());
 
        Person[] people = new Person[T];        
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int t = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
 
            people[i] = new Person(t, x, y);
        }
        Arrays.sort(people);
 
 
        int[] answer = new int[N + 1]; // 전염병 여부 배열
        answer[P] = 1;
 
        int[] tmp = new int[N + 1];    // 남은 감염시키는 횟수 배열
        Arrays.fill(tmp, K);       
 
        for (int i = 0; i < T; i++) {
            int nx = people[i].x;
            int ny = people[i].y;
 
            if (answer[nx] == 1 && answer[ny] != 1 && tmp[nx] > 0) {    // 둘 중 한 명만 감염자인 경우 1
                answer[nx] = 1;
                answer[ny] = 1;
                tmp[nx]--;
            }
            else if(answer[ny] == 1 && answer[nx] != 1  && tmp[ny] > 0) {    // 둘 중 한 명만 감염자인 경우 2
                answer[nx] = 1;
                answer[ny] = 1;
                tmp[ny]--;
            }
            else if(answer[nx] == 1 && answer[ny] == 1) {    // 둘다 감염자여도, 감염시키는 횟수 감소
                tmp[nx]--;
                tmp[ny]--;
            }
        }
 
        // 출력하기
        for (int i = 1; i <= N; i++) {
            System.out.print(answer[i]);
        }
    }
}
 

 

 

 

🧩  해결 아이디어

• 배열 기록

- 입력 받은 배열을 오름차순 시간 순으로 정렬한다.

@Override
public int compareTo(Person p) {
    return this.t - p.t;
}

 

 

- 각 인원마다 남을 감염시킬 수 있는 횟수를 저장할 1차원 배열을 만든다.

int[] tmp = new int[N + 1];    // 남은 감염시키는 횟수 배열
Arrays.fill(tmp, K);

 

 

- T번 돌면서, 둘 중 한 명만 감염자인 경우는 비감염자를 감염시키고, 감염시킨 사람의 감염시킬 수 있는 횟수에서 1 뺀다.

if (answer[nx] == 1 && answer[ny] != 1 && tmp[nx] > 0) {    // 둘 중 한 명만 감염자인 경우 1
    answer[nx] = 1;
    answer[ny] = 1;
    tmp[nx]--;
}
else if(answer[ny] == 1 && answer[nx] != 1  && tmp[ny] > 0) {    // 둘 중 한 명만 감염자인 경우 2
    answer[nx] = 1;
    answer[ny] = 1;
    tmp[ny]--;
}

 

 

- 둘다 감염자여도, 둘 모두에서 감염시킬 수 있는 횟수를 1씩 뺀다.

else if(answer[nx] == 1 && answer[ny] == 1) {    // 둘다 감염자여도, 감염시키는 횟수 감소
    tmp[nx]--;
    tmp[ny]--;
}

 

 

 

---

🔺 다른 풀이들

- 악수 횟수 세는 int형 배열과, 감염 여부 나타내는 boolean형 배열을 생성한다.

- 감염되어 있을 경우, 악수 횟수를 증가시킨다.

감염되어 있고 악수 횟수가 K번 이하라면, 상대방에 전염시킨다.

import java.util.Scanner;
import java.util.Arrays;
 
class Shake implements Comparable<Shake> {
    int t;
    int x;
    int y;
    
    public Shake(int t, int x, int t) {
        this.t = t;
        this.x = x;
        this.y = y;
    }
 
    // 시간 순 오름차순 정렬
    @Override
    public int compareTo(Shake shake) {
        return t- shake.t;
    }
};
 
public class Main {
    public static final int MAX_T = 250;
    public static final int MAX_N = 100;
    
    public static int n, k, p, t;
    public static int[] shakeNum = new int[MAX_N + 1];            // 악수 횟수 카운트 배열
    public static boolean[] infected = new boolean[MAX_N + 1];    // 감염 여부 배열
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        p = sc.nextInt();
        t = sc.nextInt();
 
        infected[p] = true;    // 감염자 감염 처리
        
        Shake[] shakes = new Shake[MAX_T];
        for(int i = 0; i < t; i++) {
            int time = sc.nextInt();
            int person1 = sc.nextInt();
            int person2 = sc.nextInt();
 
            shakes[i] = new Shake(time, person1, person2);
        }
        Arrays.sort(shakes, 0, t);    // custom comparator
        
        // 각 악수 횟수 세서, K번 초과 시 전염 X
        for(int i = 0; i < t; i++) {
            int target1 = shakes[i].x;
            int target2 = shakes[i].y;
            
            // 감염되어 있을 경우, 악수 횟수 증가시킴
            if(infected[target1])    shakeNum[target1]++;
            if(infected[target2])    shakeNum[target2]++;
            
            // target1이 감염되어 있고 아직 K번 이하로 악수했다면 target2 전염시킴
            if(shakeNum[target1] <= k && infected[target1])    infected[target2] = true;
            
            // target2가 감염되어 있고 아직 K번 이하로 악수했다면 target1 전염시킴
            if(shakeNum[target2] <= k && infected[target2])    infected[target1] = true;
        }
        
        // 출력
        for(int i = 1; i <= n; i++) {
            System.out.print(infected[i] ? 1 : 0);
        }
        
    }
}

 

 

---

💬 느낀 점

풀고 나니 간단한데 왜 이리 시간이 오래 걸릴까.....

테스트케이스 찾는 것도 쉽지 않구나....

다른 분들 테스트케이스 보고 틀린 부분 찾음...ㅠ

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 배열 기록