[ 프로그래머스 [ 월간코드챌린지 ] 스타 수열 ] (C++)

프로그래머스의 스타수열(월간코드챌린지) 문제이다.

( 기존에 이 문제에 대한 풀이로 "가장 많이 등장한 숫자를 기준으로 스타 수열을 만드는 풀이" 로 포스팅을 하였으나,

  위의 방법으로는 문제를 정확하게 해결할 수 없다는 것을 알게되어서, 이를 수정하여 다시 포스팅 합니다. )

[ 문제풀이 ]

주어진 배열에서 조건에 맞는 스타수열을 만들었을 때, 가장 길이가 긴 스타수열을 구해야 하는 문제이다.

이 글의 가장 위에서 언급한대로, 위와 같이 해결했을 때의 문제점 및 반례들부터 수정된 풀이방법까지 천천히 알아보도록 하자.

#1. 스타수열의 조건

가장 먼저, 스타수열의 조건부터 다시한번 확인하고 가보자.

조건1 : 스타수열은 길이가 반드시 2 이상이여야 한다.

조건2 : 스타수열을 인접한 2개의 값씩 묶었을 때, 즉, [ 0번Index , 1번Index ] , [ 2번Index , 3번Index ]....

        와 같은 형태로 묶고, 저 한 묶음을 '집합'이라고 표현했을 때, 모든 집합의 교집합의 원소의 갯수가 1개

        이상 이어야 한다.

조건3 : 조건2와 같이 인접한 2개의 값씩 묶었을 때, 각 집합에 있는 2개의 값은 서로 다른 값이여야 한다.

본인 마음대로 조건들에 '1','2','3'으로 번호를 붙여주었다. 지금부터는 이 조건들을 이 번호로 이야기하도록 하겠다.

#2. 가장 많이 등장한 숫자를 기준으로 스타수열 만들기

본인이 위의 풀이로 이 문제에 대한 풀이를 포스팅 하였다.

이 풀이에 대해서 간략하게만 설명을 해보면...

1. 주어진 배열에서 가장 많이 등장하는 숫자를 찾는다.

2. 이 숫자를 "무조건적으로 선택" 하면서 스타수열을 만든다.

3. 이 경우가 무조건 스타수열의 최대길이가 된다.

위와 같은 풀이로 이야기를 했었다. 가장 많이 등장하는 숫자를 찾은 이유는, 조건2를 만족시키기 위해서였다.

교집합의 원소의 갯수가 1개 이상이여야 한다는 것은, 반드시 공통된 원소가 1개 이상은 있어야 한다는 것을 의미하고

이 때, 이 '공통된 원소'를 "배열에서 가장 많이 등장하는 숫자로 선택" 해준 것이다.

그리고 이 때의 스타수열의 길이가 가장 길다고 판단을 했었다.

하지만, 이 경우 스타수열의 길이가 가장 길지 않은 경우가 존재한다.

다음과 같은 경우를 한번 보자.

반례 : [ 1 , 1 , 1 , 1 , 1 , 1 , 2 , 3 , 2 , 4 ]

위의 방식대로 이 케이스를 한번 풀어보면 다음과 같이 풀이할 수 있다.

1. 가장 많이 등장하는 숫자 = 1

2. 1을 무조건적으로 선택하면서 스타수열을 만든다. = [ 1 , 2 ]

   이 때, [ 1 , 2 ]만 만들어지는 이유는 조건3 때문이다. 인접한 2개의 값이 절대로 같을 수는 없으니, [ 1 , 1 ] 은

   스타수열이 될 수가 없다. 따라서 '1'을 무조건적으로 선택하면서 만들 수 있는 스타수열은 [ 1 , 2 ]밖에 존재하지

   않는다.

3. 결론을 도출해보면 이 경우 스타수열의 길이 = 2가 된다.

하지만 딱 봐도 알겠지만 위의 케이스의 정답은 4이다. 왜냐하면 [ 2 , 3 , 2 , 4 ] 로 스타수열을 만들게 되면 길이가 2이상이고,

{ 2 , 3 } , { 2 , 4 } 로 '2'를 공통된 원소로 가지면서, 각각의 집합은 모두 서로 다른 값을 가질 수 있기 때문에 이 경우가

최대길이가 된다.

