프로그래머스<가장 큰 수>-2차(2022.09.15수정)-3차(2022.09.16풀이 참고 후 code review)

문제 설명

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"

class Solution implements Comparable<Solution> {
    String answer = "";
    int firstindex;
    public String solution(int[] numbers) {
        this.firstindex = firstindex;
        
    }
    public int compareTo(Solution s){
        for(int i=0; i<numbers.length; i++){
            if(this.numbers[i] > s.numbers[i]){
                return 1;
            }
            else{
                return -1;
            }
        }
    }
}

사용자 정의 관련 내용을 다시 공부하며 코드를 작성하던 중, 

문제출제자의 의도를 다시 파악해보는 시간을 가졌다. 

문제의 카테고리는 정렬이었기에, 사용자 정의를 사용하기보다는 정렬 알고리즘을 사용하기로 결정. 

코드를 수정하는 과정을 겪었다 

 

2차코드)

 

import java.util.Arrays;

class Solution {
    public String solution(int[] numbers) {
        solution(numbers, numbers.length);
        String answer = "";
        answer = Arrays.toString(numbers).replace(", ","").replace("[","").replace("]","");
        //int배열을 공백없는 정수열로 만드는 과정
        return answer;
        
    }
    public static void solution(int[] numbers, int size){
        for(int i=0; i<size-1; i++){
            int max_index = i;
            for(int j=i+1; j<size; j++){
                String stri = Integer.toString(numbers[max_index]);
                int ii = Character.getNumericValue(stri.charAt(0));
                //index i의 값의 0번째 index값을 비교하여 큰 것이 무조건 앞으로 오게 
                String strj = Integer.toString(numbers[j]);
                int jj = Character.getNumericValue(strj.charAt(0));
                //위와 동일 
                if(jj>ii){
                    max_index = j;
                }
            
            }
            
            swap(numbers, max_index, i);
        }
    }
    public static void swap(int[] numbers, int i, int j){
        int temporary = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temporary;
    }
}

 

어느 정도 정성적인 정렬 알고리즘을 구현하였고 코드를 제출해보았다.

그 결과 ,

1개는 성공하였지만, 1개의 테스트 케이스는 통과하지 못했다. 

어떤 값이 return 됐는지를 보니 코드에서 부족한 부분이 눈에 보이기 시작했다. 

문제의 조건을 잘 읽어보면

numbers의 원소는 0 이상 1,000 이하입니다 

라는 문구가 있다. 예시로 30와 3처럼 0번째 index의 값이 같더라도, 더 큰 값을 만들 수 있는 3이 오고 30이 와야한다는 말이다.

첫번째 index값이 같다면, 문자열의 길이도 고려를 해줘야한다는 의미로 해석할 수 있다.

문자열의 길이가 짧은 것을 앞으로 보내야 더 큰 수를 만들 수 있기에 이 과정을 구현하는 코드를 작성하기로 하였다. 

 

막상 위 설명대로 코드를 구현하려 하니 고려해야할 점들이 몇가지 있었다. 크게 구분지어서 생각하면 

 

1. 길이가 같을 때와 다를 때를 먼저 정해서 비교하기
2. 길이가 같을 때는 숫자의 대소관계를 비교해서 return하기
3. 길이가 다를 때는 더 길이가 긴 숫자의 마지막 index와 더 짧은 숫자의 0번째 index를 비교해서 큰 숫자를 return하기

이렇게 코드를 구현한다면 정상적으로 답이 나올 것 같다. 

구현 중에 있는 지금, 연등시간이 곧 종료되기 때문에 내일 문제를 완벽하게 해결해낼 수 있을거라 믿으며 마치도록 한다

 

3차코드)

 

import java.util.Arrays;

