p42746.md

42746. 가장 큰 수

Summary

🙇‍♂️ URL : https://programmers.co.kr/learn/courses/30/lessons/42746
🤷‍♂️ Difficulty: ?
💆‍♂️ Submissions : Success

Source code

class P42746_Solution_Sort {
    public String solution(int[] numbers) {
        String answer = "";
        String[] strArray = new String[numbers.length];
        // 모든 정수형 배열을 문자열로 먼저 바꿔줌
        for(int i=0; i<numbers.length; i++) {
            strArray[i] = Integer.toString(numbers[i]);
        }

        // Comparator를 이용하여 sort 과정을 커스터마이즈
        // 인접한 두 문자열을 비교 -> 더 큰 문자열로 계속 정렬해줌
        Arrays.sort(strArray, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return ((s2+s1).compareTo(s1+s2));
            }
        });

        // 만약 문자열이 0으로 시작하면? -> 나머지도 모두 0이라는 이야기 -> 결과 값은 0
        if(strArray[0].equals("0")) {
            answer = "0";
        } else {
            for(int i=0; i<strArray.length; i++) {
                answer += strArray[i];
            }
        }
        return answer;
    }
}

How to Approach

처음에 이 문제를 DFS로 접근했다. 그리고 풀이도 완벽(?)했는데, 예시 케이스만 통과하고 실제 테스트케이스에서는 메모리부족+시간초과 오류를 마구 내뱉었다. 단순 정렬을 이용해서 구현해야겠다고 생각했는데, sort 함수를 내 입맛대로 커스터마이즈 하는 방법을 이해할 수 없었다.

그래서 정렬하는 부분은 다른 분이 열심히 풀어놓은 내용을 참조했다... comparator를 사용하면 간단하게 구현할 수 있었다.

정렬문제답게 내부 정렬을 이용해서 문제를 해결해야했다. Comparator를 사용하면 Sort하는 과정을 커스터마이즈 할 수 있는 것 같았는데, 연결된 두 문자들을 조합했을 때 더 큰 문자열(이걸 판단해주는 라이브러리도 너무 고맙고 신기했음)을 계속 만들어주면 되었다.

DFS를 이용한 문제 풀이(실패한 경우)

처음에 문제 풀이방식으로 접근한 DFS 소스코드이다. 특정 행을 시작으로 끝까지 탐색해서 모든 문자열을 연결하였을 때 해당 값을 리스트에 저장하고, 최대값을 마지막에 반환해주는 방식으로 구현하였다. 그리고 본 방식으로는 성공하지 못했다.

class P42746_Solution_DFS {
    public String solution(int[] numbers) {                
          // 들렸는지 안들렸는지 확인하는 부분
        boolean[] visited = new boolean[numbers.length];
        ArrayList<String> list = new ArrayList<>();

        for(int i=0; i<numbers.length; i++) {
            visited[i] = true;
              // 어차피 문자열로 최대값을 정렬할 수 있어서 바로 문자열로 구현했다.(메모리부족이 정수형태라서 일어나는 줄 알았다)
            dfs(numbers, visited, Integer.toString(numbers[i]), 1, list);
            visited[i] = false;
        }
        return Collections.max(list);
    }

    public void dfs(int[] numbers, boolean[] visited, String value, int count, ArrayList<String> list) {
        // 이어야 하는 모든 문자열을 다 연결하였다면 -> 리스트에 해당 문자열 저장
        if (count == numbers.length) {
            list.add(value);
            return;
        }
        for(int i=0; i<numbers.length; i++) {
            if(!visited[i]) {
                visited[i] = true;
                  // 새로 만난 행렬의 문자열을 계속 뒤에 저장해주면서 다음 칸으로 이동
                dfs(numbers, visited, value+numbers[i], count+1, list);
                visited[i] = false;
            }
        }
    }
}