[코딩테스트] [18870] 좌표 압축 & [2910] 빈도 정렬

[18870] 좌표 압축

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

2 초

512 MB

109939

46778

35007

39.733%

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• 10 ≤ X ≤ 10i
• 9
• 9

처음 문제풀이

처음 이 문제를 봤을 때 바로 해석이 안되었다.. 🥲

X'1, X'2, ..., X'N 이 값을 X 다시 혹은 X 프라임 이라고 하는데 X와 연관이 있는 값이라고 한다..

그리고 조건이 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. 조건이 있는데

Xi에서 좌표 압축을 하여 나온 값 X'i는 즉 Xi를 제외한 나머지 수 Xj 중 Xi보다 작은 수들의 총 합 개수이다!

실버 3부터 이제 문제를 보고 바로 이해가 되지 않고 있다..

0. 예제를 입력받아 배열에 저장하자

1. 중복을 제거하고 정렬을 하자

입력한 값을 기억해야 하니 배열 하나와 Set을 하나 만들어주자.

여기서 TreeSet을 하여 중복을 제거하고 정렬을 하였다.

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        Set<Integer> setNumbers = new TreeSet<>();
        Integer[] answers = new Integer[N];

        for (int i=0; i<N; i++) {
            answers[i] = sc.nextInt();
            setNumbers.add(answers[i]);
        }

2. 입력받은 값을 갖고 있는 배열과 조건을 충족한 배열 비교하기

아까 TreeSet을 이용하여 조건을 충족시켰던 Set 자료구조를 배열로 변경해주고

처음 입력했던 것과 비교하여 같은 값을 가지고 있을 때 순서를 출력해주자.

정렬이 되어 있으니 그 순서는 자기보다 작은 개수를 갖고 있는 것과 같다.

답도 잘 나오니 제출을 해보겠다.

        Integer[] sortNumbers =  setNumbers.toArray(new Integer[setNumbers.size()]);

        for (int i=0; i<answers.length; i++) {
            for (int j=0; j<sortNumbers.length; j++) {
                if (sortNumbers[j].equals(answers[i])) {
                    System.out.print(j + " ");
                    break;
                }
            }
        }

시간초과가 발생한다.. 왜냐하면 시간복잡도가 O(N^2)이 나오기 때문이다.

N의 최악의 개수는 1,000,000이다 다른 방법을 사용해야겠다..

Set과 Map을 사용한 풀이

이차원 배열로도 풀어볼 수 있지만 나는 Set과 Map을 사용해서 풀어보겠다.

그리고 입력값과 출력값이 많으니 BufferedReader와 BufferedWriter를 사용하여 입출력해보겠다.

1. 입력된 좌표를 작은 순으로 정렬한다.

2. 정렬된 좌표를 중복제거하여 압축한다.

일단 br로 입력을 받기 위해 String[]을 사용하고 int[]로 변경하기 위해 반복문을 사용해서 값을 넣어주었다.

그리고 Set을 만들어서 TreeSet으로 정렬과 중복을 제거해주고 HashSet은 정렬이 안되니 조심하자

왼쪽이 TreeSet으로 나온 출력값, 오른쪽은 HashSet을 사용한 출력값

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        int[] inputNumbers = new int[N];
        String[] input = new String[N];
        input = br.readLine().split(" ");

        Set<Integer> set = new TreeSet<>();

        for (int i=0; i<N; i++) {
            inputNumbers[i] = Integer.parseInt(input[i]);
            set.add(inputNumbers[i]);
        }

 

3. 입력된 좌표값에 알맞은 압축 인덱스를 출력한다.

이제 input에 있는 값들의 알맞은 값을 출력해주면 된다.

그러기 위해서 Map 자료구조를 사용하여 정렬된 값과 순서들을 저장할 것 이다.

for(int x: set)을 사용해서 set의 값을 순서대로 x와 idx++같이 실행하면 idx는 실행되고 1추가하여 0, 1, 2 이렇게 값이 들어간다.

들어간 순서가 즉 자기보다 작은 개수를 갖고 있는 순서이기 때문에 idx는 자기보다 작은 개수를 갖고 있고

그것을 출력하기 위해 map.get(inputNumbers[i])을 해주면 value가 출력이 되고 답이 나온다.

        Map<Integer, Integer> map = new HashMap<>();
        int idx = 0;

        for(int x: set)
            map.put(x, idx++);

        for(int i=0; i<N; i++)
            bw.write(map.get(inputNumbers[i]) + " ");
        bw.write("\\n");
        bw.flush();

시간복잡도

이 알고리즘의 시간복잡도는 입력을 받을때 O(N), Set으로 중복을 제거할때 O(NlogN), Map을 사용하여 위치 계산을 하는 것이 O(NlogN), 출력도 O(N) 즉, O(NlogN)이다.

전체 코드

