고민의 흔적

16번 문제 버블 소트

잘못된 풀이

import java.io.*;
import java.util.*;

public class Baek1377 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		int [] arr = new int[n +1];
		for(int i = 1; i <= n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		boolean change = false;
		
		for(int i = 1; i <= n + 1; i++) {
			change = false;
			for(int j = 1; j <= n - i; j++) {
				if(arr[j] > arr[j + 1]) {
					change = true;
					int swap = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = swap;
				}
			}
			if(change == false) {
				System.out.println(i);
				break;
			}
		}
		
	}

}

내가 떠올린 풀이 해설

C++ 예시로 보여준 코드를 그대로 적용해서 풀었습니다.

정확한 풀이

import java.io.*;
import java.util.*;

public class Baek1377 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		Sort [] arr = new Sort[n];
		for(int i = 0; i < n; i++) {
			arr[i] = new Sort(Integer.parseInt(br.readLine()), i);
		}
		Arrays.sort(arr);
		int max = 0;
		for(int i = 0; i < n; i++) {
			if(max < arr[i].index - i) {
				max = arr[i].index - i;
			}
		}
		System.out.println(max + 1);
	}
}

class Sort implements Comparable<Sort> {
	int value;
	int index;
	public Sort(int value, int index) {
		this.value = value;
		this.index = index;
	}
	@Override
	public int compareTo(Sort o) {
		return this.value - o.value;
	}
}

문제점

이 문제는 N의 최대 범위가 500,000이므로 버블 정렬로 문제를 풀면 시간 초과가 나온다. 각 데이터마다 정렬 전 index값에서 정렬 후 index값을 빼고 최댓값을 찾는다. 그리고 swap이 일어나지 않은 반복문이 한번 더 실행되는 것을 감안해 max에 + 1을 해준다.

17번 문제 소트 인사이드

내가 떠올린 풀이 해설

N의 크기가 1,000,000,000 보다 작거나 같은 자연수이다. 자연수를 받아 자릿수 별로 정렬하는 문제이므로 숫자를 String으로 받은 후 정렬을 List에 Arrays.stream(arr).boxed().collect(Collectors.toList()); 로 담아 Collections.sort(integer, Comparator.reverseOrder()); 를 이용해 내림차순 정렬을 진행했다.

정확한 풀이

import java.util.*;
import java.util.stream.Collectors;
public class Baek1427 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		
		int []arr = new int[str.length()];
		for(int i = 0; i < str.length(); i++) {
			arr[i] = str.charAt(i) - 48;
		}
		List<Integer> integer = Arrays.stream(arr).boxed().collect(Collectors.toList());
		Collections.sort(integer, Comparator.reverseOrder());
		
		for(int i = 0; i < str.length(); i++) {
			System.out.print(integer.get(i));
		}
		
	}

}

18번 문제 ATM

내가 떠올린 풀이 해설

N의 최댓값이 1,000이고 시간제한이 1초이므로 시간 복잡도가 O(n^2) 이하인 정렬 알고리즘 아무거나 사용해도 된다.

Arrays.sort로 정렬을 하고 인출 시간을 sum에 더하고 total 걸린 시간을 구하기 위해 sum을 다시 total에 더했다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek11399 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int []arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		int sum = 0;
		int total = 0;
		for(int i = 0; i < n; i++) {
			sum += arr[i];
			total += sum;
		}
		System.out.println(total);
	}

}

19번 문제 K번째 수

내가 떠올린 풀이 해설

N의 최대 범위가 5,000,000이므로 O(nlogn)의 시간 복잡도로 정렬을 해야 된다. 간단하게 Arrays.sort로 풀었다.

정확한 풀이

import java.io.*;
import java.util.*;

public class Baek11004 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int[] arr = new int[n];
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		System.out.println(arr[m - 1]);
	}

}

20번 문제 수 정렬하기 2

내가 떠올린 풀이 해설

N의 최대 범위가 1,000,000이므로 O(nlogn)의 시간 복잡도로 정렬을 수행해야 된다. Collections.sort을 이용해서 해결했다.

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek2751 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer bf = new StringBuffer();
		int n = Integer.parseInt(br.readLine());
		int [] arr = new int[n];
		ArrayList<Integer> list = new ArrayList<>();
		for(int i = 0; i < n; i++) {
			list.add(Integer.parseInt(br.readLine()));
			
		}
		Collections.sort(list);
		for(int i = 0; i < n; i++) {
			bf.append(list.get(i) + "\\n");
		}
		System.out.println(bf.toString());
	}

}

문제점

Arrays.sort 로 쓰면 시간 초과가 난다. Arrays.sort() 의 경우 dual-pivot Quicksort 알고리즘을 사용한다. 물론 평균 시간 복잡도가O(nlogn) 이고 매우 빠른 알고리즘이다. 그러나 최악의 경우 시간 복잡도는O(n2) 이다. Collections.sort() 은 Timsort이다. Timsort 의 경우 합병 및 삽입 정렬 알고리즘을 사용한다. 두 가지가 섞여있는 정렬 알고리즘을 hybrid sorting algorithm이라고 하는데, 합병 정렬은 최선, 최악 모두 O(nlogn)을 보장하고 삽입 정렬은 최선의 경우는 O(n) , 최악의 경우는 O(n2)이다. 그리고 두 정렬 모두 안정 정렬이기 때문에 Timsort를 hybrid stable sorting algorithm이라고도 한다. 즉, 합병 정렬의 최악의 경우와 삽입 정렬의 최선의 경우를 짬뽕한 알고리즘이 Timsort라는 것이다. 

-참고 블로그 : https://st-lab.tistory.com/106

오늘의 회고

오늘은 Do it 알고리즘 책에 있는 문제를 풀었습니다. 정렬에 관한 기본적인 문제 5문제를 풀었고 그동안 문제를 풀면서 Arrays.sort, Collections.sort를 많이 사용하였는데 시간 복잡도와 어떤 정렬을 사용하는지 모르고 사용하였습니다. sort에 대해 오늘 정렬 문제를 풀면서 학습하게 되었습니다. 정렬에 관한 알고리즘을 공부하고 시간 복잡도를 고려에 적절한 알고리즘을 사용해야 될 것 같습니다.