가장 큰 수 (프로그래머스) [JAVA]

 

 

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수

문제 설명

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

 

풀이

문제의 이해는 빠르게 했다. 숫자를 앞으로 이었을때와 뒤로 이었을때 더 큰게 무엇인지 정해서 그대로 정렬을 하면 되겠다고 생각했다.
우선 나는 자리수에 집중했다. 숫자의 크기와 상관없이 계속 큰 자리수를 유지하는 수가 앞에 올수록 좋다고 생각했다.
우선 각 숫자들의 자릿수를 계산하여 2차원 배열에 저장해놓는다. (이때 12 -> 1 2 1 2 로 저장!!!!!)
이후 비교함수에선 두 숫자의 자릿수를 하나씩 비교해나가는데, 모든 자릿수가 동일하면 (10과 100, 10이 유리) 숫자 크기를 비교해서 더 큰쪽을 불리하게 하였다.
이 비교함수를 바탕으로 삽입정렬을 통해 숫자를 정렬하였는데, 이때 직접 숫자가 저장된 배열을 정렬해버리면 자릿수를 저장해놓은 캐시의 인덱스와의 연결이 끊어지기 때문에, 배열에 저장된 숫자의 인덱스를 저장한 배열을 정렬하였다.
오름차순으로 정렬하고, 정답을 역순으로 붙여줬다.
String으로 계속 concat하면 새로운 객체를 계속 생성하는 것이라, StringBuilder의 append를 사용한 것이 훨씬 빨랐다.

 

코드

class Solution {
	static int numberarrays[][];
	static int index[];
	static int MAX = 4;
    public String solution(int[] numbers) {
    	
    	numberarrays = new int[MAX][numbers.length];
    	
    	for(int i=0; i<MAX; i++) {
    		for(int j=0; j<numbers.length; j++) {
    			numberarrays[i][j] = getPositionNum(numbers[j], i);
    		}
    	}
    	
    	index = new int[numbers.length];
    	for(int i=0; i<numbers.length; i++) {
    		index[i] = i;
    	}
    	
    	StringBuilder sb = new StringBuilder();
    	InsertionSort(numbers);	
    	
    	boolean isZero;
    	if(numbers[index[numbers.length-1]] == 0) {
    		isZero = true;
    	}
    	else {
    		isZero = false;
    	}
    	
    	
        for(int i=numbers.length-1; i>=0; i--) {
        	
        	if(isZero) {
        		sb.delete(0, sb.length());
        		sb.append(Integer.toString(numbers[index[i]]));
        	}
        	else {
        		isZero = false;
        		sb.append(Integer.toString(numbers[index[i]]));
        	}
        }      
        return sb.toString();
    }
    
    public static int getPositionNum(int number, int posx) {
    	String s = Integer.toString(number);
    	
    	if(s.length() <= posx) {
    		//return s.charAt(s.length()-1)-48; 첨엔 멍청하게 1234444444 이렇다고 생각함
    		return s.charAt(posx % s.length())-48;
    	}
    	else {
    		return s.charAt(posx)-48;
    	}
    }
    
    
    public static boolean Compare(int indexa, int indexb, int numbers[]) {
    	for(int i=0; i<MAX; i++) {
    		if(numberarrays[i][indexa] > numberarrays[i][indexb]) {
    			return true;
    		}
    		else if(numberarrays[i][indexa] < numberarrays[i][indexb]){
    			return false;
    		}
    	}
    	if(numbers[indexa] < numbers[indexb]) return true;
    	return false;
    }
    
    public void InsertionSort(int[] numbers) {
    	int y;
    		for(int x=1; x<numbers.length; x++) {       	
        		int standardkey = index[x];
        		for(y= x-1; y>=0; y--) {
        			if(Compare(standardkey, index[y],numbers)) {
        				break;
        			}
        			
        			index[y+1] = index[y];
        		}
        		index[y+1] = standardkey;
        	}
    }
}

 

결과

 

복기

