Lv1. 숫자짝꿍 Swift

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

프로그래머스

 

프로그래머스에서 숫자짝꿍이라는 문제를 풀다보니 너어어어무 안풀리다가 번뜩하고 떠올라

풀게되어 이야기를 해보겠다.

 

문제설명

두 정수 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 함수를 완성해주세요.

 

틀린 풀이

func solution1(_ X:String, _ Y:String) -> String {
	var Y: [String] = Y.map { String($0) }.sorted(by: >)
	var arr: [String] = []
	var result: String = ""
	var flag: Bool = true
	for numberX in X.sorted(by: >) {
		for (i, numberY) in Y.enumerated() {
			if String(numberX) == numberY {
				Y[i] = "."
				arr.append(String(numberX))
				flag = false
				break
			}
		}
	}
	if flag { return "-1" }
	for i in 0..<arr.count {
		result += arr[i]
	}
	return result
}

풀이를 살펴보면

 먼저 Y 문자열을 map 고차함수를 통해 배열로 변환하면서 내림차순으로 정열해준다

그 후 내림차순으로 정렬된 X의 문자열을 순회하며 그 안에서 Y 배열을 순회한다

Y 배열을 순회하며 X와 Y에서 동일한 문자를 발견하면 arr라는 배열에 추가해줌과 동시에

Bool 타입 변수인 flag을 false로 바꿔준다

flag가 true라면 동일원소가 없다는 의미이기에 "-1" 을 return 해주고

아니라면 solution 함수의 return 타입은 String 이기 때문에 

arr 변수를 순회하며 String 타입 변수인 result에 추가해주고 return 해준다

 

 이 풀이에서는 11 ~ 15 케이스에서는 시간초과, 16, 17 케이스에서는 실패가 떴다

먼저 시간초과는 이중 반복문에서 시간초과가 났을 것이라는 확신이 있었고,

실패는 아마 예시에서 알려준 공통된 숫자가 모두 0일 경우에 대한 예외처리를 안해준 것이

실패 요인이었다고 생각을 했다.

 

 다시 논리를 재정리 해보자라는 생각으로 다시 논리를 생각했다.

일단 제일 중요한 이중 반복문을 쓰지 않는 방법이어야 했다.

예전에 Counting Sort 라는 10 크기의 배열을 생성하고 횟수만큼 

배열에 추가해서 정렬하는 알고리즘이  생각이 났다.

그래서 횟수를 카운트해서 해보자라는 생각으로 논리를 다시 생각했다.

풀이는 아래 코드에서 더 말하겠다.

 

맞은 풀이

func solution(_ X:String, _ Y:String) -> String {
	// 1~10의 숫자가 몇 개 있는 지 카운트하기 위한 배열
	var countX: [Int] = Array(repeating: 0, count: 10)
	var countY: [Int] = Array(repeating: 0, count: 10)
	
	var result: String = ""
	
	// 몇 개 있는 지 카운트
	for number in X { countX[Int(String(number))!] += 1 }
	for number in Y { countY[Int(String(number))!] += 1 }
	
	// 0 ~ 9 를 역순으로 순회하면서 두 수가 0보다 클 때 더 작은 갯수만큼 문자열에 추가
	for i in stride(from: 9, through: 0, by: -1) {
		if countX[i] > 0 && countY[i] > 0 {
			result += String(repeating: String(i), count: min(countX[i], countY[i]))
		}
	}
	if result.isEmpty { return "-1" }
	if result.first! == "0" { return "0" }
	return result
}

풀이를 살펴보면

 먼저 Int 타입의 배열인 countX, countY을 선언해주고 10만큼 0으로 채워주었다.

그 후 반복문 2개로 X와 Y 문자열의 원소를 countX, countY 배열의 인덱스로 사용하여

+ 1씩 카운트 해주었다

그 후 9부터 0 까지 역순으로 순회하며 countX, countY 가 동일하게 원소를 갖고있다면

그 중 작은 갯수만큼 result 문자열에 더해준다.

9부터 0까지 역순으로 순회한 이유는 result에 동일원소를 더해주고 따로 정렬을 하지 않게 하기 위해서이다.

그 후에 코드는 따로 설명이 필요 없으니 여기까지 하겠다.