백준 | 10989 : 수 정렬하기 3 (Java)

문제에 대한 자세한 정보는 백준 | 10989번 : 수 정렬하기 3에서 확인할 수 있다.

풀이

배열 사용

2751번 : 수 정렬하기 2와 다르게 수가 중복된다. 2751번에서는 index를 사용해 boolean 배열에 해당 수가 입력되면 true값으로 저장했지만 이번에는 int 배열에 해당 수가 몇 번 입력되었는지 저장한다.
10,000보다 작거나 같은 자연수가 주어지므로 10001 길이를 가지는 배열을 생성하면 된다. (arr[5] == 3이면 5가 3번 입력됨.)

Map 사용

배열로 문제를 풀었는데 Map으로도 풀 수 있을 것 같았다.
key에는 입력된 수, value에는 입력 횟수를 저장하면 된다.

소스코드

배열 사용

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[10001];

		for (int i = 1; i <= N; i++) {
			arr[Integer.parseInt(br.readLine())]++;
		}

		for (int i = 1; i <= 10000; i++) {
			while (arr[i] != 0) {
				bw.write(String.valueOf(i) + "\n");
				arr[i]--;
			}
		}

		br.close();
		bw.close();
	}
}

Map 사용

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int MAX = 10000;
		int N = Integer.parseInt(br.readLine());
		Map<Integer, Integer> map = new HashMap<>();

		for (int i = 0; i < N; i++) {
			int temp = Integer.parseInt(br.readLine());
			if (!map.containsKey(temp))
				map.put(temp, 1);
			else
				map.put(temp, map.get(temp) + 1);

		}

		for (int i = 1; i <= MAX; i++) {
			if (map.containsKey(i)) {
				int temp = map.get(i);
				while (temp != 0) {
					bw.write(i + "\n");
					temp--;
				}
			}
		}

		br.close();
		bw.close();
	}
}

메모리, 시간

배열 사용

메모리 : 296388KB
시간 : 1944ms

Map 사용

메모리 : 300768KB
시간 : 2360ms