(알고리즘) 숫자 짝꿍

신나는 주말!

주말에는 간단한 알고리즘 문제를 풀어보자!

 

🔥알고리즘 문제

 

문제설명

두 정수 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"

입출력 예 설명

입출력 예 #1

• X, Y의 짝꿍은 존재하지 않습니다. 따라서 "-1"을 return합니다.

입출력 예 #2

• X, Y의 공통된 숫자는 0으로만 구성되어 있기 때문에, 두 수의 짝꿍은 정수 0입니다. 따라서 "0"을 return합니다.

입출력 예 #3

• X, Y의 짝꿍은 10이므로, "10"을 return합니다.

입출력 예 #4

• X, Y의 짝꿍은 321입니다. 따라서 "321"을 return합니다.

입출력 예 #5

• 지문에 설명된 예시와 같습니다.

 

내가 처음에 작성한 코드  (테스트 미통과)

fun solution(X: String, Y: String): String {
    var answer: String = ""
    var commonXY= X.toSet().intersect(Y.toSet())

    answer=commonXY.toMutableList().sortedDescending().toList().joinToString("")
    if(commonXY.isEmpty()) answer="-1"
    return answer
}

 

내가 처음에 작성한 코드 해석

이 코드는 부분적으로는 잘 작동하나 중복된 값이 들어있을경우에 중복된 값을 제외하고 집합을 만들어서 처리를 하기 때문에 X가 "5525", Y가 "1255"일때 522가 아닌 52를 반환하기 때문에 코드의 수정이 필요하다

 

수정된 코드 (런타임 에러)

fun solution(X: String, Y: String): String {

    val duplicatedX = X.groupingBy { it }.eachCount()
    println(duplicatedX)
    val duplicatedY = Y.groupingBy { it }.eachCount()
    println(duplicatedY)

    val commonChars = mutableListOf<Char>()
    for ((char, countX) in duplicatedX) {
        if (char in duplicatedY ) {
            val minCount = minOf(countX, duplicatedY [char]!!)
            repeat(minCount) {
                commonChars.add(char)
            }
        }
    }

    val sortedCommon = commonChars.sortedDescending().joinToString("")

    if (sortedCommon.isEmpty()) {
        return "-1"
    }
    return sortedCommon
}

 

수정된 코드 해석

val duplicatedX = X.groupingBy { it }.eachCount()
    println(duplicatedX)
    val duplicatedY = Y.groupingBy { it }.eachCount()
    println(duplicatedY)​

 

각 문자열 X와Y의 빈도수를 계산해서 맵으로 저장

val commonChars = mutableListOf<Char>()​

 

공통된 문자 저장할  commonChars라는 리스트 생성

for ((char, countX) in duplicatedX){}​

문자열 X의 각 문자와 빈도수만큼 반복

if (char in duplicatedY ){}

문자가 중복되는지 확인

val minCount = minOf(countX, duplicatedY [char])

두 문자열에서의 최소 빈도수를 minCount에 저장

repeat(minCount) {
    commonChars.add(char)
}

최소 빈도수 만틈 문자를 리스트에 추가

val sortedCommon = commonChars.sortedDescending().joinToString("")


if (sortedCommon.isEmpty()) {
    return "-1"
}
if(sortedCommon.toInt()<1)  return "0"

 문자열을 내림차순 정렬후 string으로 전환한 값이 0이면 0반환, 중복되는 값이 없으면 -1을 반환

return sortedCommon​

 

if문에 해당하지 않으면 sortedCommon을 반환

 

 

하지만 이 코드 또한 기능을 완벽히 구현은 하지만  런타임 에러가 발생한다

 

 

최종적으로 작성한 코드

 

