[프로그래머스 : 레벨 2] 가장 큰수 : Array.sort 와 퀵정렬 (Java)

이번 문제는 문제 자체는 쉬웠으나 내가 처음에 이상한 방식으로 풀었어서 답을 풀지 못했다.

근데 답을 알고나니 엄청 간단한 문제였다.

역시 모든건 규칙을 찾아야 하고 문제가 원하는게 뭔지 정확하게 알아야 한다.

이제 문제를 보자.

 

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbers	return
[6, 10, 2]	"6210"
[3, 30, 34, 5, 9]	"9534330"

 

문제 해석

수의 조합중 제일 큰수를 골라라.

 

 

사실 이 문제는 다를거 없이 앞의 자리수가 큰애가 제일 먼저 오게 된다.

 

[6, 10, 2]

이렇게 되어 있을때 10이 6보다 큰건 사실이지만 둘을 서로 바꾸게 된다면 

610과 106으로 비교를 하게 되면 610이 더크다.

이처럼 앞의 자리수가 더 큰 수가 먼저오게 된다.

 

이걸 생각하고 아래의 소스를 보자.

 

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        String[] change = new String[numbers.length];
        
        //숫자로 받은 배열을 문자열로 바꿔줌
        for(int i = 0; i<numbers.length;i++) {
        	change[i] = Integer.toString(numbers[i]);
        }
        
        //여기서는 이제 해당 문자열을 비교하는 부분이다.
        Arrays.sort(change, (o1,o2)-> (o2+o1).compareTo(o1+o2));
        
        //0이 여러개인 경우 0만 나와야 하는데 0000이렇게 나올수 있기때문에
        if(change[0].equals("0")) return "0";
        
        for(int i = 0; i<change.length;i++) {
        	answer+=change[i];
        }
        
        return answer;
    }
}

 

위 소스같은 경우는 일단 int형 배열을 String형 배열에 담고

String 형 배열에서 수를 비교 했다.

 

각자의 수를 비교하는 부분은 

Arrays.sort(change, (o1,o2)-> (o2+o1).compareTo(o1+o2));

위와 같이 하였다.

 

change배열에서 두개의 String을 받아서 (o2+o1).compareTo(o1+o2)을 했다.

(o1+o2).compareTo(o2+o1)을 한 이유는 

뒤에 있는 수가 더 커야지만 자리를 바꾸기 때문이다.

 

compareTo() 메소드에 관해서는 내가 아래 링크에 설명해놨으니 확인하면 될것 같다.

https://wpioneer.tistory.com/101?category=1023662 

[Java] Comperator 와 Comperable

그래서 위의 소스로 채점을 하면 아래와 같이 나온다.

사진만 봐도 알수 있듯이 테스트 1,테스트2, 테스트3,테스트5,테스트6 은 엄청난 데이터를 가지고 테스트를 하는것을

알수 있다.

 

내가 이결 보여준 이유는 내가 위의 소스를 라이브러리를 사용하지 않고 직접 선택 정렬을 통해서 구현해봤다.

하지만 테스트 1,테스트2, 테스트3,테스트5,테스트6 에서 시간초과가 나왔다.

이를 해결 하기 위해선 시간복잡도가 더 낮은 정렬 알고리즘을 사용하여야 한다.

그래서 내가 사용한것은 퀵 정렬 이라는 알고리즘이다.

 

소스는 아래와 같이 했다.

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        String[] change = new String[numbers.length];
        
        //숫자로 받은 배열을 문자열로 바꿔줌
        for(int i = 0; i<numbers.length;i++) {
        	change[i] = Integer.toString(numbers[i]);
        }
        
        //여기서는 이제 해당 문자열을 비교하는 부분이다.
//        Arrays.sort(change, (o1,o2)-> (o2+o1).compareTo(o1+o2));
        
        quikSort(change);
        //0이 여러개인 경우 0만 나와야 하는데 0000이렇게 나올수 있기때문에
        if(change[0].equals("0")) return "0";
        
        for(int i = 0; i<change.length;i++) {
        	answer+=change[i];
        }
        
        return answer;
    }
    
	//1. 큇소트를 호출했을때 시작 부분
	public void quikSort(String[] arr) {
		int start = 0;
		int end = arr.length - 1;
		quikSort(arr,start,end);
	}
	//2. 파티션을 나누는 함수를 시작점과 끝점을 가지고 호출 하는 부분 (quikSort() 오버로딩함)
	public void quikSort(String[] arr, int start, int end) {
		int part2 = part(arr,start,end);
		
		if(start < part2 - 1) { //정렬되서 나눠진게 끝에 한개가 아닌애들
			quikSort(arr,start,part2-1);
		}if(part2 < end) { //파티션의 시작이 끝보다 작을때 재귀호출 들어감
			quikSort(arr,part2,end);
		}
	}
	//3. 서로 특정 기준점을 통하여서 파티션을 나누는 부분
	public int part(String[] arr, int start, int end) {
		String pivot = arr[(start + end) / 2]; //중간지점의 값을 피봇 지점으로 지정함
		while(start <= end) { //서로를 지나칠때 빠져나온다.
			while(Integer.parseInt(arr[start]+pivot) > Integer.parseInt(pivot + arr[start]))
				start++;
			while(Integer.parseInt(arr[end]+pivot) < Integer.parseInt(pivot+arr[end]))
				end--;
			if(start<=end) {
				swap(arr,start,end);
				start++;
				end--;
			}
		}
		return start;
	}
	
	//4. 서로 위치를 바꿔주는 부분
	public void swap(String[] arr, int start, int end) {
		String temp = arr[start];
		arr[start] = arr[end];
		arr[end] = temp;
	}
}

사실 이 부분은 퀵정렬 알고리즘 부분에서 파티션 나누는 부분의 조건만 수정한것이다.

해당 소스를 보고 이해가 안간다면 내가 퀵정렬알고리즘에 대하여 정리한 부분을 확인해보면 된다.

 

https://wpioneer.tistory.com/103

[자료구조] 퀵정렬 (Java)

 

위 소스로 다시 해보니 아래와 같은 결과가 나왔다.

 

느낀점

1. 선택정렬은 구현하기 쉽지만 시간복잡도가 높다.

2. 퀵정렬은 정말 빠르다.

3. 라이브러리 사용이 편하긴한거같다... 하지만 정렬알고리즘을 구현할줄은 알아야 한다.

4. 답까지 도달하는데 필요한 규칙같은것을 찾아야 한다.