[JS] 프로그래머스 숫자 짝궁

https://school.programmers.co.kr/learn/courses/30/lessons/131128

프로그래머스

 

 

목차

• 문제
• 풀이
• 코드

문제

입력

X, Y - X, Y 두 정수. 문자열로 주어진다.

 

출력

result - X, Y의 공통인 숫자들로 만들 수 있는 최대의 정수인 짝궁을 산출한다. 없다면 -1을 반환한다.

 

제한사항

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

풀이

이 문제는 먼저 X, Y의 공통인 숫자를 찾는다. 이를 조합해서 가장 큰 정수를 결과로 반환한다.

그러나 X, Y의 최대 길이가 3,000,000이므로 X, Y 모든 배열을 하나하나 검사한다면 O(n^2)으로 시간초과가 나올 것 같다. 시간복잡도를 어떻게 해야 줄일 수 있을지 고려해야 한다.

 

지금 떠오르는 방법은 0부터 9까지의 인덱스가 있는 X의 배열, Y의 배열를 따로 선언해서 0부터 9까지의 숫자가 각각 몇 번 나오는지 확인하고 두 객체의 공통적으로 들어있는 배열을 선언한 후에 sort를 사용해서 정렬 후 출력하는 방법이 좋을 거 같다.

그리고 0, 0, 0, 0만 있는 경우를 고려해서 그럴 경우 result를 0으로 출력하도록 구현해야 한다.

=> sort 굳이 사용하지 않고 9부터 0까지 순회하면서 넣는 방법이 가장 좋다.

 

의사코드를 러프하게 적자면 다음과 같다.

X 배열 = [0부터 9까지의 인덱스. 0으로 초기화];

Y 배열 = [0부터 9까지의 인덱스. 0으로 초기화];

결과 문자열 = '';

 

for (X 문자열 안에 있는 원소 값) {

    X 배열 [원소 값] ++

}

// Y 문자열도 똑같이 반복

 

for (인덱스 9부터 0까지 10번 반복) {

    각각의 인덱스에서 작은 값을 결과 문자열에 더한다.

}

 

결과가 빈문자열이라면 -1을 반환하고 그렇지 않으면 결과를 반환한다.

 

=> 여기에서 -1을 정수로 반환해서 오류가 생겼고 코드를 직접 구현하다보니 좀 더 쉬운 방법이 생각나서 계속 고쳤다.

따라서 X, Y 배열을 미리 선언하기 보다는 함수로 통일 시켜서 return 값을 X 배열, Y 배열에 넣도록 하였고 그러고 나서 for문으로 9부터 0까지 차례대로 순회하여 결과값에 갱신되도록 하였다. 이때 while문을 사용하여 가령 9가 3번씩 공통되었다면 3부터 1까지 총 세 번 반복되도록 구현하였다. 결과값이 빈문자열일 때 0이 여러번 공통되는 경우는 if문을 활용하여 0이 한 번만 더해지도록 하였다.

 

시간 복잡도는 두 문자열을 각각 순회하고 while 문의 최악의 경우까지 합하면 O(3n)이다.

공간 복잡도는 두 문자을 저장하는 공간인 O(2n)이다.

 

코드

function countArr(str) {
    const newArr = new Array(10).fill(0);
    
    for (v of str) {
        newArr[v] += 1;
    }

    return newArr;
}

function solution(X, Y) {
    const arrX = countArr(X);
    const arrY = countArr(Y);
    var answer = '';
    
    for (let i=9; i>=0; i--) {
        let temp = arrX[i] < arrY[i] ?  arrX[i] : arrY[i];
        if (i===0 && !answer && temp) {
            answer += i;
            break;
        }
        while (temp > 0) {
            answer+=i;
            temp--;
        }
    }
    
    return answer ? answer : "-1";
}

 

의사코드를 너무 러프하게 썼다. 의사 코드 예시 보고 틀에 맞게 써야겠다.

최종적으로 완료된 풀이를 넣을지 혹은 생각하고 접근했던 모든 방법들까지 적을지 정해야겠다. => 최종적으로 완료된 풀이 적자.