[Swift | 프로그래머스 Lv.2] 튜플 (2019 카카오 개발자 겨울 인턴십)

Minji Kim·2022년 1월 3일

level2 swift 카카오 코딩테스트 튜플 프로그래머스

프로그래머스 코딩테스트 Lv.2

목록 보기

7/12

문제

문제 설명

셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, 다음과 같이 표현할 수 있습니다.

(a1, a2, a3, ..., an)

튜플은 다음과 같은 성질을 가지고 있습니다.

중복된 원소가 있을 수 있습니다. ex : (2, 3, 1, 2)
원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플입니다. ex : (1, 2, 3) ≠ (1, 3, 2)
튜플의 원소 개수는 유한합니다.

원소의 개수가 n개이고, 중복되는 원소가 없는 튜플 (a1, a2, a3, ..., an)이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다.

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

예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는

{{2}, {2, 1}, {2, 1, 3}, {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}}

는 모두 같은 튜플 (2, 1, 3, 4)를 나타냅니다.

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

s의 길이는 5 이상 1,000,000 이하입니다.
s는 숫자와 '{', '}', ',' 로만 이루어져 있습니다.
숫자가 0으로 시작하는 경우는 없습니다.
s는 항상 중복되는 원소가 없는 튜플을 올바르게 표현하고 있습니다.
s가 표현하는 튜플의 원소는 1 이상 100,000 이하인 자연수입니다.
return 하는 배열의 길이가 1 이상 500 이하인 경우만 입력으로 주어집니다.

입출력 예

s	result
"{{2},{2,1},{2,1,3},{2,1,3,4}}"	[2, 1, 3, 4]
"{{1,2,3},{2,1},{1,2,4,3},{2}}"	[2, 1, 3, 4]
"{{20,111},{111}}"	[111, 20]
"{{123}}"	[123]
"{{4,2,3},{3},{2,3,4,1},{2,3}}"	[3, 2, 4, 1]

입출력 예 설명

입출력 예 #1
문제 예시와 같습니다.

입출력 예 #2
문제 예시와 같습니다.

입출력 예 #3
(111, 20)을 집합 기호를 이용해 표현하면 {{111}, {111,20}}이 되며, 이는 {{20,111},{111}}과 같습니다.

입출력 예 #4
(123)을 집합 기호를 이용해 표현하면 {{123}} 입니다.

입출력 예 #5
(3, 2, 4, 1)을 집합 기호를 이용해 표현하면 {{3},{3,2},{3,2,4},{3,2,4,1}}이 되며, 이는 {{4,2,3},{3},{2,3,4,1},{2,3}}과 같습니다.

풀이

나의 풀이

func solution(_ s:String) -> [Int] {
    var result = [Int]()
    var dic = [Int : Int]()
    
    // [1]
    // s를 숫자만 담긴 배열로 만들기
    // ex) "{{2},{2,1},{2,1,3},{2,1,3,4}}" -> [2, 2, 1, 2, 1, 3, 2, 1, 3, 4]
    let arr = s.components(separatedBy: ["{", "}", ","]).filter { !$0.isEmpty }.map { Int($0)! }
    
    // [2]
    // 숫자를 counting해서 딕셔너리에 값 넣기 [해당숫자 : 개수]
    arr.forEach {
        dic.updateValue((dic[$0] ?? 0) + 1, forKey: $0)
    }
    
    // [3]
    // 개수가 많은 순으로 해당 숫자를 result 배열에 담기
    dic.values.sorted(by: >).forEach {
        result.append(dic.someKey(forValue: $0)!)
    }
    return result
}

// 딕셔너리 확장
// 해당 value를 가진 key 값을 가져올 수 있다.
extension Dictionary where Value: Equatable {
    func someKey(forValue val: Value) -> Key? {
        return first(where: { $1 == val })?.key
    }
}

정확성	테스트	정확성	테스트
테스트 1 〉	통과 (0.34ms, 16.6MB)	테스트 2 〉	통과 (0.31ms, 16.4MB)
테스트 3 〉	통과 (0.35ms, 16.5MB)	테스트 4 〉	통과 (0.54ms, 16.5MB)
테스트 5 〉	통과 (3.07ms, 16.6MB)	테스트 6 〉	통과 (4.40ms, 16.7MB)
테스트 7 〉	통과 (55.26ms, 16.8MB)	테스트 8 〉	통과 (168.47ms, 17.8MB)
테스트 9 〉	통과 (86.12ms, 16.9MB)	테스트 10 〉	통과 (180.72ms, 19.6MB)
테스트 11 〉	통과 (234.38ms, 19.9MB)	테스트 12 〉	통과 (349.94ms, 20.8MB)
테스트 13 〉	통과 (350.94ms, 20.7MB)	테스트 14 〉	통과 (376.85ms, 20.6MB)
테스트 15 〉	통과 (0.31ms, 16.6MB)

