[알고리즘] 프로그래머스 가장 큰 수 -정렬-

 

 

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

프로그래머스

 

프로그래머스의 가장 큰 수를 풀었다.

처음에는 별생각없이 자리수 비교해줄려고 다음과 같이 비교해주었었다.

import java.util.ArrayList;
import java.util.Collections;

class Solution {

    public static void main(String[] args) {
        Solution solution= new Solution();
        solution.solution(new int[]{40,404});
    }

    public String solution(int[] numbers) {
        StringBuilder answer = new StringBuilder();
        ArrayList<BiggestNum> biggestNumArrayList = new ArrayList<>();
        for (int num : numbers) {
            biggestNumArrayList.add(new BiggestNum(String.valueOf(num)));
        }
        Collections.sort(biggestNumArrayList);
        for (BiggestNum num : biggestNumArrayList) {
            answer.append(num.num);
        }
        System.out.println(answer);
        return answer.toString();
    }

    class BiggestNum implements Comparable<BiggestNum> {
        String num;

        BiggestNum(String num) {
            this.num = num;
        }

        @Override
        public int compareTo(BiggestNum o) {
            if (num.length() > o.num.length()) {
                for (int i = 0; i < o.num.length(); i++) {
                    // 자리값 서로 다를때
                    if (num.charAt(i) != o.num.charAt(i)) {
                        return o.num.charAt(i) - num.charAt(i);
                    }
                }
                for (int i = o.num.length(); i < num.length(); i++) {
                    if(num.charAt(i)  != num.charAt(0)){
                        return num.charAt(0) - num.charAt(i);
                    }
                }
            } else if (num.length() == o.num.length()) {
                for (int i = 0; i < o.num.length(); i++) {
                    if (num.charAt(i) != o.num.charAt(i)) {
                        return o.num.charAt(i) - num.charAt(i);
                    }
                }
            } else {
                for (int i=0; i < num.length(); i++){
                    // 자리값 서로 다를때
                    if (num.charAt(i) != o.num.charAt(i)) {
                        return o.num.charAt(i) - num.charAt(i);
                    }
                }
                for (int i = num.length(); i < o.num.length(); i++) {
                    if(o.num.charAt(i)  != o.num.charAt(0)){
                        return o.num.charAt(i) - o.num.charAt(0);
                    }
                }
            }
            return 0;
        }
    }
}

기본 테스트 케이스는 통과하였으나 제출하기시 11개중 4개의 테스트밖에 통과못했었다. 코드를 내가 짜고도 알아보기 힘들고 여러 예외사항을 처리하기 힘들어서 지우고 다시 생각했다.

 

 

 

 

숫자형 문자열 두개를 비교하는데 둘을 합쳤을 때 큰 쪽이 더 크다고 쉽게 비교할 수 있다라는 방법이 떠올랐다.

그래서 다음과 같이 비교하는 코드로 짯다. 0 의 입력 경우도 처리해주었다.

import java.util.ArrayList;
import java.util.Collections;

class Solution {

    /*public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(new int[]{0,0,0,110,1});
    }*/

    public String solution(int[] numbers) {
        StringBuilder answer = new StringBuilder();
        ArrayList<BiggestNum> biggestNumArrayList = new ArrayList<>();
        for (int num : numbers) {
            biggestNumArrayList.add(new BiggestNum(String.valueOf(num)));
        }
        Collections.sort(biggestNumArrayList);
        ArrayList<String> zeroList = new ArrayList<>();
        for (BiggestNum biggestNum : biggestNumArrayList) {
            if (biggestNum.num.startsWith("0")) {
                zeroList.add(biggestNum.num);
            } else {
                answer.append(biggestNum.num);
            }
        }
        for(String zero : zeroList){
            answer.append(zero);
        }
        return answer.toString();
    }

    class BiggestNum implements Comparable<BiggestNum> {
        String num;

        BiggestNum(String num) {
            this.num = num;
        }

        @Override
        public int compareTo(BiggestNum o) {
            String a = num + o.num;
            String b = o.num + num;
            return Integer.compare(Integer.parseInt(b), Integer.parseInt(a));
        }
    }
}

 

 

 

 

그러나 테스트11 케이스가 계속 틀렸다고 떴다. 계속 해도 분명 값이 잘 비교되고 잘 나오길래 프로그래머스 질문하기에 들어가봤다. 0,0,0,0,0 의 경우 000000 이 출력되는게 아니라 0이 출력되야한다는 글을 봤다. 

삽질을 많이 해서 살짝 짜증났다....(말장난인가 흠..)

그래서 마지막에 다음 코드를 추가했다.

 

// 000000 -> 0 출력되야함
        if(answer.toString().startsWith("0")){
            return "0";
        }else{
            return answer.toString();
        }

 

 

 

해당 케이스를 처리하여 통과한 최종 코드는 다음과 같다.

import java.util.ArrayList;
import java.util.Collections;

class Solution {

    /*public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(new int[]{0,0,0,110,1});
    }*/

    public String solution(int[] numbers) {
        StringBuilder answer = new StringBuilder();
        ArrayList<BiggestNum> biggestNumArrayList = new ArrayList<>();
        for (int num : numbers) {
            biggestNumArrayList.add(new BiggestNum(String.valueOf(num)));
        }
        Collections.sort(biggestNumArrayList);
        ArrayList<String> zeroList = new ArrayList<>();
        for (BiggestNum biggestNum : biggestNumArrayList) {
            if (biggestNum.num.startsWith("0")) {
                zeroList.add(biggestNum.num);
            } else {
                answer.append(biggestNum.num);
            }
        }
        for(String zero : zeroList){
            answer.append(zero);
        }

        // 000000 -> 0 출력되야함
        if(answer.toString().startsWith("0")){
            return "0";
        }else{
            return answer.toString();
        }
    }

    class BiggestNum implements Comparable<BiggestNum> {
        String num;

        BiggestNum(String num) {
            this.num = num;
        }

        @Override
        public int compareTo(BiggestNum o) {
            String a = num + o.num;
            String b = o.num + num;
            return Integer.compare(Integer.parseInt(b), Integer.parseInt(a));
        }
    }
}

 

 

 

댓글과 공감은 큰 힘이 됩니다..! 감사합니다