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

[가장 큰 수]

https://programmers.co.kr/learn/courses/30/lessons/42746

---

문제 재정의:

numbers배열이 주어짐 (input)

numbers 배열에 있는 숫자를 조합하여 가장 큰 수를 만들어 '문자열로' return

numbers의 길이는 1 이상 100,000 이하, numbers의 원소는 0 이상 1,000 이하

---

예외 테스트 케이스

0, 0, 0, 0 -> 0

0, 1000, 0, 0 -> 100000

12, 121 -> 12121

21, 212 -> 21221

[0,0,0,1000]
[0,0,1000,0]
[1000,0,0,0]

틀리기 쉬운 입출력 예제 

(출처:https://stroot.tistory.com/114[Strong Root])

입력	출력
{40, 403} {40, 405} {40, 404} {12, 121} {2, 22, 223} {21, 212} {41, 415} {2, 22} {70, 0, 0, 0} {0, 0, 0, 0} {0, 0, 0, 1000} {12, 1213}	40403 40540 40440 12121 223222 21221 41541 222 70000 0 1000000 121312

 

---

구현할 때 참고한 사이트

• x자릿수 쪼개서 저장하는 법

https://hashcode.co.kr/questions/1797/%EC%9E%90%EB%B0%94%EB%A5%BC-%EA%B3%B5%EB%B6%80%ED%95%98%EA%B3%A0-%EC%9E%88%EC%8A%B5%EB%8B%88%EB%8B%A4-%EC%A0%95%EC%88%98%EB%A5%BC-%EB%B0%B0%EC%97%B4%EB%A1%9C-%EC%A0%80%EC%9E%A5%EC%9D%84-%EC%96%B4%EB%96%BB%EA%B2%8C-%ED%95%98%EC%A3%A0>

• int형 숫자의 자리수 구하기

String형 문자열의 길이는 length 함수를 이용해서 쉽게 구할 수 있지만, int형 숫자의 자릿수를 구할 때는 수학적 함수를 사용해야 한다.

(int)(Math.log10(num)+1)

https://jess2.tistory.com/103

int num = 3648;
int length = (int)(Math.log10(num)+1);

System.out.println("길이 : " + length);

• 자바 정렬 Comparable, Comparator, Sort() 확실히 알기

https://javaplant.tistory.com/15
https://cwondev.tistory.com/15

• 내 코드에 사용된 comparator

---

생각한 방법

만약 input이 9, 30, 34라면

 

9	9	-1	-1
30	3	0	-1
34	3	4	-1

처럼 각 숫자의 자릿수를 쪼개서 2차원 배열을 만드는 것임

2열을 sort 하고 -> 그다음 3열을 sort 하는 방식

 

 

 

- 2차원 배열 만드는 코드

//split 해서 각 행에 각 자리의 숫자 집어넣기. (숫자가 없는 곳은 -1을 집어넣음)

/*
자리수 체크하는 코드
public static int check(int x){
        return (int)(Math.log10(x)+1);
    }
*/
        for(int j=0;j<numbers.length;j++){
            temp=v[j][0];
            cases=check(temp);
            switch(cases){
            case 1 : //1의 자리
                v[j][1]=temp;
                v[j][2]=-1;
                v[j][3]=-1;
                break;
            case 2 : //10의 자리
                a=Integer.toString(temp);
                v[j][1]=a.charAt(0)-'0';
                v[j][2]=a.charAt(1)-'0';
                v[j][3]=-1;
                break;
            case 3:  //100의 자리
                a=Integer.toString(temp);
                v[j][1]=a.charAt(0)-'0';
                v[j][2]=a.charAt(1)-'0';
                v[j][3]=a.charAt(2)-'0';
                break;

            }
        }

 

 

그 대신 sort 할 때 행이 다 같이 움직여야 함. (comparator를 이용함)

- 정렬하는 부분 코드

public static void ArraysSort2(int[][] arr, final int index_num, int from, int to){
        Arrays.sort(arr,from,to+1, new Comparator<int[]>(){
            public int compare(final int[] entry1, final int[] entry2){

                final int time1=entry1[index_num];
                final int time2=entry2[index_num];
                return Integer.compare(time2,time1);
            }
        });
    }

매개 변수 설명: ArraysSort2(배열 이름, 몇 열을 정렬할 건지, 몇 행부터, 몇 행까지 정렬할 건지)

from과 to 가 있는 이유) 33, 35, 9를 정렬해야 할 때 첫 자릿수가 '3'으로 같은 애들만 비교하기 위해 from 과 to를 설정함

 

 

 

- 앞 자리수가 같은 경우의 행을 반환(30과 34의 경우)하는 코드

그럼 위 예제처럼 앞 자릿수가 '3'으로 같은지 비교하는 메서드는 아래와 같음. from과 to를 배열에 저장해 반환

 public static int[] isSame(int[][] a, int x){
        int[] from_to = new int[a.length];
        int from=0, to=0;

        int pivot=a[0][x];
        for(int i=1;i<a.length;i++){
            if(pivot==a[i][x]){
                to++;
            }
            else{
                from=i;
                pivot=a[i][x];
                to=i;
            }
        }

        from_to[0]=from;
        from_to[1]=to;
        return from_to;
    }

---

문제점 (예외가 너무 많이 발생)

단적인 예로)

만약 input이 30, 34, 3이라면

'34-3-30' 이어야 하는데

내 코드에 의하면 '34-30-3'이 됨

-> 한 자릿수를 중간에 끼워 넣을 수 있는 경우의 수를 생각하지 못함.

 

 

sol1)

스터디 팀원분이 2차원 배열. 일의 자릿수에 -1 말고 그 수를 채우자는 아이디어를 주심

sol1- prob)

30, 3, 34는 '34330'으로 잘 정렬됨

40, 403은 틀린 답 '40340'이 나옴

__이뿐만 아니라 예외가 많이 발생해 복잡해져 버리기,,, __

 

 

내가 생각한 아이디어는 뒤집어엎어버리기로 함

---

https://developerdk.tistory.com/24 님의 해답을 봄

 

-> int형을 일단 string을 변경함

 

-> comparator 이용해서 정렬함( 2개씩 더한 후, 비교해서 정렬되는 방식)

 

-> 0000은 0 이 되게 예외처리해줌

이 방법은 코드가 50줄도 안 나온다...

---

반성

1. sort(), comparator, comparable를 사용한다는 것까진 왔으나, 이에 대해 깊이/이해하지 않고, 더 어렵게 생각해서 풂.

 

 

2. 그리고 string형 합칠 때 +가 아닌, String.valueOf()를 사용하는 게 더 효율적이라는 것을 깨달음

 

 

"java convert int to string"

char c = 'a';
String s = String.valueOf(c);             // fastest + memory efficient
String s = Character.toString(c);
String s = new String(new char[]{c});
String s = String.valueOf(new char[]{c});
String s = new Character(c).toString();
String s = "" + c;                        // slowest + memory inefficient

https://developerdk.tistory.com/24

참고 : https://stackoverflow.com/questions/8172420/how-to-convert-a-char-to-a-string