다른 사람의 풀이

import Foundation

func solution(_ s:String) -> [Int] {
    var result: [Int] = []

    // [1]
    // s를 배열로 만들기
    // ex) "{{2},{2,1},{2,1,3},{2,1,3,4}}" -> [[2], [2, 1], [2, 1, 3], [2, 1, 3, 4]]
    var sets = s.split(omittingEmptySubsequences: true, whereSeparator: { "}".contains($0) }).map {
        $0.split(omittingEmptySubsequences: true, whereSeparator: { "{,".contains($0) }).map { Int($0)! }
    }

    // [2]
    // 원소의 개수를 기준으로 오름차순 정렬하기
    sets.sort { (lhs, rhs) -> Bool in
        lhs.count < rhs.count
    }

    // [3]
    // Set의 subtracting을 이용해서 result와 겹치지 않는 것을 골라내기
    // ex) Set($0) = [2, 3], result = [3] 일 때
    //     Set($0).subtracting(result) = [2]
    sets.forEach {
        result.append(Array(Set($0).subtracting(result)).first!)
    }

    return result
}

정확성	테스트	정확성	테스트
테스트 1 〉	통과 (0.28ms, 16.5MB)	테스트 2 〉	통과 (0.24ms, 16.5MB)
테스트 3 〉	통과 (0.21ms, 16.4MB)	테스트 4 〉	통과 (0.52ms, 16.4MB)
테스트 5 〉	통과 (2.02ms, 16.4MB)	테스트 6 〉	통과 (4.46ms, 16.7MB)
테스트 7 〉	통과 (62.56ms, 17MB)	테스트 8 〉	통과 (202.05ms, 17.4MB)
테스트 9 〉	통과 (103.34ms, 17MB)	테스트 10 〉	통과 (213.17ms, 17.3MB)
테스트 11 〉	통과 (330.83ms, 17.5MB)	테스트 12 〉	통과 (501.99ms, 18.1MB)
테스트 13 〉	통과 (533.93ms, 18.2MB)	테스트 14 〉	통과 (495.36ms, 18.4MB)
테스트 15 〉	통과 (0.32ms, 16.4MB)

정리

⏰
목표 풀이 시간 : 1시간
실제 풀이 시간 : 1시간 27분

이 문제는 2019년 카카오 개발자 겨울 인턴십을 위해 출제된 문제로 총 5문제 중 두 번째로 출제되었다.

해설

참고

특정 튜플을 나타내는 집합이 주어질 때, 이를 이용해 원래 튜플을 구하는 문제입니다. 튜플로 변환해야 하는 집합이 문자열 형태로 주어지므로 먼저 각 집합에 속한 원소들을 분리합니다. ‘{‘, ‘}’ 기호 안에 있는 숫자들을 ‘,’를 기준으로 분리한 후, 각 원소를 배열에 넣습니다. 예를 들어 문제에 주어진 예시 5번의 경우 “{{4,2,3},{3},{2,3,4,1},{2,3}}”를 분리해 배열에 넣은 모습은 아래와 같습니다.

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

튜플의 첫 번째 원소까지 들어간 집합의 크기는 1, 두 번째 원소까지 들어간 집합의 크기는 2 … n 번째 원소까지 들어간 집합의 크기는 n이므로, 위에서 분리한 배열들을 길이 순서로 오름차순 정렬합니다.

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

이제, 집합의 길이가 1인 첫 번째 배열이 튜플의 첫 번째 원소를 나타낸다는 사실은 쉽게 알 수 있습니다. 또, 원소 수가 K인 집합과 K – 1인 집합의 차집합(단, K > 1)의 원소가 튜플의 K번째 원소를 나타낸다는 사실도 알 수 있습니다.

예를 들어 원소 수가 2인 집합 {2, 3}과 원소 수가 1인 집합 {3}의 차집합 {2, 3} – {3} = {2}이므로 구해야 하는 튜플의 두 번째 원소는 2가 됩니다. 마찬가지로 원소 수가 3, 4인 집합에 대해서도 차집합을 구해주면 구해야 하는 튜플은 (3,2,4,1)이 됩니다. 이때, 차집합은 길이가 K – 1인 배열에 없는 숫자를 길이가 K인 배열에서 찾는 방식으로 구현해주면 됩니다.

후기

너무 부끄럽지만 Set의 subtracting이 있다는 걸 이제 알았다..
처음에 다른 사람의 풀이와 동일한 원리로 풀어야겠다고 생각했지만 일일이 배열을 돌면서 result에 넣은 값을 삭제하고 이걸 반복한다는 것은 시간이 너무 오래 걸리기에 다른 방식으로 푼 것이다.

subtracitng을 알고 있었다면 훨씬 빨리 풀었을 것이다.
아직 많이 부족하고 알아야 할 것이 많다.
낙담하지 말고 열심히 코테 하자! 👊