class Solution {
    public String solution(int[] numbers) {
        solution(numbers, numbers.length);
        String answer = "";
        answer = Arrays.toString(numbers).replace(", ","").replace("[","").replace("]","");
        //int배열을 공백없는 정수열로 만드는 과정
        return answer;
        
    }
    public static void solution(int[] numbers, int size){
        for(int i=0; i<size-1; i++){
            int max_index = i;
            for(int j=i+1; j<size; j++){
                //index i의 값의 0번째 index값을 비교하여 큰 것이 무조건 앞으로 오게 
                String stri = Integer.toString(numbers[max_index]);
                int ii = Character.getNumericValue(stri.charAt(0));
                String strj = Integer.toString(numbers[j]);
                int jj = Character.getNumericValue(strj.charAt(0));
                //index i의 값의 1번째 index값을 비교하여 큰 것이 무조건 앞으로 오게 
                String stri1 = Integer.toString(numbers[max_index]);
                int ii1 = Character.getNumericValue(stri.charAt(1));
                String strj1 = Integer.toString(numbers[j]);
                int jj1 = Character.getNumericValue(strj.charAt(1));
                //index i의 값의 2번째 index값을 비교하여 큰 것이 무조건 앞으로 오게
                //원소는 1000이하이기 때문에 2번째까지만 비교해도 됨 
                String stri2 = Integer.toString(numbers[max_index]);
                int ii2 = Character.getNumericValue(stri.charAt(2));
                String strj2 = Integer.toString(numbers[j]);
                int jj2 = Character.getNumericValue(strj.charAt(2));
                //위와 동일 
                if(jj>ii){
                    max_index = j;
                }else if(jj.equals(ii)&&numbers[i].length.equals(numbers[j].length)){
                    if(numbers[j]>numbers[i]){
                        max_index = j;
                    }
                    else {
                        max_index = i;
                    }
                }
                else {
                     String stri2 = Integer.toString(numbers[max_index]);
                     int ii2 = Character.getNumericValue(stri.charAt(2));
                     String strj2 = Integer.toString(numbers[j]);
                     int jj2 = Character.getNumericValue(strj.charAt(2));
                    
                }
                    
//                 }else if(numbers[])){
//                     String lastindex = Integer.toString(numbers[j]);
//                     int forlastindex = Character.getNumericValue(lastindex.charAt(lastindex.length()));
//                     if(numbers[i].length()>numbers[j].length&&)
//                 
                //else if문에서 구현해하는 기능들
                //경우의 수를 나열해보자 
                // 1.jj와ii가 같을 때 그 다음 인덱스 값을 비교 
                // 2. 같으면 그 다음 인덱스 비교 큰거 return하기  
                // 3. 길이가 다른데 다음 index값이 그 전 index값보다 크면 더 긴거 return하기 
                // else if(jj.equals(ii))
                //*길이가 같을 때와 다를 때는 먼저 정해서 비교하자**!//
                //길이가 같을 때는 진짜 그냥 순수 숫자의 크기를 비교해서 return하기
                //길이가 다를 때는 더 큰 숫자의 마지막 index와 더 짧은 숫자의 0번째 index를 비교해서 큰 숫자를 return하기 !! 
                }
            }
            swap(numbers, max_index, i);
        }
    }
    public static void swap(int[] numbers, int i, int j){
        int temporary = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temporary;
    }
}

*아직 정리가 된 코드가 아니며 주석처리도 되게 많기 때문에 난잡해보는 것 같다(실제로도 clean-code가 아닐 가능성 농후)*

 

 

3차까지 작성된 코드를 계속해서 변형시켜보기도 하였고, 발생할 수 있는 여러 경우의 수에 관련된 코드를 다 넣어보았지만, 작동이 안되거나 되더라도 런타임에러를 발생시키기 일쑤였다. 

 

이에 대한 해결책으로 조합(permutation)을 사용하기라는 대안을 내새웠지만, 요소의 개수가 매우 클 수도 있다는 점을 고려하면 코드를 작성하더라도 Runtime error가 무조건 발생할 수 밖에 없을 것이라고 확신이 들었다.

 

결국 다른 사람의 풀이를 참고하였고, 다른 접근법으로 해결했다면 훨씬 더 쉬웠을만한 문제였다. 

 

 

뜬 눈으로 꾸는 꿈님의 코드)

 

import java.util.Arrays;

public class Solution {
    public String solution(int[] numbers) {
        String[] arr = new String[numbers.length];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = String.valueOf(numbers[i]);
        }

        Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
        
        if (arr[0].equals("0")) {
           return "0";
        }

        StringBuilder answer = new StringBuilder();

        for (int i = 0; i < arr.length; i++) {
            answer.append(arr[i]);
        }


        return answer.toString();
    }
}

출처 : https://bellog.tistory.com/m/170

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

 

여기서 주목할만한 코드는 

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

부분이었다. 

두 숫자가 각자 앞,뒤일 때 2가지 상활에 대해 더 큰 순으로 정렬해나가는 기능을 구현한 람다식이다. 

그 후, 효율성을 위해 StringBuilder를 사용하여 문자열을 합쳐주고 return하였다. 

 

 

느낀점

 

조금 더 생각을 확장시킬 필요성이 있는 것 같다. level 1 문제는 그냥 해결하는데에 집중을 하였다면, level2부터는 자료구조 및 알고리즘의 내용을 적용시키며 해결하려고 노력중이기에, 나도 모르게 뭔가 정석적인 방법만을 생각하고 유연한 생각을 하지 않고 있는 것 같기도 하다. 조금 더 여러가지 방법들을 생각하며 문제 해결에 임해야겠다. 

그래도 뿌듯한 점은 하나라도 더 배웠다는 점.