[프로그래머스] Lv.1 숫자 짝꿍

이진이·2023년 8월 10일

⚠️JAVA 언어를 사용합니다.

🔒문제

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.

예를 들어, X \= 3403이고 Y \= 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X \= 5525이고 Y \= 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.)
두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요.

제한사항

3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
X, Y는 0으로 시작하지 않습니다.
X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

입출력 예

X	Y	result
"100"	"2345"	"-1"
"100"	"203045"	"0"
"100"	"123450"	"10"
"12321"	"42531"	"321"
"5525"	"1255"	"552"

🗝️정답

class Solution {
    public String solution(String X, String Y) {
        StringBuffer answer = new StringBuffer("");
        int[] x = {0,0,0,0,0,0,0,0,0,0};
        int[] y = {0,0,0,0,0,0,0,0,0,0};
        boolean[] key = {true, true};
        
        for(int i=0; i<X.length() || i<Y.length(); i++){
            if(i<X.length())
                x[X.charAt(i)-'0']++;
            if(i<Y.length())
                y[Y.charAt(i)-'0']++;
        }
        
        for(int i=9; i>=0; i--){
            if(x[i]!=0 && y[i]!=0){
                key[0] = false;
                for(int j=0; j<x[i] && j<y[i]; j++){
                    answer.append(i);
                }
                if(i!=0) key[1] = false;
            }
        }
        
        if(key[0]){
            answer.append(-1);
        }else if(key[1]){
            answer = new StringBuffer("0");
        }
        
        return answer.toString();
    }
}

💡풀이해석

- 숫자 0-9까지의 갯수를 파악해야 하므로, 10사이즈의 배열을 두개(X,Y) 만들어서 각자 카운팅한다.

- 카운팅된 갯수가 둘 다 0이 아니면 그 수를 저장한다. 이때 둘 중 더 작은 수가 서로 중복되는 갯수이므로 작은 수 만큼만 반복한다.

// 선언 및 초기화

int[] x, int[] y : 카운팅을 위한 두 변수 생성
boolean[] key : 마지막에 사용된다. 인덱스 0은 같은 수가 하나도 없는지 판단, 인덱스 1은 같은 수가 모두 0인지 판단

// 각 숫자 카운트

for(int i=0; i<X.length() || i<Y.length(); i++) : 둘 다 끝나야 반복문이 종료된다. 길이가 다를 수 있기 때문에 설정
- 주어진 숫자에 해당하는 인덱스를 하나씩 증가해주면 된다.

// X와 Y에서 같은 수 판단

for(int i=9; i>=0; i--) : 만들 수 있는 가장 큰 수를 반환해야 하므로 큰 수부터 판단하여 문자열에 넣는다.
if(x[i]!=0 && y[i]!=0) : 둘 다 0이 아니라면 둘이 같은 수를 가지는 것이므로 key[0]을 바꿔주고, 몇 번 중복되는지 확인하여 문자열에 추가한다.
if(i!=0) : 이 때 0이 아닌 수가 담기는 것이라면 숫자 0만 반복되는 일이 없으므로 두번째 키값(key[1])을 바꿔준다.

// 문자열 정리

if(key[0]) : true라면 같은 수가 하나도 없으므로 -1 반환
else if(key[1]) : true라면 0만 반복된 문자열 이므로 0 중복 제거

채점 결과

✏️자기 분석

숫자가 0-9까지만 있는 것을 고려하여 배열을 만드는걸 생각해내지 못했다.

방향을 카운팅이 아니라 직접 비교하는 쪽으로 잡아서 시간이 오래 걸렸다.

첫 번째 풀이

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        StringBuffer answer = new StringBuffer("");
        ArrayList<String> same = new ArrayList<>();
        String lon = X, shor = Y;
        if(X.length()-Y.length() < 0) {
            lon = Y;
            shor = X;
        }
        String[] ch = shor.split("");
        for(int i=0; i<shor.length(); i++) {
            if(lon.contains(ch[i])){
                lon = lon.replaceFirst(ch[i]," ");
                same.add(ch[i]);
            }
        }
        Collections.sort(same, Collections.reverseOrder());
        if(same.size()==0){
            answer.append("-1");
        }else if(same.get(0).equals("0")){
            answer.append("0");
        }else{
            for(int i=0; i<same.size(); i++) {
                answer.append(same.get(i));
            }
        }
        return answer.toString();
    }
}

- 더 짧은 문자열을 큰 문자열과 하나씩 대조하며 같은 수를 찾는다.

- 찾는 방식은 작은 문자열을 하나씩 잘라 배열로 저장하고 배열의 값이 큰 문자열에 있으면 문자열에서 그 수 즉, 문자를 하나만 제거하고, 그 값을 list에 저장한다.

- 리스트를 내림차순으로 정렬하여 문자열로 변환한다.

replaceAll()도 많이 사용되고, 과정에 필요한 로직이 많아서 시간 초과에 걸렸다.

두 번째 풀이

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        StringBuffer answer = new StringBuffer("");
        ArrayList<Character> same = new ArrayList<>();
        char[] x = X.toCharArray();
        char[] y = Y.toCharArray();
        Arrays.sort(x);
        Arrays.sort(y);
        
        for(int i=0, j=0; i<x.length && j<y.length; i++){
            if(x[i]<y[j]) continue;
            while(j<y.length){
                if(x[i] != y[j]) 
                    j++;
                else{
                    same.add(x[i]);
                    j++;
                    break;
                }
            }
        }
        
        Collections.sort(same, Collections.reverseOrder());
        if(same.size()==0){
            answer.append("-1");
        }else if(same.get(0)=='0'){
            answer.append("0");
        }else{
            for(int i=0; i<same.size(); i++){
                answer.append(same.get(i));
            }
        }
        return answer.toString();
    }
}

이번엔 둘 다 배열로 접근해 보았다. 두 문자열(배열)을 정렬하고 X를 중심으로 하나씩 비교하는데, X의 비교 값이 Y의 현재 비교값 보다 크거나 같을 때만 Y를 다음 순서로 넘긴다. 이건 말로 설명해놓기 어려운 것 같다. ~~나중에 궁금하면 직접 돌려보자..~~

어쨋든 이것도 실패했다. 이거는 진짜 왜 실패한건지 아직도 모르겠다.~~(문제 푼지 4시간 지남)~~

세 번째 풀이(정답)

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        StringBuffer answer = new StringBuffer("");
        int[] x = {0,0,0,0,0,0,0,0,0,0};
        int[] y = {0,0,0,0,0,0,0,0,0,0};
        char[] xchar = X.toCharArray();
        char[] ychar = Y.toCharArray();
        boolean[] key = {true, true};
        
        for(int i=0; i<xchar.length || i<ychar.length; i++){
            if(i<xchar.length)
                x[xchar[i]-'0']++;
            if(i<ychar.length)
                y[ychar[i]-'0']++;
        }
        
        for(int i=9; i>=0; i--){
            if(x[i]!=0 && y[i]!=0){
                key[0] = false;
                for(int j=0; j<x[i] && j<y[i]; j++){
                    answer.append(i);
                }
                if(i!=0) key[1] = false;
            }
        }
        
        if(key[0]){
            answer.append(-1);
        }else if(key[1]){
            answer = new StringBuffer("0");
        }
        
        return answer.toString();
    }
}