코딩테스트 연습 - 튜플

문제 풀이 아이디어

문제의 이름은 튜플이지만 사실 튜플과는 크게 관련이 없는 문제입니다.😅  문자열을 어떻게 다룰 것인가가 가장 메인입니다.

문자열을 숫자의 배열로

일단 문제를 풀기 위해서는 주어진 문자열을 통해서 집합을 n개 구해야 합니다. 즉 String을 [[Int]]로 변경해야 하는 것이죠. 단계별로 해보도록 하겠습니다. 문제에 주어진 테스트 케이스 1번인 "{{2},{2,1},{2,1,3},{2,1,3,4}}”로 진행해보도록 하겠습니다.

일단 전체를 감싸고 있는 중괄호를 제거합니다. 다만 제거할 때 전체를 감싸는 중괄호만 제거하지 말고 하나씩 더 제거해서 "2},{2,1},{2,1,3},{2,1,3,4”의 형태로 만들어주도록 합니다.

이렇게 하면 숫자의 집합 사이에 “},{”가 위치하게 됩니다. .components(separatedBy: "")를 활용해서 숫자와 콤마만 남은 문자열의 집합으로 바꾸어 줍니다. [”2”, “2,1”, “2,1,3”, “2,1,3,4”]이 됩니다.

이제부터는 평소에 많이 하던 작업입니다. .split(separator: ",").map{ Int($0)! }을 통해서 콤마 정수의 배열로 바꾸면 됩니다. [[2], [2, 1], [2, 1, 3], [2, 1, 3, 4]]가 됩니다.

✅ split()과 component()

제가 예전에 작성한 이 포스팅을 보시면 component()를 사용했을 때 시간초과로 통과하지 못한 코드가 split()으로 바꾸고 나서 통과한 것을 볼 수 있는데요. 저 포스팅에서 저는 component 대신에 split이 빠르므로 split를 사용하는 것이 좋다고 적었습니다.

하지만 component가 split에 비해서 좋지 않은 것은 아닙니다. component의 장점은 인자로 String을 받는다는 점입니다. 위에서 우리는 “},{”를 기준으로 문자열을 나눈 적이 있는데요. Character를 인자로 받는 split으로는 불가능한 작업입니다. 필요한 때에 맞춰 적절히 활용합시다!

튜플 구하기

이제 튜플을 구하는 것은 쉽습니다. 문제의 조건에 의하면 우리가 구한 배열에서 길이가 1인 배열의 원소는 무조건 튜플의 첫 원소가 됩니다. 그리고 길이가 2인 배열은 튜플의 첫번째, 두 번째 원소를 가지고 있습니다. 순서는 섞여 있을 수도 있다고 했으므로 튜플의 첫번째 원소가 아닌 원소가 튜플의 2번째 원소가 될 것입니다. 이와 같은 방식으로 n번째 원소까지 구하면 됩니다. [[2], [2, 1], [2, 1, 3], [2, 1, 3, 4]]의 예시를 다시 볼까요?

길이가 1인 배열의 원소가 2이므로 튜플의 첫 원소는 2가 됩니다. 그리고 다음 길이가 2인 배열의 원소는 [2, 1]인데 튜플은 중복되는 원소가 없다고 했으므로 튜플의 두번째 원소는 1입니다. 이렇게 튜플을 채우고 다음 길이의 배열에서 기본 튜플에 없는 원소를 하나 찾아서 튜플을 채워나가면 됩니다.

코드

import Foundation

func solution(_ s:String) -> [Int] {
    
    // 앞 뒤에 괄호 2개씩 지우기
    var s = s
    s.removeFirst(2)
    s.removeLast(2)

    // String을 [[Int]]로 변형하기
    let arr = s
        .components(separatedBy: "},{")
        .map { $0.split(separator: ",").map{ Int($0)! } }
        .sorted { $0.count < $1.count }
        //👉 짧은 배열로 정렬

    // 정답을 담는 배열
    var ans = [Int]()

    // 길이가 1인 배열 부터 순회하면서
    for nums in arr {
        for num in nums {
            // 기존의 튜플 (= ans)에 없는 원소가 다음 튜플의 원소
            if !ans.contains(num) {
                ans.append(num)
                break
            }
        }
    }

    return ans
}

시간복잡도를 개선해보자.

위 코드의 실행시간을 보면 1초를 넘어가는 테스트 케이스들이 보입니다. 코드에서 가장 시간을 많이 잡아먹는 부분이 어디일까요?

문자열을 조작하는 부분은 단 1번만 실행이 되므로 실행시간과는 큰 관련이 없습니다. 하지만 마지막 반복문 부분에 있는 ans.contain()의 시간 복잡도는 O(N)입니다. (N은 ans의 길이) 따라서 위 코드는 이중반복문이라도 contain 때문에 삼중반복문, 즉 O(N^3)의 시간복잡도를 가지고 있는 것과 같습니다. 튜플의 최대 길이가 500이라고 했으므로 시간초과까지는 아니어도 부담스러운 시간복잡도입니다. (물론 정확히 O(N^3)인 것은 아닙니다. num의 길이는 1에서 시작해서 점증하므로 O(N^3) 보다는 작습니다.)

아래 2가지 방법을 통해서 O(N)인 contain을 쓰지 않고 O(1)인 방법으로 교체해서 전체 시간복잡도를 O(N^2)로 줄이고 실행시간을 줄여보겠습니다.

dictionary (= hash table)을 활용하는 법

첫번째 방법은 dictionary를 사용하는 방법입니다. dictionary를 활용해서 중복 체크를 하면 O(1)로 중복체크를 할 수 있습니다. 실행시간이 최대 4배까지 빨라졌습니다.

import Foundation

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

    var s = s
    s.removeFirst(2)
    s.removeLast(2)

    let arr = s
        .components(separatedBy: "},{")
        .map { $0.split(separator: ",").map{ Int($0)! } }
        .sorted { $0.count < $1.count }

    var ans = [Int<]()
    var dict = [Int : Bool]()

    for nums in arr {
        for num in nums {
            if !dict[num, default: false] {
                ans.append(num)
                dict[num] = true
            }
        }
    }

    return ans
}

길이가 N인 배열을 활용하는 법

다음은 길이가 N인 배열을 사용하는 방법입니다. 이 방법은 튜플의 원소의 범위가 주어졌기 때문에 활용할 수 있습니다. 문제의 조건에 의하면 튜플의 원소는 1이상 100,000 이하의 자연수입니다. 따라서 길이가 100,001인 배열을 선언해서 중복체크에 활용할 수 있습니다. 마찬가지로 O(1)입니다. 실행시간은 dictionary를 사용한 방법과 거의 동일합니다.

import Foundation

func solution(_ s:String) -> [Int] {
    
    var s = s
    s.removeFirst(2)
    s.removeLast(2)
    
    let arr = s
        .components(separatedBy: "},{")
        .map { $0.split(separator: ",").map{ Int($0)! } }
        .sorted { $0.count < $1.count }
    
    print(arr)
    
    var ans = [Int]()
    var check = Array(repeating: false, count: 100001)
    
    for nums in arr {
        for num in nums {
            if !check[num] {
                ans.append(num)
                check[num] = true
            }
        }
    }
    
    return ans
}