[BaekJoon] 10989번 수 정렬하기3 문제풀이 (Success)

10989번: 수 정렬하기 3

 

☕Language: Java

 

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로 정렬 시, 메모리 초과 발생

 

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로 정렬 시, 메모리 초과 발생

 

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로 변경 시, 메모리 점유가 낮아져 초과 문제를 해결할 수 있음

 

 

😮 이 외의 풀이

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된 횟수만큼 출력되도록 설정

 

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의 차이

[백준] 10989번 : 수 정렬하기 3 - JAVA [자바]