[프로그래머스] Swift - 스타 수열

https://school.programmers.co.kr/learn/courses/30/lessons/70130

프로그래머스

 

2023.08.25 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

• 수열 a가 주어짐
• a의 부분수열들을 구함
• 부분 수열 중에서 스타 수열인 수열의 길이의 최댓값을 리턴

 

스타 수열 x의 조건

1. x의 길이는 2 이상의 짝수
2. x의 길이를 2n이라고 할 때 {x[0], x[1]}, {x[2], x[3]} ... {x[2n-2], x[2n-1]} 의 교집합의 원소의 개수가 1 이상
3. x[0] != x[1], x[2] != x[3], ... x[2n-2] != x[2n-1]

이렇게 3가지 조건입니다.

 

정리해보면 수열 x의 요소들을 순서대로 2개씩 묶어서 봤을 때 그 둘의 요소들이 같지 않아야 하며 2개씩 묶은 것들을 전체 교집합 했을 때 해당 교집합의 크기가 1이상이어야 합니다.

즉, 각 묶음끼리 겹치는 요소를 1개 이상을 가지고 있어야 합니다.

이때의 x길이의 최댓값을 구해야 합니다.

 

 

스타 수열의 조건을 잘 생각해보면 각 묶음 마다 겹치는 수가 1개씩 있어야 하므로 x의 길이를 최대한 키울려면 중복되는 수가 많이 필요합니다.

따라서 a를 한번 쭉 순회하면서 각 요소들이 몇번 등장하는지 기록해두었다가 해당 요소들을 기준으로 탐색을 진행하면 될 것 같습니다.

저는 cnt라는 이름의 딕셔너리를 만들어서 기록했습니다.

 

var cnt = [Int: Int]() // key: a의 요소, value: 해당 key가 a에 몇개 존재하는지 개수를 저장

 

이제 cnt의 키값들을 순회하면서 해당 키가 x의 교집합인 경우일 때 스타수열을 만들면 길이가 몇일지를 구합니다.

스타 수열의 3번 조건을 검증하는 것입니다.

 

예를 들어 a = [1, 1, 5, 2, 5, 3, 5, 6] 라면

이때 cnt[5] = 3입니다. a에서 5가 3번 있다는 의미입니다.

이렇게 5와 다른 숫자가 붙어 있다면 5,2 | 5,3 | 5,6 이렇게 3 묶음을 만들 수 있고 x의 길이가 6이 됩니다.

 

cnt의 키값을 num이라고 이름 붙이고 a를 순회하며 a[i] == num 이거나 a[i+1] == num인 경우를 찾습니다.

이 경우가 스타 수열 x에 추가할 후보입니다.

그리고 a[i] != a[i+1]이라면 스타 수열 조건 3번에 만족합니다.

➡️ 스타 수열에 추가 (우리는 길이만 필요하기 때문에 길이만 기록합니다.)

이 경우에는 i+1를 한번 더 해줘서 중복 검사를 방지합니다.

 

a[i] == num 또는 a[i+1] == num 이지만 a[i] == a[i+1]인 경우는 3번 조건에 어긋나기 때문에 제외합니다.

 

 

이렇게 기록한 스타 수열 길이의 최댓값을 리턴합니다.

 

 

풀이

fileprivate func solution(_ a:[Int]) -> Int {
    var answer = 0
    
    var cnt = [Int: Int]() // key: a의 요소, value: 해당 key가 a에 몇개 존재하는지 개수를 저장
    
    for num in a {
        cnt[num, default: 0] += 1
    }
    
    for num in cnt.keys {
        if cnt[num]! <= answer {
            continue
        }
        
        var result = 0
        
        var i = 0
        
        while i < a.count-1 {
            if (a[i] == num || a[i+1] == num) && (a[i] != a[i+1]) {
                result += 1
                i += 1
            }
            
            i += 1
        }
        
        answer = max(answer, result)
    }
    
    
    return answer*2
}

if cnt[num]! <= answer { continue } 를 하지 않으면 시간 초과가 발생합니다. 이미 구한 스타수열 길이의 최댓값보다 더 작은 길이인 경우는 검증할 필요가 없기 때문에 continue로 넘어갑니다.

 

마무리

문제 조건에 맞는 풀이법을 잘 찾아야 했습니다.

교집합이 존재해야 하기 때문에 일단 1개의 요소는 각 묶음마다 들어가야 했습니다. -> 중복되는 요소가 1개 필요함

이를 딕션너리에 저장하고 딕셔너리에 들어있는 key값들만 비교하여 비교군을 축소시켰습니다.

 

또한 현재까지 구한 스타 수열 길이의 최댓값보다 해당 key값으로 구할 수 있는 스타 수열의 길이가 작다면 더 이상 검사하지 않고 continue를 시켜 시간을 대폭 단축시킬 수 있었습니다.