10989번: 수 정렬하기 3
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
www.acmicpc.net
☕Language: Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int cnt = Integer.parseInt(br.readLine());
List<Integer> intList = new ArrayList<>();
while (cnt-- > 0) {
intList.add(Integer.parseInt(br.readLine()));
}
Collections.sort(intList);
for (int i = 0; i < intList.size(); i++) {
if (i == intList.size() - 1) {
bw.write(intList.get(i) + "");
} else {
bw.write(intList.get(i) + "\n");
}
}
bw.flush();
bw.close();
}
}
|
|
🚨 List를 Collections 함수 sort로 정렬 시, 메모리 초과 발생
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long cnt = Integer.parseInt(br.readLine());
List<Integer> intList = new ArrayList<>();
while (cnt-- > 0) {
intList.add(Integer.parseInt(br.readLine()));
}
intList.sort(Comparator.naturalOrder());
for (int i = 0; i < intList.size(); i++) {
if (i == intList.size() - 1) {
bw.write(intList.get(i) + "");
} else {
bw.write(intList.get(i) + "\n");
}
}
bw.flush();
bw.close();
}
}
|
|
🚨 List를 Comparator로 정렬 시, 메모리 초과 발생
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int cnt = Integer.parseInt(br.readLine());
int[] intArr = new int[cnt];
for(int i=0; i<cnt; i++) {
intArr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(intArr);
for(int i : intArr) {
bw.write(i+"\n");
}
bw.flush();
bw.close();
}
}
|
|
🤔 해설
- int[]를 선언해서 Arrays 라이브러리에 sort 메서드 사용
⭐ ArrayList와 int[] 차이
1. ArrayList
- 가변적 크기
- 데이터 추가, 삭제 시, 메모리를 재할당하므로 속도가 Array보다 느림
- 다차원 불가
2. Array(int[])
- 고정된 크기
- 초기화 시, 메모리에 할당되어 ArrayList보다 속도가 빠름
- 다차원 가능(int[][])
Integer는 Wrapper class로 객체가 기본 데이터 유형을 래핑하거나 포함하므로 int형에 비해 큰 저장 공간이 필요
→ Integer에서 int로 변경 시, 메모리 점유가 낮아져 초과 문제를 해결할 수 있음
😮 이 외의 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int cnt = Integer.parseInt(br.readLine());
StringBuffer sb = new StringBuffer();
int[] iArr = new int[10001];
for (int i = 0; i < cnt; i++) {
iArr[Integer.parseInt(br.readLine())]++;
}
for (int i = 0; i < iArr.length; i++) {
if (iArr[i] > 0) {
for (int j = 0; j < iArr[i]; j++) {
sb.append(i).append("\n");
}
}
}
bw.write(sb + "");
bw.flush();
bw.close();
}
}
|
|
- 계수 정렬(Counting Sort) 사용
- if 조건문: 입력값이 있는 경우에만 출력되도록 설정
- 내부 for 반복문: 중복값이 존재하므로 Count된 횟수만큼 출력되도록 설정
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int cnt = Integer.parseInt(br.readLine());
StringBuffer sb = new StringBuffer();
int[] iArr = new int[10001];
for (int i = 0; i < cnt; i++) {
iArr[Integer.parseInt(br.readLine())]++;
}
for (int i = 0; i < iArr.length; i++) {
while (iArr[i]-- > 0) {
sb.append(i).append("\n");
}
}
bw.write(sb + "");
bw.flush();
bw.close();
}
}
|
|
- 계수 정렬(Counting Sort) 사용2
- if 조건문과 내부 for 반복문을 while문으로 교체하여 코드 간결화
🔗 소스 코드
HJ0216/TIL/BOJ
📚 참고 자료
Array와 ArrayList의 차이
배열(Array)과 ArrayList의 차이점 Array ArrayList 사이즈 초기화시 고정 int[] arr = new int[3]; 초기화시 사이즈를 표시하지 않음. 크기가 가변적임 ArrayList arrList = new ArrayList(); 속도 초기화시 메모리에 할당
dev-coco.tistory.com
[백준] 10989번 : 수 정렬하기 3 - JAVA [자바]
www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmic
st-lab.tistory.com