class Solution {
    public String solution(int[] numbers) {
    	String answer = "";
    	Sortnumbs(numbers);
    	boolean isZero;
    	if(numbers[numbers.length-1] == 0) {
    		isZero = true;
    	}
    	else {
    		isZero = false;
    	}
    	
    	
        for(int i=numbers.length-1; i>=0; i--) {
        	if(isZero) {
        		answer = Integer.toString(numbers[i]);
        	}
        	else {
        		isZero = false;
        		answer = answer.concat(Integer.toString(numbers[i]));
        	}
        }      
        //System.out.println(answer);   
        return answer;
    }
    
    public void Sortnumbs(int[] numbers) {
    	int y;
    	
    	for(int x=1; x<numbers.length; x++) {
    		int standard = numbers[x];
    		
    		for(y = x-1; y>=0; y--) {
    			if(Mysort(standard,numbers[y])) {
    				break;
    			}
    			numbers[y+1] = numbers[y];
    		}
    		numbers[y+1] = standard;
    		
    		//printArray(numbers);
    	} 	
    }
    
    
    public boolean Mysort(int a, int b) {
    	String afirst = Integer.toString(a)+Integer.toString(b);
    	String bfirst = Integer.toString(b)+Integer.toString(a);
    	//System.out.println(Integer.parseInt(afirst) + " " + Integer.parseInt(bfirst));
    	
    	if(Integer.parseInt(afirst) > Integer.parseInt(bfirst)) {
    		return true;
    	}
    	else {
    		return false;
    	}
    }
    
    public void printArray(int[] numbers) {
    	for(int i=0; i<numbers.length; i++) {
    		System.out.print(numbers[i] + " ");
    	}
    	System.out.println("\n");
    }
    
}

정말 쉬운 문제지만.. 시행착오를 너무 많이 겪은 문제였다..
처음엔 일일히 자릿수를 계산하는 메소드를 사용했으나 시간초과가 나서, 어차피 1000이하의 자연수 100,000개이므로 4 * 100,000의 배열을 만들어버리기로 작정하고 이차원 배열 numberarrays(캐시라 칭하겠다)를 만든 뒤 거기다 저장하면 좋겠다고 생각했다.
그리고 이 numberarrays를 삽입정렬을 활용해서 대소 비교를 하자 생각했는데 치명적인 문제가 발생했다.
삽입정렬을 해서 정렬을 하면, 이 2차원의 자리수를 기록해둔 캐쉬 역시 원래 인덱스에 맞게 같이 정렬해줘야 한다.. 매번 4번의 추가 연산이 필요했던 것이다.
이를 막으려고 숫자의 주소를 저장한 배열인 index[]를 또 선언해서 캐시의 주소에 숫자의 주소를 저장한 배열을 주소로 하는 웃긴 모양으로 참조해나아갔다...
여기서 또 놓치던 부분이, 만약 전부 0이면 값이 0으로 나와야 하지만, 0000..이런꼴로 나와버리는 것이었다.
더 좋은 방법이 있을 것 같지만, 너무 지쳐버려서 그냥 bool값으로 일일히 체크하게 만들었다.
그래도 계속되는 오답에, 괜히 자릿수로 까불지 말고 그냥 Int -> String + String -> Int로 대소비교해버리자 하고 그렇게 짰다.
하지만 시간초과를 맞았다... (이때 정답을 String.concat으로 출력해서 시간초과가 났을 수 도 있다..)
절망하며 다시 첫번째 방법으로 기어들어간 내가 찾아낸 또다른 오류는
10 100 일때 단순히 자릿수 계산만 한다면 10010으로 되어버리는 경우였다.
이 방법을 비교할때 모든 자릿수가 동일하게 나오면, 숫자 전체를 비교해버리는 방법으로 무식하게 해결했다.
그래도 1~6번을 내리 틀려버려서 절망하다 찾아낸 치명적인 오류는
지금까지 바보같이 34였으면 3 4 4 4 로 자릿수가 떨어지겠다고 생각한 것이었다. 34면 3434가 맞다. (14 142 < 142 14)
하.. 그래서 그 부분을 나머지 연산을 써서 수정해서 새벽 5시에 겨우 탈출하게 되었다.