이런 반례가 존재함에도 불구하고, 위의 방식대로 문제를 해결해서 제출을 하면 pass를 받을 수가 있다.

#3. 모든 원소에 대한 탐색

#2에서 이야기했듯이, 가장 많이 등장하는 숫자를 기준으로만 탐색을 하는 것은 옳은 풀이가 될 수 없다.

따라서 본인은 모든 원소에 대한 탐색을 다 진행해주었다.

예를 들어서 다음과 같은 배열이 주어졌다고 가정해보자.

[ 1 , 2 , 1 , 3 , 2 , 4 , 3 , 5 , 6 , 7 , 3 , 8]

이런식의 배열이 주어졌다고 가정해보자.

그러면 여기서 모든 원소에 대해서 스타수열의 최대길이를 모두 구해보는 것이다.

가장 먼저 '1'을 스타수열의 공통된 원소로 삼았을 때 만들 수 있는 길이를 구해보자.

[ 1 , 2 , 1 , 3 ] 으로 스타수열을 만들면, 길이가 4인 스타수열을 만들 수 있다.

'2'를 스타수열의 공통된 원소로 삼았을 때는 [ 2 , 1 , 2 , 4 ] 로 길이가 4인 스타수열을 만들 수 있다.

'3'을 스타수열의 공통된 원소로 삼았을 때는 [ 3 , 2 , 3 , 5 , 3 , 8 ] 로 길이가 6인 스타수열을 만들 수 있다.

'4'를 스타수열의 공통된 원소로 삼았을 때는 [ 4 , 3 ] 으로 길이가 2인 스타수열을 만들 수 있다.

'5'를 ... '6'을... '7'을... '8'을 공통된 원소로 삼았을 때의 스타수열을 만들게 되면 길이가 '2'인 스타수열을 만들 수 있다.

즉, 우리가 구한 스타수열의 길이들은 [ 4 , 4 , 6 , 2 , 2 , 2 , 2 ... ] 뭐 이런식으로 구해질 것이다.

이 중 최대길이는 '6'이 되고, 실제로 이 케이스의 답은 '6'이 된다.

구하는 과정은 굉장히 간단하게 접근해볼 수가 있다.

1. 주어진 배열에 존재하는 값들을 다른 공간에 저장해준다.

2. 다른 공간에 저장해준 값을 하나씩 빼오면서, 해당 값을 '공통된 원소'로 설정한 뒤, 주어진 배열을 탐색하면서

   만들 수 있는 스타수열을 만들어 본다.

위의 예시를 이 방법처럼 접근해보자.

주어진 배열은 [ 1 , 2 , 1 , 3 , 2 , 4 , 3 , 5 , 6 , 7 , 3 , 8 ] 이 되고, 이 때 등장하는 값들을 저장해보면 다음과 같다.

[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]

그리고 이제부터는 가장 첫번째 값인 '1'부터 '8'을 순차적으로 '공통된원소'로 설정해주고 배열을 탐색해보면 된다.

배열을 탐색하는 과정에서는 다음과 같은 2가지 조건을 판단해 주면 된다.

1. 인접한 2개의 값을 봤을 때, 현재 공통된 원소로 설정해준 값이 존재하는지 ?

2. 인접한 2개의 값이 동일하지는 않은지 ?

먼저 1번 조건부터 알아보자.

1번조건을 탐색해 주어야 하는 이유는, 우리는 현재 '공통된 원소'로 사용할 값을 미리 지정해놓고 스타수열을 만드는 과정을 진행하고 있다. 즉, '공통된 원소'가 없는 값은 선택을 할 수 없기 때문에 이를 체크해주어야 한다.

이 때, 인접한 2개의 값 모두 확인해 주어야 한다는 것을 주의해주자.

다음과 같은 예를 한번 보자.

[ 1 , 2 , 1 , 3 , 4 , 1 ]

이 상황에서 현재 '1'을 공통된 원소로 지정해놓고 배열을 탐색을 한다고 가정해보자.

그리고 편의상 배열의 가장 첫 번째 값을 1번 Index, 가장 마지막 값을 6번 Index라고 표현하겠다.

가장 처음에 1번 Index를 보자. 공통된 원소로 설정한 '1'인 1번 Index에 존재하고, 1번Index와 2번Index가 다르니 1번과 2번 Index를 선택해주자.

