Programmers - 숫자 짝궁 with JAVA

 

문제

문자열 X,Y가 주어졌을 때, X와 Y 중 겹치는 숫자를 활용해 만들 수 있는 최대값을 구하라

 

 

 

 

로직

1. 문자열은 각 자리가 0~9로 이루어져있다. 우선적으로, X 내부의 9의 개수, 8의 개수 등을 구하여 배열로 저장한다.

(연산 수 : 300만, 누적 : 300만)

2. Y를 체크하는데 만약 위에서 구한 배열에 해당 숫자가 0이라면 다음 숫자를 체크하고 0이 아니라면 1을 빼주고 결과 배열에 저장한다.

(연산 수 : 300만, 누적 : 600만)

3. 결과 배열을 9부터 0까지 확인하며 StringBuilder에 추가한다.

(연산 수 : 300만, 누적 : 900만)

 

고찰

- StringBuilder대신 + 연산자로 3번의 과정을 거쳐서 시간에서 넘쳤다.

- 기본적으로 String의 + 연산자는 n길이의 문자열을 추가하는데 O(n)의 시간복잡도를 갖고 StringBuilder의 append연산자는 시간 복잡도가 O(1)이다.

- 또한 String은 불변 객체이기에 +연산 사용시 매번 객체 생성, 메모리의 누적되어 위와같이 반복되는 연산을 사용시 O(N^2)의 시간 복잡도를 갖는다. 따라서, StringBuilder를 통해 해당 로직을 풀어나아가야 한다.

 

 

 

코드 1

import java.util.*;
class Solution {
    public String solution(String X, String Y) {
        String answer = "";
        int[] x_list = new int[10];
        for(char x : X.toCharArray()){
            int now_x = (int)x-48;
            x_list[now_x] += 1;
        }
        int[] result = new int[10];
        for(char y : Y.toCharArray()){
            int now_y = (int)y-48;
            if(x_list[now_y] == 0){
                continue;
            }
            x_list[now_y] -= 1;
            result[now_y] += 1;
        }
        StringBuilder sb = new StringBuilder();
        for(int i=9; i>=0; i--){
            for(int j=0; j<result[i]; j++){
                sb.append((char)(i+'0'));
            }
        }
        answer = sb.toString();
        if(answer.length() == 0){
            return "-1";
        }
        if(answer.charAt(0) == '0'){
            return "0";
        }
        return answer;
    }
}

 

 

 

코드 2

import java.util.*;
class Solution {
    public String solution(String X, String Y) {
        HashMap<Character, Integer> map = new HashMap<>();
        for(char x : X.toCharArray()){
            map.put(x, map.getOrDefault(x, 0)+1);
        }
        List<Character> result = new ArrayList<>();
        for(char y : Y.toCharArray()){
            if(map.get(y) == null){
                continue;
            }
            if(map.get(y) == 0){
                continue;
            }
            map.put(y, map.get(y)-1);
            result.add(y);
        }
        if(result.size() == 0){
            return "-1";
        }
        Collections.sort(result, Comparator.comparing(arr -> -arr));
        StringBuilder sb = new StringBuilder();
        for(int i : result){
            sb.append((int)(i-48));
        }
        String answer = sb.toString();
        if(answer.charAt(0) == '0'){
            return "0";
        }
        return answer;
    }
}