20.12.09 [백준] 10989 수 정렬하기 3

[blossun]

• 문제

• 수는 10,000보다 작거나 같은 자연수
• 중복 가능

아이디어

• Counting Sort

어려운점 & 실수

• 중복이 가능하므로 boolean 배열이 아닌 int형 배열로 몇번 나왔는지 체크해서 나온 수 만큼 출력해줌
• 자연수이므로 음수를 신경쓰지 않아도 됨!! (처음에 음수가 들어오는 줄 알고 20002로 잡았었다.)

정답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class N10989 {
 public static void main(String[] args) throws IOException {
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 StringBuilder sb = new StringBuilder();
 int N = Integer.parseInt(br.readLine());
 int[] input = new int[10002];
 for (int i = 0; i < N; i++) {
 int num = Integer.parseInt(br.readLine());
 input[num]++;
 }
 for (int i = 0; i < 10002; i++) {
 for (int j = 0; j < input[i]; j++) {
 sb.append(i).append('\n');
 }
 }
 System.out.println(sb);
 }
}

[blossun]

다들 비슷한 풀이로 푸는 듯.
int형 배열의 크기를 20002에서 10002로 잡아도 사용하는 메모리 크기는 비슷하다. 메모리 잡히는 방식 공부해야지

// 레퍼런스 변수 int[] a; (int배열형) 가 할당된 힙영역의 주소를 가지게 됩니다.
레퍼런스 변수는 스택에 저장이 되구요. //

int[] input = new int[10002]; 이거나
int[] input = new int[20002]; 이거나
알고리즘에서 잡아먹는 메모리가 거의 똑같은데 알고리즘에서 메모리 제한이 스택영역만인가?
백준에서 말하는 메모리 제한은 보통 힙 메모리를 말하는 것이라는데...

[blossun]

배열의 메모리 영역

자바 배열은 Heap(힙) 영역에 실제 메모리가 할당됩니다.
▷ Heap(힙) 영역의 특징

• new라는 동적 메모리 할당 연산자를 사용하며, 각 메모리 영역이 할당되는 자료형에 따라 초기화 작업이 자동적으로 이루어짐
• 자동적으로 Garbage Collector에 의해 소멸됨

[blossun]

알고리즘 시간제한, 메모리제한

[blossun]

메모리 효율

BufferedWriter가 StringBuilder보다 시간은 더 걸려도 메모리는 적게 잡는다.
시간 메모리 봐서 조절해서 써야할 듯