프로그래머스 스타 수열 Kotlin (그리디)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/70130

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

문제 설명

다음과 같은 것들을 정의합니다.

• 어떤 수열 x의 부분 수열(Subsequence)이란, x의 몇몇 원소들을 제거하거나 그러지 않고 남은 원소들이 원래 순서를 유지하여 얻을 수 있는 새로운 수열을 말합니다.
  • 예를 들어, [1,3]은 [1,2,3,4,5]의 부분수열입니다. 원래 수열에서 2, 4, 5를 제거해서 얻을 수 있기 때문입니다.
• 다음과 같은 조건을 모두 만족하는 수열 x를 스타 수열이라고 정의합니다.
  • x의 길이가 2 이상의 짝수입니다. (빈 수열은 허용되지 않습니다.)
  • x의 길이를 2n이라 할 때, 다음과 같은 n개의 집합 {x[0], x[1]}, {x[2], x[3]}, ..., {x[2n-2], x[2n-1]} 의 교집합의 원소의 개수가 1 이상입니다.
  • x[0] != x[1], x[2] != x[3], ..., x[2n-2] != x[2n-1] 입니다.
  • 예를 들어, [1,2,1,3,4,1,1,3]은 스타 수열입니다. {1,2}, {1,3}, {4,1}, {1,3} 의 교집합은 {1} 이고, 각 집합 내의 숫자들이 서로 다르기 때문입니다.

1차원 정수 배열 a가 매개변수로 주어집니다. a의 모든 부분 수열 중에서 가장 길이가 긴 스타 수열의 길이를 return 하도록 solution 함수를 완성해주세요. 이때, a의 모든 부분 수열 중에서 스타 수열이 없다면, 0을 return 해주세요.

---

제한사항

• a의 길이는 1 이상 500,000 이하입니다.
  • a의 모든 수는 0 이상 (a의 길이) 미만입니다.

입출력 예 설명

입출력 예 #1

• a의 부분 수열 중에서 주어진 조건을 모두 만족하는 스타 수열이 없으므로, 0을 return 해야 합니다.

입출력 예 #2

• [5,2,5,3], [5,3,3,5] 는 a의 부분 수열인 동시에 스타 수열입니다. a의 부분 수열 중 이보다 더 긴 스타 수열은 없으므로, 4를 return 해야 합니다.

입출력 예 #3

• [0,3,3,0,7,0,2,0] 는 a의 부분 수열인 동시에 스타 수열입니다. a의 부분 수열 중 이보다 더 긴 스타 수열은 없으므로, 8을 return 해야 합니다.

※ 공지 - 2020년 11월 27일 테스트케이스가 추가되었습니다.

풀이

이 문제를 풀기 위해선 크게 두 가지 과제가 있다.

1. 탐색 방법 구하기

2. 탐색 가짓수 줄이기

우선 탐색 방법을 찾아야 하기 위해선 주어진 요구 사항을 먼저 이해해야 한다.

 

a란 배열에서 요소를 두 개씩 묶은 부분 수열들을 구한다.

편의상 두 개씩 묶은 부분 수열을 짝수열이라고 하겠다.ㅋㅋ 

1. 이 부분 수열들은 모두 하나의 공통 요소를 가져야 한다.(교집합)

2. 부분 수열의 첫 번째 요소와 두 번째 요소는 같아선 안된다.

요구사항을 정리하면 두 개씩 묶은 부분 수열들을 구할 것이니 x가 짝수라는 것은 무시하고 위 두 가지 조건을 만족하는 것이 '스타 수열'이고, 우리가 찾는 답은 가장 긴 '스타 수열'의 길이이다.

 

1번 교집합 조건을 잘 생각해 보자.

가장 긴 '스타 수열'을 만들다 보면 어떠한 숫자가 모든 짝수열에 하나 들어가 있다는 것인데(2번 조건에 의해 같은 값이 들어갈 수 없으므로 1개) 그럼 가장 긴 스타 수열은 일단 주어진 배열에 많이 등장하는 숫자를 공통 숫자로 만드는 게 유리하다는 것을 알 수 있다.

