[백준]2750 수 정렬하기 1 - 자바/Java

11399번: ATM

🌱풀이

알고리즘

1. 삽입 정렬을 사용하든, 버블 정렬을 사용하든 상관없다. 연습삼아 삽입정렬로 했다.
2. 최초 반복문의 i는 검사하고자 하는 값의 인덱스다. 인덱스와 값은 따로 빼둔다.
3. 내부 반복문에서 j는 검사하고자 하는 인덱스보다 낮은 인덱스들이다. 즉, 검사하고자 하는 인덱스의 번호는 갈수록 커지고 검사 범위의 인덱스는 검사 인덱스보다 1 낮은 상태에서 0까지 감소하며 진행된다.
4. 검사 중 만약 검사 인덱스보다 작은 값이 있다면, 해당 인덱스를 저장하여 기억해둔다.
5. 나보다 작은 값이 없다면 내가 가장 작은 값이므로 j == 0 일 때도 기억해둔다.
6. 검사 인덱스와 기억해둔 인덱스 사이를 돌며 배열 값을 하나씩 뒤로 미룬다. 마지막에는 기억해둔 인덱스의 값을 입력한다.

메모리 : KB, 시간 : ms

package book_algoTEst;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_11399 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] A = new int[N];
		int[] S = new int[N];
		for(int i = 0; i<N; i++) A[i] = Integer.parseInt(st.nextToken());
		
		//삽입 정렬
		for(int i = 1; i<N; i++) {
			int insert_point = i;
			int insert_value = A[i];
			for(int j = i-1; j>=0; j--) {
				if(A[j] < A[i]) {
					insert_point = j+1;
					break;
				}
				if(j == 0) insert_point = 0;
			}
			for(int j = i; j > insert_point; j--) A[j] = A[j-1];
			A[insert_point] = insert_value;
		}
		
		//각 사람이 걸리는 시간
		S[0] = A[0];
		for(int i = 1; i<N; i++) S[i] = A[i]+S[i-1];
		
		int sum = 0;
		for(int i = 0; i<N; i++) sum += S[i];
		System.out.println(sum);
		br.close();
	}
}

---

🪴코드 리뷰

Array.sort는 시간 복자도가 O(nLogn) 이므로 삽입 정렬보다 빠르다. 그래서 시간이 단축된 듯. 해당 라이브러리가 사용하는 정렬 알고리즘은 Dual-Pivot Quick Sort이다. 두 개의 피 봇으로 퀵 정렬 한다는 뜻이다.

🌿메모리 : 11836KB, 시간 : 84ms

💡 풀이자 : apso123

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] time = new int[N];
        int[] sum = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int k=0; st.hasMoreTokens(); k++){
            time[k] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(time);
        for(int i=0; i<N; i++){
            sum[i] = time[i];
        }

        for(int i=0; i<N-1; i++){
            sum[i+1] += sum[i];
        }

        int answer=0;
        for(int s=0; s<N; s++)
            answer += sum[s];
        System.out.println(answer);
    }
}

---

Conclusion

• 삽입 정렬은 구현이 버블 정렬보다 까다롭지만 시간 복잡도는 n의 제곱으로 동일하다.
• 써먹을 일은 없겠지만 로직의 발상은 기억해두면 좋겠다.