λ¬Έμ
λ¬Έμ λ§ν¬ https://www.acmicpc.net/problem/1931
- ν κ°μ νμμ€μ΄ μλλ° μ΄λ₯Ό μ¬μ©νκ³ μ νλ Nκ°μ νμμ λνμ¬ νμμ€ μ¬μ©νλ₯Ό λ§λ€λ €κ³ νλ€.
- κ° νμ Iμ λν΄ μμμκ°κ³Ό λλλ μκ°μ΄ μ£Όμ΄μ Έ μκ³ , κ° νμκ° κ²ΉμΉμ§ μκ² νλ©΄μ νμμ€μ μ¬μ©ν μ μλ νμμ μ΅λ κ°μλ₯Ό μ°Ύμ보μ.
- λ¨, νμλ νλ² μμνλ©΄ μ€κ°μ μ€λ¨λ μ μμΌλ©° ν νμκ° λλλ κ²κ³Ό λμμ λ€μ νμκ° μμλ μ μλ€.
- νμμ μμμκ°κ³Ό λλλ μκ°μ΄ κ°μ μλ μλ€. μ΄ κ²½μ°μλ μμνμλ§μ λλλ κ²μΌλ‘ μκ°νλ©΄ λλ€.
- 첫째 μ€μ νμμ μ N(1 ≤ N ≤ 100,000)μ΄ μ£Όμ΄μ§λ€.
- λμ§Έ μ€λΆν° N+1 μ€κΉμ§ κ° νμμ μ λ³΄κ° μ£Όμ΄μ§λλ° μ΄κ²μ 곡백μ μ¬μ΄μ λκ³ νμμ μμμκ°κ³Ό λλλ μκ°μ΄ μ£Όμ΄μ§λ€. μμ μκ°κ³Ό λλλ μκ°μ 231-1λ³΄λ€ μκ±°λ κ°μ μμ°μ λλ 0μ΄λ€.
- 첫째 μ€μ μ΅λ μ¬μ©ν μ μλ νμμ μ΅λ κ°μλ₯Ό μΆλ ₯νλ€.
μμ΄λμ΄
- νμμ€ μκ°μ 2μ°¨μ λ°°μ΄μ μμμκ°κ³Ό λμκ°μ μ μ₯νλ€.
- λλλ μκ°μ΄ λΉ λ₯Όμλ‘ λ§μ νμμ€μ λ°°μ ν μ μκΈ° λλ¬Έμ λλλ μκ°μ κΈ°μ€μΌλ‘ λ¨Όμ μ λ ¬νλ€.
- κ·Έλ¦¬κ³ λμκ°μ΄ κ°λ€λ©΄ μμμκ°μ κΈ°μ€μΌλ‘ μ€λ¦μ°¨μ μ λ ¬μ νλ€.
- μ λ ¬μ λ€ νκ³ λ°λ³΅λ¬Έμ λ리면μ νμ¬ νμμ€ μμμκ°μ΄ μ μ₯λμ΄μλ λλ μκ°λ³΄λ€ κ°κ±°λ ν¬λ€λ©΄
- μΉ΄μ΄νΈλ₯Ό ν΄μ£Όκ³ λλλ μκ°μ νμ¬ νμμ€μ΄ λλλ μκ°μΌλ‘ κ°±μ μν¨λ€.
κ²ͺμ μνμ°©μ€
- X (μ¬μ€ νλ©΄μ 2μ°¨μ λ°°μ΄λ‘ νλ©΄ μκ° μ΄κ³Όλ λ©λͺ¨λ¦¬ μ΄κ³Όκ° λμ§ μμκΉ κ±±μ μ μ’ νλ€...)
μ½λ
import java.io.*;
import java.util.*;
public class BOJ1931 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// νμμ€ κ°μ
int N = Integer.parseInt(br.readLine());
// νμμ€ μκ° μ μ₯ν λ°°μ΄
int office[][] = new int[N][2];
for(int i = 0; i < N; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
// μμμκ°κ³Ό λμκ° λ°°μ΄μ μ μ₯
office[i][0] = a;
office[i][1] = b;
}
// μ€λ¦μ°¨μμΌλ‘ μ λ ¬
Arrays.sort(office, (n1, n2) -> {
// λλλ μκ°μ κΈ°μ€μΌλ‘ μ λ ¬ λ§μ½ λΉκ΅νλ λ κ°μ΄ κ°λ€λ©΄
// μμμκ°μ κΈ°μ€μΌλ‘ μ λ ¬
if((n1[1] - n2[1]) == 0){
return n1[0] - n2[0];
}
return n1[1] - n2[1];
});
// νμμ€ μΉ΄μ΄νΈ
int cnt = 0;
// λλλ μκ° κ³μ°ν λ μΈ λ³μ
int last_time = 0;
for(int i = 0; i < N; i++){
// λ§μ½ ν΄λΉ νμμ€ μμμκ°μ΄ μμ κ³μ°λ λλ μκ°λ³΄λ€
// κ°κ±°λ ν¬λ€λ©΄
if(office[i][0] >= last_time){
// νμμ€ + 1
cnt = cnt + 1;
// λλ μκ°μ ν΄λΉ νμμ€ λλλ μκ°μΌλ‘ κ°±μ
last_time = office[i][1];
}
}
System.out.println(cnt);
}
}
'μκ³ λ¦¬μ¦' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[Java] BOJ 2667 λ¨μ§λ²νΈλΆμ΄κΈ° (0) | 2024.08.23 |
---|---|
[Java] BOJ 2178 λ―Έλ‘νμ (2) | 2024.08.22 |
[Java] BOJ 1697 μ¨λ°κΌμ§ (0) | 2024.08.20 |
[Java] BOJ 1389 μΌλΉ λ² μ΄μ»¨μ 6λ¨κ³ λ²μΉ (0) | 2024.08.19 |
[Java] BOJ 1074 Z (0) | 2024.08.18 |