그렇다고 가장 많이 등장하는 숫자를 사용해서 만든 '스타 수열'이 가장 긴 '스타 수열'이란 보장은 없다. 이 반례는 쉽게 만들 수 있다.

하지만 이를 이용할 수는 있을 것 같다.(Hint)

일단 여기까지 알아낸 정보로 구현을 하자면, 배열에 등장한 숫자들이 몇 번씩 나왔는지 횟수를 배열에 따로 저장해 놓고,

각각의 숫자들을 이용해서 '스타 수열'을 만들어 보자.

괜히 '스타 수열'에 작은따옴표를 붙였다. 너무 귀찮다.

무튼 3번 입력을 예로 들면,

0 = 4번

2 = 3번

3 = 2번

7 = 1번

위의 정보들을 저장해 놓고, 0을 공통 숫자로 스타 수열, 2를 공통 숫자로 스타 수열, ~~~ , 7을 공통 숫자로 스타 수열을 만들어 보는 것이다. 스타 수열을 만드는 것은 구현의 영역으로 1번 조건과 2번 조건에 맞게 구현하면 된다.

그러면 최대 O(50만^2)의 시간 복잡도 풀이가 나온다.

 

이제 우리가 처음 정의한 두 번째 과제를 풀어야 한다.

탐색 가짓수를 어떻게 줄일 수 있을까.

위에 올려보면 Hint가 있다.

직접적인 Hint는 아니지만 저 부분에서 그리디한 사고를 하기 때문에 충분히 이 솔루션이 생각날 수 있따.

만약 0을 공통 숫자로 해서 스타 수열을 만들었고, 이 길이가 8이라고 하자. 그럼 0은 4번 사용된 것이다.

오?!

지금 생각하는 그거 맞다.

현재 구한 가장 긴 스타 수열의 길이는 8이고 사용된 숫자 횟수는 4다.(0을 4개)

그럼 2를 공통 숫자로 만든다고 했을 때, 2는 배열에 3번밖에 안 나오므로, 죽었다 깨어나도 스타 수열의 길이가 6을 넘을 수 없다.

이는 탐색을 하지 않아도 알 수 있는 사실이다. 따라서 얘는 탐색을 하지 않는다!

결론 : 현재 구한 스타 수열의 길이에 이용된 숫자 횟수(길이/2)보다 다음 탐색할 숫자의 배열 등장 횟수가 적다면 탐색 스킵!

만약 횟수가 같은 경우는 탐색해 주어야 한다. 0이 4번 나온다고 해서 스타 수열의 길이가 8이라는 보장이 없다.

 

이렇게 1번 과제와 2번 과제를 해결하여 최대 36.96ms(코틀린 기준)으로 통과했다.

근데 의문이 든다.

만약 극악 케이스로 50만 개의 숫자가 다 다른 값이 들어온다고 하면,

결국 위의 풀이도 O(50만^2)의 시간 복잡도로 터질 텐데...

그런 테케는 없어서 통과된 것 같은데 찝찝하다...라고 생각하다 보니 지금 글 쓰다가 생각난 건데,

해결 법이 생각났다.

            //현재 나온 스타 수열의 길이보다 배열에 나온 횟수가 적은 숫자는 검사할 필요 없음
            //answer는 스타 수열의 길이가 아니라 스타 수열의 길이가 최대일 때 사용한 공동 숫자의 등장 횟수다.
            if (answer > cnt) continue
            
            //정답 출력은 일케 하고 있었음
            return answer*2

이 부분을

           //현재 구한 스타 수열의 길이로 비교
           // cnt가 2일 때, 이미 구한 길이가 2로 구할 수 있는 최대 길이인 4이상이라면 스킵!
           // 그러면 cnt가 계속 1 1 1 1 1 1 1 1 1인 경우도 한 번만 검사하고 나머진 스킵 가능하다.
           if (answer*2 >= cnt*2) continue

