프로그래머스 LV.1 숫자 짝꿍 스위프트

처음 이 문제를 읽고 이해하는데는 5분이 걸렸지만...

푸는데는... 근 3시간정도 걸린거 같다... ㅠ

 

들어가기에 앞서 풀이를 보고 싶다면 

맨 아래 코드만 보면 됩니다.

 

하지만 이러한 실패 케이스와 플로우를 따라가며 왜 그런코드가 나왔는지 이해하는것을 추천합니다

 

자 들어가보면

 

처음 예제 지문을 봤을때 조금 아리송 했는데

입출력 예제를 보니 바로 이해가 갔다

 

지문을 정리하자면

 

1.  X, Y의 짝꿍이 존재하지 않으면 - 1

2. X, Y의 짝꿍이 존재하지만 0만 있으면 0

3. 그것도 아니라면 가장 큰 정수 만들기

 

참 쉽죠... 그렇다면 코드를 작성해보겠습니다.

  첫번째 실패 케이스

import Foundation

func solution(_ X:String, _ Y:String) -> String {
    
    
    // x,y의 짝꿍이 존재하지 않는다면 -1 즉, 포함되어 있지 않다면
    var notPartner = X.map { $0 }.filter { Y.contains($0)}
    if notPartner.isEmpty {
        return "-1"
    }
    
    // x,y의 짝꿍이 0 이라면
    var partnerToZero = notPartner.map { Int(String($0))! }.reduce(0,+)
    if partnerToZero < 1 {
        return "0"
    }
    
    // 탈락시키는 방법은 어떰??
    
    var result: [String] = []
    var y = Y
    
    for i in X {
        if y.contains(String(i)) {
            if let number = y.firstIndex(of: i) {
                
                var result = y.remove(at: number)
                result.append(String(result))
            }
        }
    }
    var finalResult = result.sorted(by: >).joined()
    return finalResult
}

 

처음에는 지문 그대로 

단락 별로 구분 했습니다 ( -1 , 0, 수가 있을때 ) 

문제를 이해하고 순서대로 작성하면 이렇게 됩니다.. ㅠㅠ

 

실행이 되는가 싶더니 11 ~ 15번까지 시간초과가 떴습니다...

 

흠... 문제가 뭐였을까 생각을 하다가 

혹시 이 부분일까? 

    // x,y의 짝꿍이 0 이라면
    var partnerToZero = notPartner.map { Int(String($0))! }.reduce(0,+)
    if partnerToZero < 1 {
        return "0"
    }

이 부분에서 notPartner를 한번더 map과 reduce를 사용해서 그런가 싶어서 

다른 방식으로 녹여봤습니다.

import Foundation

func solution(_ X:String, _ Y:String) -> String {
    
    
    // x,y의 짝꿍이 존재하지 않는다면 -1 즉, 포함되어 있지 않다면
    // map으로 실행할때 문자 -> 문자열로 변환해서 뱉어주자.
    var notPartner: [String] = X.map { String($0) }.filter { Y.contains($0)}
     if notPartner.isEmpty {
         return "-1"
         // notPartner의 갯수와 notParter에 0의 갯수를 비교하는 식
     } else if notPartner.count == notPartner.filter({ $0 == "0"}).count {
         return "0"
     }
    
    // 탈락시키는 방법은 어떰??
    
    var result: [String] = []
    var y = Y
    
    for i in X {
        if y.contains(String(i)) {
            if let number = y.firstIndex(of: i) {
                
                var result = y.remove(at: number)
                result.append(String(result))
            }
        }
    }
    var finalResult = result.sorted(by: >).joined()
    return finalResult
}

 

흠... 뭔가 훨씬더 깔끔해진 느낌이라서 코드를 돌려 봤습니다.

....

 

네... 여전히 11~ 15번 케이스가 시간초과로 나왔습니다.

 

아마도 시간초과가 나오는 부분은 

숫자가 커질수록 하나씩 filter를 하는 부분이 많아지게 되서 시간 초과가 나오는거 같았습니다.

 

접근을 달리 해봤습니다.

하나씩 비교하는 부분이 많이 걸리는 거면...

 

일단 빈배열을 만들고 해당 인덱스를 +1 시켜주는 것을 만들고

비교하면 어떨까??

 

var arr = Array(repeatin: 0, count: 10)
print("arr:",arr)
    
    // arr: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

    for i in X.map({ Int(String($0))! }) {
    	// x를 String -> Int 로 변환후 해당 인덱스를 for문으로 돌려서 
        // 하나씩 빼오고 그것을 arr[i]에 넣고 해당 인덱스 자리를 +1 해준다.
        arr[i] += 1
    }
    print("arr[i]:",arr)
    
    // arr의 배열: [0, 2, 2, 1, 0, 0, 0, 0, 0, 0]

 

map을 통해 x 가 "12321" 로 주어졌을때 [1,2,3,2,1] 이런식으로 타입은 Int인 배열이 만들어 집니다.

i에 해당하는 인덱스 자리에 +1을 해줍니다.

 

여기까지는 참 쉽죠?

 

 

