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

2751번: 수 정렬하기 2

🌱풀이

알고리즘

병합 정렬을 사용했다.

1. mergeSort의 s는 시작 인덱스, e는 종료 인덱스다. 다르게 말하면 s는 우측 인덱스, e는 좌측 인덱스다. 투 포인터 마냥 pivot 인덱스를 향해 다가온다.
2. e-s < 1 일 때 return 하는 건, 두 인덱스가 같거나 시작 인덱스가 종료 인덱스보다 큰 경우다.
3. m은 pivot 인덱스다. 시작과 종료 인덱스의 중간으로 하는게 일반적이다.
4. mergeSort(s,m) 과 mergeSort(m+1,e)를 호출한다. 이로서 m번 인덱스를 기준으로 좌측, 우측으로 범위가 절반씩 쪼개지는 재귀 함수가 호출된다.
5. for(int i = s; i<=e; i++) tmp[i] = A[i]; 는 배열을 잠시 복사해두는 기능을 한다.
6. 첫번째 while문은 서로 다른 두 그룹을 병합하는 기능을 수행한다.둘 중 작은 값은 A[] 배열에 입력한다.
7. 한 그룹은 s → m, 한 그룹은 m+1 → e 까지 검사하며 서로의 값을 비교한다.
8. 아래의 while문은 두 그룹 중 남아있는 값들을 검사하며 A 배열에 입력해서 마무리한다.

메모리 : 194404KB, 시간 : 1056ms

package book_algoTEst;

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

public class BOJ_2751 {
	public static int[] A, tmp;
	public static long result;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		A = new int[N+1];
		tmp = new int[N+1];
		for(int i = 1; i<=N; i++) A[i] = Integer.parseInt(br.readLine());
		mergeSort(1,N);
		for(int i = 1; i<= N; i++) bw.write(A[i]+"\\n");
		bw.flush();
		bw.close();
	}
	public static void mergeSort(int s, int e) {
		if( e - s < 1) return;
		int m = s+(e-s)/2;
		//재귀 함수로 구현
		mergeSort(s,m);
		mergeSort(m+1,e);
		for(int i = s; i<=e; i++) tmp[i] = A[i];
		int k = s;
		int index1 = s;
		int index2 = m+1;
		
		// 두 그룹을 병합하는 로직
		while(index1 <= m && index2 <= e) {
			// 양쪽 그룹의 index가 가리키는 값을 비교해 더 작은 수를 배열에 저장, 
			// 선택된 데이터의 index 값을 오른쪽으로 한 칸 이동하기
			if(tmp[index1] > tmp[index2]) {
				A[k] = tmp[index2];
				k++;
				index2++;
			}
			else {
				A[k] = tmp[index1];
				k++;
				index1++;
			}
		}

		while(index1 <= m) {
			A[k] = tmp[index1];
			k++;
			index1++;
		}
		while(index2 <= e) {
			A[k] = tmp[index2];
			k++;
			index2++;
		}
	}
}

---

🪴코드 리뷰

옛날에 짜두었던 코드다. 정렬 로직이 하나도 없길래 뭐지? 하고 살펴봤는데.. 아니 이게 무슨??

데이터의 최대 범위에 해당하도록 Boolean형 배열을 선언하고, 입력되는 데이터는 인덱스로 입력시킨다. 인덱스가 입력된 배열은 false에서 true로 바꾼다. 이 후 마지막에 Boolean형 배열을 순회하면서 true인 값의 인덱스만 추출하면 된다. 데이터를 따로 정렬하지 않고도 입력되는 족족 자동으로 정렬되는 효과가 있다.

심지어 메모리도 정렬 알고리즘을 사용한것보다 덜 먹었다는게 충격. 단순한게 가장 좋을 때가 있구나. 근데 지금은 연습이라서 제출했다쳐도 코테에 가서도 이렇게 제출할 수 있을까? 알고리즘 구현이 안되면, 이렇게라도 제출하기.. 얻어 걸릴 수 도 있잖아?

🌿메모리 : 125204KB, 시간 : 724ms

💡 풀이자 : 본인

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		boolean[] arr = new boolean[2000001];
		int T = Integer.parseInt((br.readLine()));
		for(int i = 0; i<T; i++) {
			arr[Integer.parseInt(br.readLine())+1000000] = true;
		}
		for(int i = 0; i<arr.length; i++) {
			if(arr[i]) {
				sb.append(i-1000000).append("\\n");
			}
		}
		System.out.print(sb.toString());
	}
}

---

Collection를 사용해서 정렬했다. 특이 사항 없음

🌿메모리 : 335512KB, 시간 : 3000ms

💡 풀이자 : tkdrl8908

import java.util.*;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		StringBuffer bf = new StringBuffer();
		
		int N = sc.nextInt();
		
		ArrayList<Integer> list = new ArrayList<>();

	    for(int i=0;i<N;i++){
	    	list.add(sc.nextInt());
	    }
	    
	    Collections.sort(list);
	    
	    for(int i : list) {
	    	bf.append(i+"\\n");
	    }
	    System.out.println(bf.toString());
	}
}

---

Conclusion

• 병합 정렬 자체는 좀 난이도 있는 편이다. 재귀, 투 포인터에 대한 개념이 잡혀있어야 이해하기 수월할 것으로 보인다.
• 굳이 알고리즘을 구현하지 않아도, Boolean형 배열을 활용해서도 풀 수 있다. 어쩌면 이게 가장 적합한 풀이방식이다.