이렇게 바꾸면 더 완벽한 풀이가 된다!! 요런 뽀인트 중요하지 채점도 안 해주는 코테에 이런 케이스 때문에 틀리면 이거 어떡할 거야 이거

최대 31.47ms로 바뀌었다.

포스팅하는 동안 성장해 버렸다.

두 코드 모두 그 극악 케이스가 테케로 들어있진 않아서 시간 초과 없이 통과하는데,

극악 케이스가 추가된다면 아마 첫 번째 코드는 시간 초과가 뜰 것이다.

코드만 보면 크게 달라진 건 없지만 엄청난 차이다..!

코드1

class Solution {
    /*
    * a에서 부분 수열 뽑기 a 50만
    * 짝수, 길이 2이상
    * 순서대로 2개씩 묶은 n개의 집합의 교집합이 1개 이상
    * x[i]!=x[i+1]
    * */
    var answer = 0
    fun solution(a: IntArray): Int {
        val cntArr = IntArray(a.size + 1)
        for (num in a) {
            cntArr[num]++
        }

        for (i in cntArr.indices) {
            val cnt = cntArr[i]
            //배열에 없는 수는 스팁
            if (cnt == 0) continue
            //현재 나온 스타 수열의 길이보다 배열에 나온 횟수가 적은 숫자는 검사할 필요 없음
            if (answer > cnt) continue
            var hasI = false
            var hasOther = false
            var len = 0
            for (idx in a.indices) {
                //공통 수 만났을 때
                if (a[idx] == i) {
                    hasI = true
                    //공통 수가 x[i],x[i+1]에서 x[i+1]인 경우
                    if (hasOther) {
                        len++
                        hasI = false
                        hasOther = false
                    }
                }
                //다른 수 만났을 때
                else {
                    hasOther = true
                    //공통 수가 x[i],x[i+1]에서 x[i]인 경우
                    if (hasI) {
                        len++
                        hasI = false
                        hasOther = false
                    }
                }
            }
            answer = answer.coerceAtLeast(len)
        }
        return answer * 2
    }
}

코드2

class Solution {
    /*
    * a에서 부분 수열 뽑기 a 50만
    * 짝수, 길이 2이상
    * 순서대로 2개씩 묶은 n개의 집합의 교집합이 1개 이상
    * x[i]!=x[i+1]
    * */
    var answer = 0
    fun solution(a: IntArray): Int {
        val cntArr = IntArray(a.size + 1)
        for (num in a) {
            cntArr[num]++
        }

        for (i in cntArr.indices) {
            val cnt = cntArr[i]
            //배열에 없는 수는 스팁
            if (cnt == 0) continue
           //현재 구한 스타 수열의 길이로 비교
           // cnt가 2일 때, 이미 구한 길이가 2로 구할 수 있는 최대 길이인 4이상이라면 스킵!
           // 그러면 cnt가 계속 1 1 1 1 1 1 1 1 1인 경우도 한 번만 검사하고 나머진 스킵 가능하다.
            if (answer*2 >= cnt*2) continue
            var hasI = false
            var hasOther = false
            var len = 0
            for (idx in a.indices) {
                //공통 수 만났을 때
                if (a[idx] == i) {
                    hasI = true
                    //공통 수가 x[i],x[i+1]에서 x[i+1]인 경우
                    if (hasOther) {
                        len++
                        hasI = false
                        hasOther = false
                    }
                }
                //다른 수 만났을 때
                else {
                    hasOther = true
                    //공통 수가 x[i],x[i+1]에서 x[i]인 경우
                    if (hasI) {
                        len++
                        hasI = false
                        hasOther = false
                    }
                }
            }
            answer = answer.coerceAtLeast(len)
        }
        return answer * 2
    }
}