[코딩테스트/백준 알고리즘] 10816번 : 숫자 카드 2 (Java, 자바 풀이)

문제

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

---

문제 설명

---

문제 풀이

 계수 정렬(카운팅 정렬)을 할 때 사용하는 방법을 사용하기로 했다. 계수 정렬은 정렬할 데이터에 해당 요소가 몇 개씩 있는지 센 후 이를 앞 순서대로 차례대로 써주면 된다.

 

계수 정렬 예시

ex)
입력 데이터 : {1, 1, 4, 7, 8, 5, 6, 2, 3, 3, 7 ,7 ,9, 10}

1 : 2개
2 : 1개
3 : 2개
4 : 1개
5 : 1개
6 : 1개
7 : 3개
8 : 1개
9 : 1개
10 : 1개

1부터 10까지 개수대로 나열
[1, 1, 2, 3, 3, 4, 5, 6, 7, 7, 7, 8, 9, 10]

 계수 정렬은 입력 데이터에 중복된 값이 많고, 입력 데이터의 개수가 클 때 쓰면 유리하다.

 

 나는 20000001개 크기의 배열을 제작( -10,000,000  카드에 적혀있는 수 ≤ 10,000,000)하여 상근이가 가진 카드가 나올 때마다 그 수에 대응하는 배열의 요소값을 증가시켰다.

index	0	1	...	10000000	10000001	...	19999999	20000000
대응하는 수	-10,000,000	-9,999,999		0	1		9,999,999	10,000,000

---

코드

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

class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] sang = new int[20000001];
        int n = sc.nextInt();	//상근이 카드 수
        
        while(n-- > 0) {	//상근이 카드 카운트
            int card = sc.nextInt();
            sang[card + 10000000]++;
        }
        
        int m = sc.nextInt();	//확인하려는 카드 수
        
        while(m-- > 0) {
            int card = sc.nextInt();
            bw.write(sang[card + 10000000] + " ");
        }
        bw.flush();
    }
}

---

총평

  메모리 낭비가 엄청나다. Map을 사용했어도 좋은 풀이가 될 거 같았지만 뭔가 이렇게 해보고 싶었다.