๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/18870
- ์์ง์ ์์ N๊ฐ์ ์ขํ X1, X2, ..., XN์ด ์๋ค. ์ด ์ขํ์ ์ขํ ์์ถ์ ์ ์ฉํ๋ ค๊ณ ํ๋ค.
- X1, X2, ..., XN์ ์ขํ ์์ถ์ ์ ์ฉํ ๊ฒฐ๊ณผ X'1, X'2, ..., X'N๋ฅผ ์ถ๋ ฅํด๋ณด์.
- Xi๋ฅผ ์ขํ ์์ถํ ๊ฒฐ๊ณผ X'i์ ๊ฐ์ Xi > Xj๋ฅผ ๋ง์กฑํ๋ ์๋ก ๋ค๋ฅธ ์ขํ Xj์ ๊ฐ์์ ๊ฐ์์ผ ํ๋ค.
- ์ฒซ์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค.
- ๋์งธ ์ค์๋ ๊ณต๋ฐฑ ํ ์นธ์ผ๋ก ๊ตฌ๋ถ๋ X1, X2, ..., XN์ด ์ฃผ์ด์ง๋ค.
- ์ฒซ์งธ ์ค์ X'1, X'2, ..., X'N์ ๊ณต๋ฐฑ ํ ์นธ์ผ๋ก ๊ตฌ๋ถํด์ ์ถ๋ ฅํ๋ค.
์์ด๋์ด
- ์ขํ๊ฐ์ ์ ์ฅํ ๋ ๋ฐฐ์ด์ ํ๋ฒ ์ ์ฅํ๊ณ TreeSet์ ํ๋ฒ ๋ ์ ์ฅํ๋ค.
- TreeSet์ ์ ์ฅํ๋ ์ด์ ๋ ์ค๋ณต๊ฐ์ ์ ๊ฑฐํ๊ณ ์ ๋ ฌํ๊ธฐ ์ํด์์ด๋ค.
- ๊ทธ๋ฆฌ๊ณ HashMap์ TreeSet์ ์ ์ฅํ ๊ฐ์ Key๋ก, ์์๋ฅผ ์ ์ฅํ ๋ณ์๋ฅผ ์ ์ธํ๊ณ 1์ฉ ์นด์ดํธํ์ฌ Value๊ฐ์ผ๋ก ์ ์ฅํ๋ค. (์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋์๊ธฐ ๋๋ฌธ์ ์์๋๋ก ์นด์ดํธํ ๊ฐ์ด ์์๊ฐ ๋๋ค.)
- ๊ทธ๋ฆฌ๊ณ ์ฒ์์ ์ ์ฅํ ๋ฐฐ์ด๊ฐ์ผ๋ก HashMap์์ ๊ฒ์ํ์ฌ ์์๋ฅผ ๊ฒฐ๊ณผ๊ฐ ๋ฐฐ์ด์ ์ ์ฅํ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- X
์ฝ๋
import java.io.*;
import java.util.*;
public class BOJ18870 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// ์ขํ ๊ฐ์
int N = Integer.parseInt(br.readLine());
// ์ขํ๊ฐ์ ๋ฃ์ ๋ฐฐ์ด
int arr[] = new int[N];
// ์ขํ๊ฐ์ ์ ๋ ฌํ treeset(์ค๋ณต๊ฐ์ ์ ์ธํ๊ธฐ ์ํด)
TreeSet<Integer> arr2 = new TreeSet<>();
// ์ขํ๊ฐ๊ณผ ์์ถ ์ขํ๊ฐ์ ์ ์ฅํ Hashmap
HashMap<Integer, Integer> graph = new HashMap<>();
// ๊ฒฐ๊ณผ๊ฐ์ ์ ์ฅํ ๋ฐฐ์ด
int result[] = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
// ๋ฐฐ์ด์ ์ขํ๊ฐ์ ์ ์ฅ
for(int i = 0; i < N; i++){
int x = Integer.parseInt(st.nextToken());
arr[i] = x;
arr2.add(x);
}
// ์์
int cnt = 0;
// ์ ๋ ฌํ treeset์ ๊ฐ์ key๋ก, ์์๋ฅผ value๋ก hashmap์ ์ ์ฅ
for(int i : arr2){
graph.put(i, cnt);
// ์์ + 1
cnt = cnt + 1;
}
for(int i = 0; i < arr.length; i++){
// ๊ฒฐ๊ณผ๊ฐ์ ๋ฐฐ์ด์ ๊ฐ์ ์ด์ฉํ์ฌ hashmap์ ์ ์ฅ๋์ด์๋ value๊ฐ์ ์ ์ฅ
result[i] = graph.get(arr[i]);
}
for(int i = 0; i < result.length; i++){
sb.append(result[i] + " ");
}
System.out.println(sb);
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 30804 ๊ณผ์ผ ํํ๋ฃจ (2) | 2024.08.17 |
---|---|
[Java] BOJ 21736 ํ๋ด๊ธฐ๋ ์น๊ตฌ๊ฐ ํ์ํด (0) | 2024.08.16 |
[Java] BOJ 18111 ๋ง์ธํฌ๋ํํธ (0) | 2024.08.14 |
[Java] BOJ 11724 ์ฐ๊ฒฐ ์์์ ๊ฐ์ (0) | 2024.08.13 |
[Java] BOJ 2805 ๋๋ฌด ์๋ฅด๊ธฐ (2) | 2024.08.12 |