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

문제

숫자 짝꿍

요약 | 두 수에서 공통적으로 나타나는 수를 이용하여 가장 큰 수를 만들어보자.

나의 풀이

첫 번째 삽질

class Solution {
    fun solution(X: String, Y: String): String {
        var answer: String = ""
        //1. 동일 숫자 찾기
        val longStr = if (X.length >= Y.length) X else Y
        var shortStr = if (X.length < Y.length) X else Y        
        var sameStr = ""
        for(i in 0 .. longStr.length - 1) {
            if (shortStr.contains(longStr[i])) {
                sameStr += shortStr[shortStr.indexOf(longStr[i])]
                shortStr = shortStr.replaceFirst(longStr[i].toString(), "")
            }
        } 
        //2. 제일 큰 수 만들기
        if(sameStr.isEmpty()) {
            return "-1"
        } else if (sameStr.maxOrNull()!! == '0') {
            return "0"
        } else {
            //println(sameStr.maxOrNull() ?: "none")
            var temp = sameStr
            var maxNum = ""
            for (i in 0 .. sameStr.length - 1) {                
                var max = temp.maxOrNull() ?: "0"
                maxNum += max
                temp = temp.replaceFirst(max.toString(), "")                
            }
            return maxNum
        }     
    }
}

• 두 숫자 중 길고 짧은 숫자를 식별해 놓는다.
• 동일한 숫자를 찾는데, 긴 숫자에서 짧은 숫자 중 포함(contains)하고 있는 숫자(문자)가 있으면 해당 숫자를 sameStr에 적립해둔다.
• sameStr로 가장 큰 수를 만들어주는데, 가장 큰 수를 맨 앞에 위치시키는 방식으로 구현했다(정렬을 하면 됐는데...)
• 이 코드는 답은 잘 구하는 것 같지만 계속 시간초과가 되어서 통과를 못했었다.
  • 정렬을 해도 시간초과 되는 것은 마찬가지 였다..
  • 이번 문제로 replace의 연산량이 꽤 크다는 사실을 알았다.

두 번째 시도

class Solution {
    fun solution(X: String, Y: String): String {
        var answer: String = ""        
        var xArr = IntArray(10)
        var yArr = IntArray(10)        
        for (digit in X) {
            xArr[ (digit - '0') ]++ //'0' = 48, 48을 빼면 숫자 값 얻음
        }        
        for (digit in Y) {
            yArr[ (digit - '0') ]++
        }        
        for (i in 9 downTo 0) {
            if (xArr[i] != 0 && yArr[i] != 0) {
                var minCnt = kotlin.math.min(xArr[i], yArr[i])
                answer += i.toString().repeat(minCnt)
            }
        }        
        if(answer == "") return "-1"
        if(answer[0] == '0') return "0"       
        return answer
    }
}

• 시간이 많이 소요되어 결국엔 선조의 코드들을 참고했다.
• 0~9의 숫자가 X, Y에 몇 번씩 들어가는 지를 먼저 판별한다.
  • 매개변수가 string으로 주어지기 때문에 xArr[ (digit - '0') ]++를 작성한다.
    • 각 문자는 ASCII 코드 값으로 표현되며, 숫자 문자 '0'의 ASCII 값은 48이다. 따라서 각 숫자 문자의 ASCII 값에서 '0'의 ASCII 값(48)을 빼면 해당 숫자의 정수 값을 얻을 수 있는데, 예를 들어, 문자 '5'의 ASCII 값은 53이며, '5' - '0'은 5가 된다.
• 9에서 0까지 내려가면서 X, Y 중 들어간 숫자의 횟수가 더 적은(min) 값을 알아내면 두 숫자에 공통으로 들어간 횟수를 알 수 있게 된다.
  • 공통으로 들어간 횟수를 알게되면, 그 횟수 만큼 해당 숫자를 반복한다. (이때, 9부터 0까지 내려오기 때문에 자동으로 내림차순 된 값 즉, 가장 큰 값으로 저장된다).
• 마지막으로 예외적인 -1, 0 케이스를 처리해준다.

---

[TIL-240318]