현재까지 만든 스타수열 = [ 1 , 2 ]

2번 Index는 이미 선택되었으니 그 다음으로 넘어가서 3번 Index를 살펴보자.

공통된 원소로 설정한 '1'인 3번 Index에 존재하고, 3번 Index와 4번Index가 다르니 3번과 4번 Index를 선택해주자.

현재까지 만든 스타수열 = [ 1 , 2 , 1 , 3 ]

4번 Index까지 선택했으니 그 다음으로 넘어가서 5번 Index를 살펴보자.

공통된 원소로 설정한 '1'이 5번 Index에 존재하지 않는다. 그럼 여기서 그냥 넘어가주어야 할까 ??

아니다 ! 인접한 2개의 원소를 모두 확인해 주어야 한다.

6번 Index를 확인해보니 공통된 원소로 선택된 '1'이 존재한다. 따라서 , [ 4 , 1 ] 을 선택해준다.

이런 부분 때문에, "공통된 원소를 가지고 있는지에 대해서 판단을 할 때에는, 현재 탐색하는 Index뿐만 아닌, 그 다음 Index까지도 확인"을 해 주어야 한다.

2번 조건을 확인해주어야 하는 것은, 스타수열을 만족할 수 있는 조건들 중 3번 조건 때문이다.

그럼 이를 코드로 나타내면 다음과 같이 2중 for문으로 굉장히 간단하게 표현할 수가 있다.

for(공통된 원소로 선택할 값들에 대한 반복문)
{
    for(배열을 탐색하기 위한 반복문)
    {
        조건1 탐색.
        조건2 탐색.
    }
}
 

위와같이 간단하게 구할 수가 있다.

여기까지 정리해보자.

1. 배열에 등장하는 값들을 새로운 저장공간에 저장해준다. 이를 vector<int> V 라고 표현해 보겠다.

2. V를 순차적으로 탐색한다. 왜냐하면 V에 들어있는 값들을 하나씩 꺼내오면서 그 값을 '공통된 원소' 로 설정할

  것이기 때문이다.

3. 공통된 원소로 사용할 값을 구했다면, 배열을 탐색하면서 스타수열의 길이를 구한다.

4. 최종적으로 스타수열의 최대 길이를 구한다.

#4. 문제점

#3의 과정처럼 구한다면 분명히 정답은 도출해 낼 수 있을 것이다. 하지만 한 가지 문제점이 발생하게 된다.

바로, 배열의 크기이다. 주어지는 배열의 크기는 최대 500,000이다.

그럼 이런 상황을 가정해보자.

배열의 크기가 500,000이고, 이 배열에 들어있는 원소가 0 ~ 499,999 까지 하나씩 순차적으로 들어있다고 가정해보자.

그리고 이 상태에서 #3의 과정을 진행해보자.

먼저, 등장하는 값들을 새로운 저장공간에 저장해줄 것인데, 이 새로운 저장공간에는 0 ~ 499,999 까지의 숫자가

들어가게 될 것이다. 즉, 이 저장공간은 크기가 500,000인 저장공간이 될 것이다.

그리고 이 저장공간에서 값을 하나씩 꺼내오면서 꺼낸 값을 공통된 원소로 설정한 후, 배열을 탐색하면서 스타수열을

만들어 보면 된다.

그럼, 이 때의 시간복잡도를 한번 계산해보자. 위에 코드로 적어놓은 2중 for문으로 구현한다고 가정했을 때, 시간복잡도는

500,000 * 500,000 이 된다. 굉장히 어마어마한 연산양이 될 것이다. 당연하게도 제한된 시간내에 문제를 절대로 해결할 수가 없다. 사실, 배열의 크기만 보더라도 이 문제는 완전탐색으로 해결을 하기에는 굉장히 타이트하다고 느낄 수 있을 것이다.

따라서 이런식으로 문제를 해결하기 위해서는 몇 가지 탐색을 해보지 않아도 결과가 뻔한 그런 상황들은 탐색을 하지 않게 미리 걸러주는 방식을 추가해주어야 한다.

#5. 탐색을 해보지 않아도 되는 경우

다음과 같은 경우를 보자.

[ 1 , 8 , 1 , 4 , 1 , 5 , 3 , 6 , 3 , 7 ]