fun solution(X: String, Y: String): String {

    val countX = IntArray(10)
    val countY = IntArray(10)

    for (char in X) {
        countX[char - '0']++
    }

    for (char in Y) {
        countY[char - '0']++
    }
    val commonChars = StringBuilder()

    for (i in 9 downTo 0) {
        val minCount = minOf(countX[i], countY[i])
        if (minCount > 0) {
            repeat(minCount) {
                commonChars.append(i)
            }
        }
    }

    val result = commonChars.toString()


    if (result.isEmpty()) {
        return "-1"
    }
    
    if (result == "0".repeat(result.length)) {
        return "0"
    }

    return result
}

 

val countX = IntArray(10)
    val countY = IntArray(10)

    for (char in X) {
        countX[char - '0']++
    }
    for (char in Y) {
        countY[char - '0']++
    }

0부터 9까지의 숫자 빈도를 저장할 배열을 생성하고 X와Y의 빈도를 계산한다
문자 '0'의 ASCII코드 값은 48이기때문에 '0'을 빼지 않고 문자열을 넣게되면
예를들어 '3'의 ASCII코드의 값은 51이기때문에 3이라는 값이 들어가지 않고 51이라는 값이 들어가게 된다.
따라서 '0'을 빼는식으로 진행

val commonChars = StringBuilder()​

 

공통된 문자를 저장할 StringBuilder 생성

for (i in 9 downTo 0) {
        val minCount = minOf(countX[i], countY[i])
        if (minCount > 0) {
            repeat(minCount) {
                commonChars.append(i)
            }
        }
    }​

 

각 숫자의 최소 빈도를 minCount에 저장하고
최소빈도수만큼 반복

 

런타임 오류 없이 잘 작동

 

다른사람은 어떻게 했을까?

fun solution(X: String, Y: String): String {
        var answer: String = ""

        for (ch in (9 downTo 0).toList().map { it.toString() }) {
            answer += ch.toString().repeat(min(X.count { it.toString() == ch }, Y.count { it.toString() == ch }))
        }
        if (answer.isEmpty()) answer = "-1"
        if (answer.toList().distinct() == listOf('0')) answer = "0"

        return answer
    } //JupitorCentral , 안태호 , SeongJongHo님이 작성한 코드 입니다

 

다른 사람들이 작성한 코드 해석

min(X.count { it.toString() == ch }, Y.count { it.toString() == ch })​

ch가 9부터 0까지 내려가므로 예를들어 ch가 9일때를 예시로 들면  X에 "9"가 몇개 있는지, Y에 "9"가 몇개 있는지를 확인 -> X에 "9"가 2개 있고, Y에 "9"가 5개가 있다면 2라는 값을 반환

ch.toString().repeat()

그 2라는 값이  repaet() 인자로 들어감. 즉 ch를 2번 반복. 이경우에는 "9"를 2번 반복한다

answer += ch.toString().repeat(min(X.count { it.toString() == ch }, Y.count { it.toString() == ch }))​

"9"를 2번 반복한 값은 "99"이다. 그 "99"를 answer에 저장
현재 answer는 "99" 라는 문자열이다.

 for (ch in (9 downTo 0).toList().map { it.toString() }) {}​

 

즉 이 과정을 9부터 0까지 반복하기 때문에  answer의 값은
"99" -> "998"-> "998666" -> "9986661"-> "99866610" 이런식으로 변하게 된다.

if (answer.isEmpty()) answer = "-1"
if (answer.toList().distinct() == listOf('0')) answer = "0"​

 

만약 answer가 공백이라면, 즉 X와Y가 겹치는 값이 전혀 없다면 answer에 -1을 저장하고
만약 answer가 0으로만 이루어져있는, 즉 0이라면 answer에 0을 저장

return answer​

answer 값 반환

 

 

 

더 개선해야할 Point

StringBuilder()는 코틀린에서 문자열을 효율적으로 조작할 수 있게 해주는 클래스이다. 문자열을 많이 변경을 해야하는 경우에는 StringBuilder()을 사용하는것이 성능을 향상시키는데 도움이 된다

 

 알고리즘 GitHub : https://github.com/kotlin2024/algorithm/commit/8a7a5fcd306a3d8dc2a6ca37175ef75a6e98af49