[Swift] 프로그래머스 월간 코드 챌린지1 스타 수열

Problem

 

코딩테스트 연습 - 스타 수열

---

Solution

 

1. a에 있는 숫자들의 갯수를 세준다.

 

숫자들의 갯수를 세주는 이유는 갯수가 많은 숫자로 정렬하여 시간 초과를 막기 위해서 입니다.

 

func countNumbers(a:[Int]) -> [Int:Int] {
    var countDic:[Int:Int] = [:]
    for n in a {
        if countDic[n] == nil {
            countDic[n] = 1
        }else {
            countDic[n]! += 1
        }
    }
    return countDic
}

 

2. 각 숫자들의 가장 긴 부분 수열 길이를 구해준다.

 

간단하게 설명하면 각 숫자들의 앞 뒤를 비교해줍니다.

 

만약 앞과 뒤 중 하나라도 현재 숫자와 같지 않은 숫자가 있다면 +2 해줍니다.

 

그 다음 해당 숫자를 현재 숫자로 바꿔줍니다.

 

func findLongSubsequence(n:Int,a:[Int]) -> Int {
    var numbers = a
    var length:Int = 0
    if a[0] == n && a[1] != n {
        length += 2
        numbers[1] = n
    }
    for i in 1..<numbers.count-1 {
        if a[i] == n {
            if numbers[i-1] != n {
                numbers[i-1] = n
                length += 2
            }else if numbers[i+1] != n  {
                numbers[i+1] = n
                length += 2
            }
        }
    }
    if numbers[a.count-1] == n && numbers[a.count-2] != n {
        length += 2
    }
    return length
}

 

3. 각 숫자들의 가장 긴 부분 수열 길이 중 가장 긴 것을 반환한다.

 

시간 초과를 막기 위해 숫자의 갯수가 더 많은 것으로 정렬한 다음 순환을 진행합니다.

 

만약 answer보다 숫자의 갯수 * 2가 더 작다면 answer보다 더 클 수가 없으므로  다음으로 넘어가줍니다.

 

func findMaxLength(a:[Int]) -> Int {
    var answer:Int = 0
    let sortCounts = countNumbers(a: a).sorted{$0.value > $1.value}
    for dic in sortCounts {
        if dic.value * 2 < answer { continue }
        let length = findLongSubsequence(n:dic.key, a:a)
        answer = max(answer,length)
    }
    return answer
}

---

Source Code

 

---

P.S

 

처음엔 가장 숫자의 갯수가 많은 것의 가장 긴 부분 수열을 찾아서 반환했다.

 

근데 계속 테스트 케이스 28번이 틀렸다...

 

그래서 질문하기를 통해 봤더니 만약 이렇게 a가 주어졌을경우 -> [4, 0, 0, 2, 1, 1, 1, 1, 1, 1, 1, 1, 0, 3]

 

1이 가장 많지만 가장 긴 부분 수열은 0을 이용해서 만들어야 한다...

 

그래서 결국 모든 숫자를 확인해봐야 했었다..