[카카오] 튜플

• 2019 KAKAO 겨울 인턴십
• 튜플
• Level 2

 

문제

• 튜플은 중복된 원소가 있을 수 있으나, 순서가 다르면 서로 다른 튜플이다

 

• 이 때, 중복 값이 없는 튜플 (a1, a2, a3, …, an) 이 주어질 때, 이 것은 다음과 같이 표현될 수 있다

→ {{a1}, {a1,a2}, {a1,a2,a3}, ..., {a1,a2,a3,...,an}}

• 예로. 튜플이 (2, 1,  3, 4) 이면 다음과 같이 표현될 수 있다.
• 집합은 순서가 없으므로 집합 내 순서가 바뀔 수 있다.

→ {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

→ {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}

→ {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}

 

• 특정 튜플을 표현하는 집합이 담긴 문자열 s 가 주어질 때, s 가 표현하는 튜플을 배열에 담아 반환하기
• 예. s → “{{2},{2,1},{2,1,3},{2,1,3,4}}”, result → [2, 1, 3, 4]

 

• s 는 숫자, {, }, , 로만 이루어짐
• s 의 길이는 5 이상 1,000,000 이하
• 숫자는 1이상 100,000 이하
• 반환되는 배열의 길이는 1이상 500 이하

 

Idea

• 일단 집합 내 순서가 보장되지 않기 때문에 집합 내 원소 개수가 하나인 집합부터 n 개인 집합 순으로 정렬해야 한다고 생각함
• 그래서 처음부터 새롭게 나오는 숫자를 차례로 저장하면 원하는 튜플을 얻을 수 있음

 

• 따라서 각각의 집합 내 숫자와 , 만 있는 문자열 배열로 먼저 변환 후, 길이 순으로 정렬

→ [”1,2,3”, “2,1”, “1,2,4,3”, “2”]

→ [“2”, “2,1”, ”1,2,3”, “1,2,4,3”]

• 각각의 문자열을 다시 ,로 분리하여 숫자만 있는 집합으로 만듬

→ [[2], [2,1], [1,2,3], [1,2,4,3]]

• 그 다음 결과를 담는 배열과 새로 만든 집합을 차집합 연산을 해서 새로 추가된 값을 구함
• 새로 추가된 값을 결과 배열에 추가

 

Code

Swift

import Foundation

func solution(_ s:String) -> [Int] {
    
    let sets = Array(s)[2...s.count-3].map { String($0) }
            .joined(separator: "").components(separatedBy: "},{")
            .sorted { $0.count < $1.count }
    
    var answer: [Int] = []
    for subset in sets {
        let numbers = Set(subset.components(separatedBy: ",").map { Int($0)! })
        let diff = Array(numbers.subtracting(Set(answer)))
        answer += diff
    }
    
    return answer
}