[프로그래머스- Lv1] 숫자 짝꿍

문제 링크

Problem

두 개의 문자열에서 공통되는 문자를 뽑아 내림차순으로 정렬해서 출력하는 문제이다. 

주의해야 할 점은 문자열이 '0'으로만   '0'을 출력해야 하고, 공통되는 문자가 없다면 '-1'을 출력해야 한다.

 

Approach

Map의 key:value 특징을 활용하여 풀었다.

map 변수 : 더 긴 문자열의 문자 개수를 저장하는 map

store 변수 : 공통되는 문자 개수를 저장하는 map

 

먼저, 두 문자열 중에서 더 긴 문자열을 찾고 map 변수에 저장한다. 긴 문자열에서 0~9 사이의 정수가 몇 번 나왔는지 map 변수에 저장한다. 

X의 길이 < Y의 길이

for (int i = 0; i < Y.length(); i++) 
{
    int num = Y.charAt(i) - '0';
    map.put(num, map.get(num) + 1);
}

다음으로, 더 짧은 문자열에서 문자를 하나씩 꺼낸다. 해당 문자가 이전에 저장한 map 변수에 1개 이상 저장되어 있다면 두 문자열 간에 공통되는 문자이므로 store 변수에 개수 1을 증가시킨다. 반대로 map 변수에서는 1을 감소시킨다.

문자 개수를 감소시키지 않는다면 계속 공통되는 문자가 되기 때문에 반드시 1을 감소시킨다.

X의 길이 < Y의 길이

for (int i = 0; i < X.length(); i++)
{
    int num = X.charAt(i) - '0';
    if (map.get(num) > 0) {
        store.put(num, store.get(num) + 1);
        map.put(num, map.get(num) - 1);
    }
}

 

Code

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        StringBuffer sb = new StringBuffer();

        Map<Integer, Integer> map = new HashMap<>();
        Map<Integer, Integer> store = new HashMap<>();
        for (int i = 0; i <= 9; i++) {
            map.put(i, 0);
            store.put(i, 0);
        }

        if (X.length() < Y.length()) {
            for (int i = 0; i < Y.length(); i++) {
                int num = Y.charAt(i) - '0';
                map.put(num, map.get(num) + 1);
            }

            for (int i = 0; i < X.length(); i++) {
                int num = X.charAt(i) - '0';
                if (map.get(num) > 0) {
                    store.put(num, store.get(num) + 1);
                    map.put(num, map.get(num) - 1);
                }
            }
        } else {
            for (int i = 0; i < X.length(); i++) {
                int num = X.charAt(i) - '0';
                map.put(num, map.get(num) + 1);
            }

            for (int i = 0; i < Y.length(); i++) {
                int num = Y.charAt(i) - '0';
                if (map.get(num) > 0) {
                    store.put(num, store.get(num) + 1);
                    map.put(num, map.get(num) - 1);
                }
            }
        }

        for(int i = 9; i >= 0; i--) {
            for(int j = 0; j < store.get(i); j++) {
                sb.append(i);
            }
        }

        boolean isAllZero = noZero(store);

        if(sb.length() == 0)
            return "-1";
        else {
            if(!isAllZero)
                return "0";
            else
                return sb.toString();
        }
    }
    static boolean noZero(Map<Integer, Integer> map) {
        for(int i = 1; i <= 9; i++) {
            if(map.get(i) > 0)
                return true;
        }
        return false;
    }
}

 

참고사항

위의 코드에서 String을 사용하면 시간 초과가 발생한다. StringBuffer를 쓰도록 하자. 그 이유는 아래 링크를 참고하자.

 

https://server-technology.tistory.com/13