import java.io.*;
import java.util.*;

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));

        int N = Integer.parseInt(br.readLine());

        int[] inputNumbers = new int[N];
        String[] input = new String[N];
        input = br.readLine().split(" ");

        Set<Integer> set = new TreeSet<>();

        for (int i=0; i<N; i++) {
            inputNumbers[i] = Integer.parseInt(input[i]);
            set.add(inputNumbers[i]);
        }

        Map<Integer, Integer> map = new HashMap<>();
        int idx = 0;

        for(int x: set)
            map.put(x, idx++);

        for(int i=0; i<N; i++)
            bw.write(map.get(inputNumbers[i]) + " ");
        bw.write("\\n");
        bw.flush();
    }
}

[2910] 빈도 정렬

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

128 MB

13523

7574

5694

55.763%

문제

위대한 해커 창영이는 모든 암호를 깨는 방법을 발견했다. 그 방법은 빈도를 조사하는 것이다.

창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했다. 이 메시지는 숫자 N개로 이루어진 수열이고, 숫자는 모두 C보다 작거나 같다. 창영이는 이 숫자를 자주 등장하는 빈도순대로 정렬하려고 한다.

만약, 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다. 만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다.

이렇게 정렬하는 방법을 빈도 정렬이라고 한다.

수열이 주어졌을 때, 빈도 정렬을 하는 프로그램을 작성하시오.

입력

첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000)

둘째 줄에 메시지 수열이 주어진다.

출력

첫째 줄에 입력으로 주어진 수열을 빈도 정렬한 다음 출력한다.

문제풀이

이 문제는 등장한 숫자의 총 개수를 구하여 내림차순으로 정렬을 한다. 만약 총 개수가 같은 값이 있다면 먼저 들어온 순서로 정렬을 해주면 된다. 예제 2를 기준으로 보자.

9 3
1 3 3 3 2 2 2 1 1

[1 3 3 3 2 2 2 1 1]이 되고 정렬을 하면 1 1 1 3 3 3 2 2 2이 된다.

1. 등장한 수 구하기

배열을 만들어서 입력값을 모두 배열에 저장하자.

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int C = sc.nextInt();
        
        Integer[] input = new Integer[N];

        for(int i=0; i<N; i++)
            input[i] = sc.nextInt();

2. 등잔한 수를 기준으로 내림차순 정렬하기

3. 만약 같다면 먼저 들어온 순서대로 정렬하기

들어온 순서대로 정렬하기 위해서 LinkedHashMap을 사용한다.

Map에 같은 Key값이 있다면 value를 1 추가해주고 없다면 value를 1로 만들어주자.

        Map<Integer, Integer> map = new LinkedHashMap<>();
        
        int count = 0;

        for(int i=0; i<N; i++) {
            if(map.containsKey(input[i])) {
                count = map.get(input[i]);
                count++;
                map.put(input[i], count);
            } else {
                map.put(input[i], 1);
            }
        }

그리고 다시 Map의 엔트로를 배열로 변환하고 value를 기준으로 내림차순 정렬을 한다.

그리고 Value만큼 key를 출력해주면된다.

 // Map의 엔트리를 배열로 변환
        Map.Entry<Integer, Integer>[] entryArray = map.entrySet().toArray(new Map.Entry[0]);

        // value를 기준으로 내림차순 정렬
        Arrays.sort(entryArray, (entry1, entry2) -> entry2.getValue().compareTo(entry1.getValue()));

        for (Map.Entry<Integer, Integer> entry : entryArray) {
            int key = entry.getKey();
            int value = entry.getValue();
            for (int i = 0; i < value; i++) {
                System.out.print(key + " ");
            }
        }

Frequency class를 사용한 문제풀이

class를 만들어서 count와 firstIndex끼리 비교하여 문제를 풀 수도 있다.

하지만 아래처럼 풀면 메모리가 부족한데 그 이유는 C가 최대 10억이기 때문에 Count 배열을 이용해 빈도를 구하는 방법은 메모리가 부족하다.

class Frequency {
	int num;
	int count;
	int firstIndex;
}

Arrays.sort(frequencies, (o1, o2) -> {
	if (o1.count==o2.count)
		return o1.firstIndex - o2.firstIndex;
	return o2.count - o1.count;
});

for (Frequency frequency : frequencies)
	while (frequency.count-->0)
		System.out.print(frequency.num + " a);
System.out.println();

더 간단히 풀어보자

아까와 똑같이 LinkedHashMap을 사용해서 풀 것 이다.

다만 더 간단하고 편리하게 구현을 해보자.

다만 더 간단하고 편리하게 구현을 해보자.

LinkedHashMap을 사용하면 Put한 순서대로 Key가 유지되고 Interger[]로 Tim Sort를 사용하면 stable하기 때문에 Frequency가 같다면 먼저 입력한 Key가 앞에 위치한다.

import java.util.*;

class Main
{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int C = sc.nextInt();
        Map<Integer, Integer> messages = new LinkedHashMap<>();
        for (int i = 0; i < N; i++) {
            int message = sc.nextInt();
            messages.put(message, messages.getOrDefault(message, 0) + 1);
        }

        Integer[] frequencies = messages.keySet().toArray(new Integer[messages.size()]);
        Arrays.sort(frequencies, (o1, o2) -> messages.get(o2) - messages.get(o1));

        for (int frequency : frequencies) {
            int count = messages.get(frequency);
            while (count-- > 0)
                System.out.print(frequency + " ");
        }
        System.out.println();
    }
}