먼저 등장하는 숫자로는 [ 1 , 8 , 3 , 4 , 5 , 6 , 7 ] 이 있다.

그리고 '1'을 공통된 원소로 탐색했을 때 만들 수 있는 스타수열의 최대길이는 [ 1 , 8 , 1 , 4 , 1 , 5 ] 로 6이 될 것이다.

그리고 그 다음으로 '3'을 공통된 원소로 탐색을 해보자. 그런데.. 꼭 해봐야할지에 대해서 생각을 해보자.

지금 눈으로 딱 보더라도, '3'은 2번밖에 등장하질 않고, 이 '3'으로 스타수열을 만든다고 하더라도, 아마 가장 좋은 조건일 경우 길이가 4인 스타수열 밖에 만들지를 못할 것이다.

여기서 가장 좋은 조건이라는 것은 "등장하는 모든 값이 스타수열이 될 수 있는 경우" 를 의미한다.

1번 Case : [ 3 , 3 , 4 , 5 ]

2번 Case : [ 3 , 6 , 3 , 7 ]

위의 2가지 경우 모두 '3'이 2번씩 등장한다는 공통점이 있지만, 1번 Case는 '3'을 공통된 원소로 삼을 경우, [ 3 , 4]

2번 Case는 '3'을 공통된 원소로 삼을 경우, [ 3 , 6 , 3 , 7 ] 로 길이가 더 긴 스타수열을 만들 수 있게 된다.

위에서 말한 가장 좋은 조건이라는 것은 2번 Case와 같은 경우를 말한다.

다시 돌아와서 [ 1 , 8 , 1 , 4 , 1 , 5 , 3 , 6 , 3 , 7 ] 로 돌아와서 보면...

'1'은 3번이 등장하지만, '3'은 2번밖에 등장하질 않는다.

그리고 그 외에 숫자들은 모두 한번밖에 등장하질 않는다.

그리고 이 상태에서 우리는 '1'을 공통된 원소로 삼았을 때 길이가 '6'인 스타수열을 만들 수 있다는 것을 알고 있다.

그럼, '3'을 포함한 나머지 숫자들에 대한 탐색이 필요할까 ??

탐색을 하지 않아도 된다. 왜 ?! 나머지 숫자들이 가장 좋은 조건으로 존재한다고 하더라도, 결코 기존에 만들었던 '6'보다 더 긴 스타수열을 만들 수는 없기 때문이다. 왜 ?! 등장하는 숫자의 갯수만 보더라도 이를 알 수 있기 때문이다.

위와 같은 방법이라면, 어쩌면 탐색을 해보지 않아도 되는 경우를 걸러낼 수도 있을 것이다.

따라서, 위와 같은 방법을 사용하기 위해서는 "배열에 등장하는 숫자의 횟수" 를 알고 있어야 한다.

그렇다고, 등장하는 숫자의 횟수가 가장 많은 숫자가 무조건 가장 긴 스타수열이 되는 것은 아니다. 이 부분에 대한 문제점은 #2에서 이야기 했었다.

배열에 등장하는 숫자의 횟수를 알았다면, 기존의 숫자들 중 몇개의 숫자가 스타수열에 사용되었는지만 판단해 주면 된다.

[ 1 , 8 , 1 , 4 , 1 , 5 , 3 , 6 , 3 , 7 ]

이 배열에서 가장 처음에 '1'을 공통된 원소로 삼고 스타수열을 만들었을 때, 총 3개의 '1'이 스타수열에 사용되었다.

즉, 이 때 '3'이라는 값을 저장해 놓는 것이다.

그리고 그 이후에 등장하는 숫자들의 등장횟수와 이 값을 비교하는 것이다.

'3'을 보면 2번 등장하게 된다. 그런데, 이미 '1'은 스타수열에 3번이나 사용되었네 ? 그럼 이 '3'은 탐색을 해보지 않아도 아무리 좋은 조건, 기가막힌 위치에 있다고 하더라도 절대로 3번이나 사용된 '1'이 만든 스타수열보다 더 길어질 수는 없다는 것을 의미한다. 이 부분에 대한 코드는 다음과 같다.

