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

Minji Kim·2022년 1월 3일
1
post-thumbnail

문제

문제 설명

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

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

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

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

원소의 개수가 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 이하인 경우만 입력으로 주어집니다.

입출력 예

sresult
"{{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을 알고 있었다면 훨씬 빨리 풀었을 것이다.
아직 많이 부족하고 알아야 할 것이 많다.
낙담하지 말고 열심히 코테 하자! 👊

profile
iOS Developer

0개의 댓글