BEAKJOON / 백준 - JAVA 29732번 Rick-Roll Virus

2024.09.30기준 - 브론즈1

728x90

백준, BEAKJOON, BOJ, JAVA, 자바

 

🟥 풀이

이 문제는 Rick-Roll Virus에 감염될 때, 하루가 지났을 때, 전부 치료할 수 있다면 Yes 아니라면 No를 출력하는 문제입니다.

 

문제 접근

1. 딱 하루만 비교를 하면되기 때문에 입력 받은 감염된 사람들의 인덱스를 따로 저장을 해주었습니다.
2. 저장된 인덱스에서 감염되는 범위만큼 전부 감염을 처리합니다.
3. 전체 감염된 인원수와 치료제의 수를 비교해 Yes or No를 출력합니다.

1. 입력받은 사람의 감염 상태를 char[]로 저장을 해주면서 인덱스를 찾아줍니다.

// 현재 감염된 사람의 수
int sum = 0;

// 감염 상태
char[] people = br.readLine().toCharArray();

// 감염된 사람의 번호를 저장할 큐
Queue<Integer> q = new LinkedList<>();

// 큐에 감연된 사람의 인덱스를 저장하면서 감염된 사람의 수를 계산
for (int i = 0; i < n; i++) {
    if (people[i] == 'R') {
        sum++;
        q.add(i);
    }
}

• 인덱스를 검사하면서 현재 감염된 인원을 미리 측정해줍니다.
• 이유는 다시 감염 상태를 확인해 수를 구하는 것보다 좋다고 생각했습니다.

 

2. 큐에 들어온 감염된 사람의 인덱스가 비어질 때 까지 주변을 전부 감염 시킵니다.

// 큐가 비어질 때 까지
while (!q.isEmpty()) {
    index = q.poll();

    // 감염 범위만큼 앞에 사람들을 체크
    for (int i = index + 1; i <= index + k; i++) {
        if (i >= n) { // 범위에 벗어나면 break;
            break;
        }

        // 감염
        if (people[i] == '.') {
            sum++;
            people[i] = 'R';
        }
    }

    // 감염 범위만큼 뒤에 사람들을 체크
    for (int i = index - 1; i >= index - k; i--) {
        if (i < 0) { // 범위에 벗어나면 break;
            break;
        }

        // 감염
        if (people[i] == '.') {
            sum++;
            people[i] = 'R';
        }
    }
}

• 앞과 뒤 둘 다 감염되기 때문에 index - k 에서 index + k를 해도 되지만 보기 편하게 분류를 했습니다.

3. 치료제가 더 많다면 Yes를 아니라면 No를 출력합니다.

 

// 치료제가 더 많다면
if (sum <= m) {
    sb.append("Yes");

// 치료제가 부족하다면
} else {
    sb.append("No");
}

 

 

🟪 코드

package Main;

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));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); // 사람의 수
		int m = Integer.parseInt(st.nextToken()); // 치료제의 개수
		int k = Integer.parseInt(st.nextToken()); // 감염 범위
		
		// 현재 감염된 사람의 수
		int sum = 0;
		
		// 감염 상태
		char[] people = br.readLine().toCharArray();
		
		// 감염된 사람의 번호를 저장할 큐
		Queue<Integer> q = new LinkedList<>();
		
		// 큐에 감연된 사람의 인덱스를 저장하면서 감염된 사람의 수를 계산
		for (int i = 0; i < n; i++) {
			if (people[i] == 'R') {
				sum++;
				q.add(i);
			}
		}
		
		int index;
		
		// 큐가 비어질 때 까지
		while (!q.isEmpty()) {
			index = q.poll();
			
			// 감염 범위만큼 앞에 사람들을 체크
			for (int i = index + 1; i <= index + k; i++) {
				if (i >= n) { // 범위에 벗어나면 break;
					break;
				}
				
				// 감염
				if (people[i] == '.') {
					sum++;
					people[i] = 'R';
				}
			}
			
			// 감염 범위만큼 뒤에 사람들을 체크
			for (int i = index - 1; i >= index - k; i--) {
				if (i < 0) { // 범위에 벗어나면 break;
					break;
				}
				
				// 감염
				if (people[i] == '.') {
					sum++;
					people[i] = 'R';
				}
			}
		}
		
		// 치료제가 더 많다면
		if (sum <= m) {
			sb.append("Yes");
			
		// 치료제가 부족하다면
		} else {
			sb.append("No");
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
}