[Swift 알고리즘] Programmers 숫자 짝꿍

△

Level 1 연습문제 

숫자 짝꿍

문제 설명
두 정수 X, Y가 공통으로 가지는 정수 k(0 ≤ k ≤ 9) 들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 한다. 짝꿍이 존재하지 않으면 짝꿍은 -1. 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0.
두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요. 
제한사항 
- 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
- X, Y는 0으로 시작하지 않습니다.
- X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

입출력 예시

print(solution("3403", "13203")) //330
print(solution("100", "2345")) //-1
print(solution("100", "203045")) //0
print(solution("12321", "42531")) //321

 

1단계 문제 이렇게 어렵기 있나요..? ㅠㅠ 사실 문제자체는 그리 어렵지 않은 느낌이었는데 (문제 이해는 5분 걸림) 11번 ~ 15번 케이스에서 계속 시간  초과로 실패가 뜨는 바람에 ㅠㅠ 너무 오래걸렸다. (4시간 동안 붙들고있었음.. ㅎ)

 

1차 시도

정수 X와 Y의 자릿수 중 더 작은 자릿수 만큼 반복문을 돌려, ... 

시간초과! + 몇몇 케이스에서 실패 (signal illegal instruction (core dumped)) 라는 에러도 함께 떴다. 

짝꿍이 상당히 큰 정수일 수 있으니 문자열로 반환하라는 제한사항.. 

String(Int(String(k))!) 이렇게 String을 Int로 바꾸고 String으로 다시 형변환을 해주니 이런 에러가 뜨는 것 같더라.

ㅎㅎ 걸렸나요..? 그쵸 그럴거면 Int로 반환하라고 하지 

 

2차 시도 

아 테스트 케이스 크기가 크니까, 0~9만큼만 반복문 돌리자! 그럼 괜찮겠지..?

No. 

 

3차 시도

첨부터 정렬을 해주고 firstIndex 구해서 dropFirst(n)으로 X, Y에서 값을 없애나가자!

별 도움 안됨. 테스트케이스 숫자가 커서 처음부터 정렬을 해주는 것이 오히려 시간초과.   

var X = X.map{ String($0) }.sorted()

 

통과 답안

func solution(_ X:String, _ Y:String) -> String {
    var k = [String]()
    
    for i in 0...9 {
        let xCount = X.filter{ String($0) == String(i) }.count
        let yCount = Y.filter{ String($0) == String(i) }.count
        let count = min(xCount, yCount)
        k.append(contentsOf: Array(repeating: "\(i)", count: count))
    }
    k = k.reversed()
    if (k.count > 0) && (k[0] == "0") { k = ["0"] }
    return (k.count > 0) ? k.joined(separator: "") : "-1"
}

 

다른 답안 

각 문자열의 자리수 개수를 먼저 세 준 후 나중에 비교를 하는 것이 포인트. 

func solution(_ X:String, _ Y:String) -> String {
    var answer = ""
    var xNumberCount = Array(repeating: 0, count: 10)
    var yNumberCount = Array(repeating: 0, count: 10)
    for x in X {
        xNumberCount[Int(String(x))!] += 1
    }
    for y in Y {
        yNumberCount[Int(String(y))!] += 1
    }
    for number in stride(from: 9, through: 0, by: -1) {
        let minCount = min(xNumberCount[number], yNumberCount[number])
        if number == 0, 0 < minCount, answer.isEmpty { 
            answer = "0"
            break
        }
        for _ in 0 ..< minCount {
            answer.append(String(number))
        }
    }
    return answer.isEmpty ? "-1" : answer
}