자. 그렇다면 여기서부터 하이라이트 입니다.

그렇다면 y도 비슷하게 한번 만들어 보겠습니다.

for j in Y.map({ Int(String($0))! }) {
	
}
// [4, 2, 5, 3, 1] 타입: Int

 

자 이렇게 나왔고... 만들어진 배열의 인덱스 와 기존에 만들었던 arr의 인덱스를 비교해가면서 코드를 작성해줍니다.

이런식으로 말이죠

for j in Y.map({ Int(String($0))! }) {
	// 들어오는 j인덱스가 0보다 크다면 함수 실행
	if arr[j] > 0 {
    	
    }
}

// 현재 arr배열 : [0, 2, 2, 1, 0, 0, 0, 0, 0, 0]
// [4, 2, 5, 3, 1] 타입: Int

 

함수를 실행하고, j가 있다면 담아줄 빈 배열을 생성해줍니다. 

// 담아줄 빈 배열
var answer: [Int] = []


for j in Y.map({ Int(String($0))! }) {
	// 들어오는 j인덱스가 0보다 크다면 함수 실행
	if arr[j] > 0 {
    	answer.append(j)
    }
}

// 현재 arr배열 : [0, 2, 2, 1, 0, 0, 0, 0, 0, 0]
// [4, 2, 5, 3, 1] 타입: Int

자 여기서 기술 들어갑니다.

 

지문에 보면 

X와 Y 에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다( X 에는 5가 3개, Y 에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.)

라고 나옵니다. 이말인 즉슨 중복은 가능 할 수는 있지만 하나씩 자릿수가 맞아야한다.

엥? 무슨 말인지...

 

결국 코드를 보면

// 담아줄 빈 배열
var answer: [Int] = []


for j in Y.map({ Int(String($0))! }) {
	// 들어오는 j인덱스가 0보다 크다면 함수 실행
	if arr[j] > 0 {
    	answer.append(j)
        // arr[j]가 0보다 큰것이 있다면 기존에 있던 arr배열에서 해당 인덱스에 -1를 
        // 해줌으로써 계속 중복되는 것을 방지 할 수 있음
        arr[j] -= 1
        print("arr[j]:",arr)
        // arr[2]: 1
        // arr[3]: 0
        // arr[1]: 1
    }
}

// 현재 arr배열 : [0, 2, 2, 1, 0, 0, 0, 0, 0, 0]
// [4, 2, 5, 3, 1] 타입: Int

 

1) j 가 4일때 : arr[4]에는 0이므로 함수 실행 안함

2) j 가 2일때 : arr[2]일때 2이므로 함수 실행 

( 중복으로 계속 실행하는 것을 방지하기 위해 arr[2] -1를 해줍니다)

 

이런식으로 하나씩 제거하다 보면 

answer = [2, 3, 1]

 

이렇게 쌓입니다.

지금 하나씩 손으로 적으면서 지워가는것도 이해하는데 도움이 많이 됩니다.

 

여기서 끝난게 아니라 

앞선 조건들 

 

1.  X, Y의 짝꿍이 존재하지 않으면 - 1

2. X, Y의 짝꿍이 존재하지만 0만 있으면 0

3. 그것도 아니라면 가장 큰 정수 만들기

 

관련 코드를 작성해줍니다. 

// answer이 비어있으면
if answer.isEmpty {
	return "-1"
}

// answer의 배열이 0으로 되어있으면
if answer.count == answer.filter({ $0 == 0 }).count {
	return "0"
}

// 최종 정답
return answer.sorted(by:>).map { String($0) }.joined()

 

현재 answer의 타입은 Int입니다

 

Int는 joined() 함수를 호출 할 수 없기 때문에, 다시 한번 map { String($0) } 해 줌으로써

하나씩 String 값으로 만들어 줍니다.

 

 

 

최종 코드 입니다. 

func solution(_ X:String, _ Y:String) -> String {
    
    var answer: [Int] = []
    var arr = Array(repeating: 0, count: 10)
    print("arr: ",arr)
    
    for i in X.map({ Int(String($0))! }) {
        arr[i] += 1
    }
    
    print("arr의 배열:",arr)
    
    for j in Y.map({ Int(String($0))! }) {
        if arr[j] > 0 {
            answer.append(j)
            arr[j] -= 1
            print("arr[j]:",arr[j])
        }
    }
    print("answer배열:",answer)
    
    if answer.isEmpty {
        return "-1"
    }
    
    if answer.count == answer.filter({ $0 == 0 }).count {
        return "0"
    }
    
    return answer.sorted(by: >).map { String($0) }.joined()
    
}

/*
arr:  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
arr의 배열: [0, 2, 2, 1, 0, 0, 0, 0, 0, 0]
arr[j]: 1
arr[j]: 0
arr[j]: 1
answer배열: [2, 3, 1]
321
*/

 

 

네... 11~ 15번 케이스에서 어마무시하네요... ㅠ

 

 

 

 

한줄평 : 쉽다고 다 쉬운게 아니라 시간 복잡도는 어렵고도 멀고도 멀다..