BEAKJOON / 백준 - JAVA 1449번 수리공 항승

2024.09.05기준 - 실버3

728x90

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 테이프를 이용해 물을 막을 때, 최소 몇개의 테이프를 사용하는지 출력하는 문제입니다.

 

접근 방법

1. 입력받은 물이 새는 위치를 우선순위 큐로 정렬과 동시에 입력을 받았습니다.
2. 처음 테이프를 붙인 위치에서 한 번에 테이프를 붙일 수 있는지 확인해 최소 테이프의 개수를 구했습니다.

 

1. 입력받은 위치를 우선순위 큐에 저장합니다.

// 입력 받은 물이 새는 위치를 오름차순으로 정렬.
PriorityQueue<Integer> q = new PriorityQueue<>();
st = new StringTokenizer(br.readLine());

while (n-- > 0) {
    q.add(Integer.parseInt(st.nextToken()));
}

 

2. 처음 테이프를 붙힌 위치에서 거리를 계산해 테이프를 몇개를 사용하는지 계산을 합니다.

int count = 1;
int start = q.poll();
int now;

while (!q.isEmpty()) {
    now = q.poll();

    // 처음 테이프를 붙힌 위치에서 현재 참조하는 위치까지 못 붙힌다면
    if (now - start > l - 1) {
        count++;
        start = now;
    }
}

 

 

 

코드

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));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); // 물이 새는 곳의 개수
		int l = Integer.parseInt(st.nextToken()); // 테이프의 길이
		
		// 입력 받은 물이 새는 위치를 오름차순으로 정렬.
		PriorityQueue<Integer> q = new PriorityQueue<>();
		st = new StringTokenizer(br.readLine());
		
		while (n-- > 0) {
			q.add(Integer.parseInt(st.nextToken()));
		}
		
		int count = 1;
		int start = q.poll();
		int now;
		
		while (!q.isEmpty()) {
			now = q.poll();
			
			// 처음 테이프를 붙힌 위치에서 현재 참조하는 위치까지 못 붙힌다면
			if (now - start > l - 1) {
				count++;
				start = now;
			}
		}
		
		bw.write(Integer.toString(count));
		bw.flush();
		bw.close();
		br.close();
	}
}