728x90
반응형
2024.09.05기준 - 실버3
728x90
백준, BEAKJOON, BOJ, JAVA, 자바
풀이
이 문제는 테이프를 이용해 물을 막을 때, 최소 몇개의 테이프를 사용하는지 출력하는 문제입니다.
접근 방법
- 입력받은 물이 새는 위치를 우선순위 큐로 정렬과 동시에 입력을 받았습니다.
- 처음 테이프를 붙인 위치에서 한 번에 테이프를 붙일 수 있는지 확인해 최소 테이프의 개수를 구했습니다.
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();
}
}
728x90
반응형
'코딩테스트 일기 (BAEKJOON)' 카테고리의 다른 글
BEAKJOON / 백준 - JAVA 2096번 내려가기 (0) | 2024.09.07 |
---|---|
BEAKJOON / 백준 - JAVA 1916번 최소비용 구하기 (0) | 2024.09.06 |
BEAKJOON / 백준 - JAVA 1497번 기타콘서트 (3) | 2024.09.04 |
BEAKJOON / 백준 - JAVA 30620번 서로소 싫어 (0) | 2024.09.03 |
BEAKJOON / 백준 - JAVA 9342번 염색체 (0) | 2024.09.02 |