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

 

🍄 코딩테스트

코딩테스트 문제 풀이

✍🏻 Github

문제 풀이 github 링크

 

 

문제 설명

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

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

 

 

문제 풀이

나의 풀이

import Foundation

func solution(_ X:String, _ Y:String) -> String {
    
    let setX = Set(X)
    let setY = Set(Y)
    let intersect = setX.intersection(setY)
    
    var duplication = [String]()
    
    for i in Array(intersect) {
        let count = min(Y.filter{ $0 == i }.count, X.filter{ $0 == i }.count)
        (0..<count).forEach{ _ in duplication.append(String(i)) }
    }
    
    if duplication.isEmpty {
        return "-1"
    }else if duplication.filter{ $0 == "0" }.count == duplication.count {
        return "0"
    }
    
    return duplication.sorted(by: >).joined()
}

 

풀이 시간을 한 시간을 넘겨버렸지만, 조금만 더 하면 풀릴 것 같아서 계속 붙잡고 있었더니 그 결과 10분 뒤에 해결할 수 있었다. 하지만 첫 풀이과정의 결과는 그저 처참했다.

 

도저히 뭐가 문제인지 반례를 찾을 수 없어서 "질문하기"를 쓰윽 봤다. 내가 놓친 부분은 X와 Y의 문자열의 길이의 최댓값이 Int의 최댓값을 넘어간다는 사실이었다. 처음에 “00” 이나 “000”, “” 이 출력되는 과정을 해결하기 위해서 guard let 문을 써서 Int 값으로 바꿔버린 후 다시 String 으로 바꾸려고 시도했다. 그러니 Int 값으로 반환되는 과정에서 Int의 범위를 벗어나 올바른 값이 출력되지 않았던 것이다.

 

이를 해결하기위해 Int로 바꾸는 대신 if문을 첨가했다. 첫 번째는 겹치는 숫자만을 도출한 duplication배열이 비어있는지 확인 후 “-1”을 출력하는 것이고, 두 번째는 문자열에서의 “0”의 갯수가 문자열의 길이와 같다면 “0”을 출력하도록 하는 것이다.

 

처음에 쓸데없는 for문을 도는 것을 방지하기 위해 교집합 연산을 활용해 두 배열의 공통된 값을 찾았다. 이 부분이 시간을 줄일 수 있도록 도와준 것 같다.

 

다른 사람 풀이

import Foundation

func solution(_ X:String, _ Y:String) -> String {
    let arr1 = Array(X)
    let arr2 = Array(Y)
    let uniqueKey = Set(arr1).intersection(Set(arr2))
    var answer = ""
    for key in uniqueKey.sorted(by: >) {
        answer += String(repeating: key, count: min(arr1.filter{$0 == key}.count, arr2.filter{$0 == key}.count))
    } 
    return answer == "" ? "-1" : ((uniqueKey.count == 1 && uniqueKey.contains("0")) ? "0" : answer)
}

 

풀이 방법은 비슷하나 answer에 값을 내림차순으로 도출하여 String의 + 연산을 활용해 바로 answer을 만들어 냈다는 점이다.

duplication.sorted(by: >).joined() 이 과정을 생략할 수 있어서 좀 더 효율적인 풀이 방법인 것 같다.

 

 

중요한 개념

- A와 B의 교집합구하기

A.intersection(B)