[백준]18870 좌표 압축
- 수직선 위에 N개의 좌표 X1,X2,...,Xn 이 존재함.
- Xi를 좌표 압축 → Xi' 의 값은 X i > X j 를 만족하는 서로 다른 좌표의 개수와 같다.
- N은 100만 이하이다.
- 각각의 Xi는 -10억 이상 10억 이하다.
풀이 생각
(시간 초과로 인해 멘붕이 왔다. 시간초과 이후 한 시간 반을 고민해버렸다.. 다른 사람 풀이를 먼저 보는 것이 그렇게 어렵나.. ㅠ 고민하는 시간을 줄이자💥_)
-
이 문제는 중복되는 원소가 있을 수 있다는 것이 핵심이다.
-
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 [ 서로 다른 좌표의 개수 ]와 같아야 한다 ==⇒ 즉, Xi>Xj를 만족하는 동일한 Xj가 여러개더라도 한개로 취급한다.
( 여기서 실수가 있었다💥💥 )6 1000 999 1000 999 1000 999 // 1 0 1 0 1 0 -
N의 개수는 100만 이하이고, 각 Xi는 -10억 이상 10억 이하이기 때문에 ,
-
단순히 Map을 사용하여 iterate할까
-
Map은 Unordered Data Structure이기 때문에, a 보다 작은 숫자의 개수가 몇 개인지 탐색하기 위해 결국, 단순히 각 a에 대해 또 다시 n개 전체를 iterate하는 경우가 생길 수 있다.
- 이 경우, n이 100만이기 때문에 O(n^2) 의 효율이 나와서는 안 된다.
-
ArrayList를 두고, Map에 아직 없는 숫자 → ArrayList에 추가 —> 이 ArrayList를 정렬시킨다. → List를 iterate하면서 cnt에 누적시킨다. cnt는 map으로부터 수를 가져와 누적시켜야 한다., 해당 element를 방문할 때의 cnt는, 해당 element에 대한 e' 과 같다. → 이것을 Map에 다시 저장한다.
시간초과가 나옴
-
map을 사용할 때 n이 100만 정도가 되면 시간초과가 된다고 한다.
글 읽기 - [c++] map 사용했는데 시간초과 났습니다ㅠㅜ
map이나 set 등은 레드블랙 트리라는 자료구조를 사용하는데 이는 시간복잡도는 로그를 보장해주지만 상수가 매우 큰 자료구조입니다. 특히 삽입/삭제 연산에서 상당히 많은 작업이 들어갈 수 있습니다.
입력을 한 번에 받고 나중에 정렬하는 편이 몇 배는 더 빠릅니다.
-
하지만 100만으로 이런 결과가 나오는 것 같지는 않았다.
-
문제는 System.out.println()의 사용으로 인한 것이었다. —> BufferedWriter를 사용하는 것으로 변경하였다.
import java.io.*;
import java.util.*;
public class Main {
public static int n;
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static StringBuilder sb = new StringBuilder("");
public static List<Integer> list = new ArrayList<>(1000000); // unique한 수를 입력
public static Map<Integer, Integer> map = new HashMap<>();
public static int[] input; // 주어진 수
public static void Setting() throws IOException {
n = Integer.parseInt(br.readLine());
input = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
int i=0;
int temp=0 , cnt=0, numbCnt=0;// numbCnt는 해당 numb가 몇 개 존재하는지
for(;i<n;i++) {
temp = Integer.parseInt(st.nextToken());
input[i] = temp;
if (map.containsKey(temp)) continue;
// map에 존재하지 않는 수
list.add(temp);
map.put(temp, 1);
}
Collections.sort(list);
// list를 iterate
for(Integer numb:list){
// 현재 numb의 개수를 저장해둔다.
numbCnt = map.get(numb);
// 현재 cnt를 numb에 대한 numb' 로서 저장한다
map.put(numb,cnt);
cnt+=numbCnt;
}
// input을 iterate
for(Integer numb:input){
sb.append(map.get(numb));
sb.append(" ");
}
bw.write(sb.toString());
bw.flush();
bw.close();
}
public static void main(String[] args) throws IOException {
Setting();
}
}다른 사람 풀이
- input 배열을 copy한 배열을 생성 → copy라 칭하자
- copy를 정렬시킨다.
- copy를 iterate하면서, 중복되지 않은 수라면 hashmap에 numb를 넣는다, 오름차순 정렬되어있는 copy의 numb 순으로 넣기 때문에, 해당 numb는 이제까지 앞선 numb들의 개수 누적값을 value로 map에 저장한다.
import java.io.*;
import java.util.*;
public class Main {
public static int n;
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static StringBuilder sb = new StringBuilder("");
public static Map<Integer, Integer> map = new HashMap<>();
public static int[] input; // 주어진 수
public static int[] copy;
public static void Setting() throws IOException {
n = Integer.parseInt(br.readLine());
input = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
int i=0;
int temp=0 , cnt=0, numbCnt=0;// numbCnt는 해당 numb가 몇 개 존재하는지
for(;i<n;i++) {
input[i] = Integer.parseInt(st.nextToken());
}
copy = input.clone();
Arrays.sort(copy);
for (int numb : copy) {
if(map.containsKey(numb))continue; // 중복 제거 가능
map.put(numb,cnt++);
}
for (int numb : input) {
sb.append(map.get(numb));
sb.append(" ");
}
bw.write(sb.toString());
bw.flush();
bw.close();
}
public static void main(String[] args) throws IOException {
Setting();
}
}