vector<int> Cnt(a.size() + 1, 0);
for (int i = 0; i < a.size(); i++) Cnt[a[i]]++;
for (int i = 0; i < Cnt.size(); i++)
{
    if (Cnt[i] == 0) continue;
    if (Cnt[i] <= answer) continue;
    int Result = 0;
 
    for (int j = 0; j < a.size() - 1; j++)
    {
        if (a[j] != i && a[j + 1] != i) continue;
        if (a[j] == a[j + 1]) continue;
        
        Result++;
        j++;
    }
    answer = Max(answer, Result);
}
 

line1)의 Cnt변수는 각 숫자들이 등장하는 횟수를 저장해놓기 위해서 사용되는 벡터이다.

#3과 #4의 과정에서 "등장하는 숫자들을 새로운 다른공간에 저장" 한다는 표현을 주로 사용했었는데, 더 구체적으로 이야기해보자면, "등장하는 숫자들의 횟수를 새로운 다른공간에 저장" 해주어야 한다.

line2)는 등장하는 숫자들의 횟수를 Count해주는 과정이다.

Cnt[A] = B 는 "배열에서 숫자 A는 B번 등장합니다." 를 의미한다.

그리고 line3)과 line9)가 #3에서 이야기했던 2중 for문이다.

line11)은 배열을 탐색할 때의 조건1이다. 인접한 2개의 값 중, 어느 하나라도 공통된 원소를 가지고 있어야 한다는 조건을

체크해주는 부분이다.

line12)는 스타수열의 조건3을 위배하는지 체크하는 경우이다.

line14)에 있는 'Result'라는 변수는 "해당 숫자가 사용된 횟수" 를 저장하는 변수이다.

line17)에 있는 'answer'는 "현재까지, 스타수열을 만드는데 가장 많이 사용된 횟수"가 저장된다.

그리고 이를 반복하게 되는데, 핵심은 line5) 와 line6) 이 된다.

line5)는 해당 숫자가 없는 경우를 의미한다. 배열에 존재하지 않는 숫자를 공통된 원소로 스타수열을 만들 수는 없다.

line6)이 지금까지 #5에서 이야기했던 부분을 체크하기 위한 조건문이다.

answer라는 변수에는 "현재까지 스타수열을 만드는데 사용된 공통된 원소가, 가장 많이 사용된 횟수" 를 저장하고 있다.

[ 1 , 8 , 1 , 4 , 1 , 5 , 3 , 6 , 3 , 7 ] 에서 '1'을 탐색했다면 answer에는 '3'이 저장되어 있을 것이다.

[ 1 , 8 , 1 , 4 , 1 , 5 ] 로 스타수열을 만들었을 때, 공통된 원소인 '1'이 '3번' 사용되었기 때문이다.

그 이후, '3'을 탐색해본다고 가정해보자. 3은 2번 등장하므로 Cnt[3] = 2 로 저장되어 있을 것이다.

이 때, line6)에서 2 <= 3 이므로 탐색을 하지 않고 넘어가게 된다.

이 이유는 위에서도 말했듯이, 3이 아무리 좋은 위치에 있어봤자 절대로 기존에 공통된 원소로 3번이나 사용된 '1'보다 더 긴 스타수열을 만들 수 없음을 의미하기 때문이다.

최종적으로 정답은 answer의 값에 * 2를 해주면 된다. answer는 공통된 원소가 사용된 횟수를 의미하고, 우리가 구해야 하는 값은 스타수열의 길이이므로, 공통된 원소가 사용될 때마다, 인접한 값 하나씩을 더 가지고 있으므로 실질적인 길이는 answer * 2가 된다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int Max(int A, int B) { return A > B ? A : B; }
bool Cmp(int A, int B) { return A > B ? true : false; }
 
int solution(vector<int> a)
{
    int answer = -1;
    vector<int> Cnt(a.size() + 1, 0);
    for (int i = 0; i < a.size(); i++) Cnt[a[i]]++;
 
    for (int i = 0; i < Cnt.size(); i++)
    {
        if (Cnt[i] == 0) continue;
        if (Cnt[i] <= answer) continue;
        int Result = 0;
 
        for (int j = 0; j < a.size() - 1; j++)
        {
            if (a[j] != i && a[j + 1] != i) continue;
            if (a[j] == a[j + 1]) continue;
            
            Result++;
            j++;
        }
        answer = Max(answer, Result);
    }
    return answer * 2;
}