[C++로 풀이] 스타 수열⭐⭐⭐

Date: 2021.02.24 Updated: 2021.02.24

카테고리: Programmers

📌 스타 수열

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이 ⭕

X는 부분수열 (순서는 유지한채 몇몇 원소들을 제거해서 만들 수 있는 부분)

✨X 부분 수열이 "스타 수열"이 되려면 만족 해야 하는 조건✨
조건 1 : X 는 길이가 2 인 집합 n 개로 이루어진다. (이때 X의 길이 = 2n. X는 2 이상의 짝수다.)
조건 2 : X 를 이루는 길이 2 짜리의 모든 집합들은 모두 공통된 원소를 가지고 있다.(교집합 개수 1개 이상)
조건 3 :  X 를 이루는 길이 2 짜리의 집합들 내의 두 원소는 서로 다른 값을 가진다.

문제에서 구하고자 하는 것은 "가장 긴 길이의 스타 수열"이다.

조건 1️⃣
- a[i]가 a[i - 1] 이전 원소와 같은 집합이 될 수 있는지를 1 차로 검사하고
- 될 수 없다면 a[i]가 a[i + 1] 다음 원소와 같은 집합이 될 수 있는지를 2 차로 검사해야 한다.
- 이미 다른 집합에 포함이 된 원소는 다른 집합에 포함될 수 없다.
  - [2,3,5] 에서 [2,3]을 이미 같은 집합으로 묶었다면 [3,5]는 같은 집합이 될 수 없다.
조건 2️⃣
- 스타 수열이려면 길이 2 를 이루는 모든 집합들이 공통된 원소를 가져야 하므로 a 배열에서 등장한 원소 종류들을 차례로 검사하며 해당 원소가 공통된 원소가 될 때 몇개의 2 길이 집합을 만들어낼 수 있는지를 따지면 된다! 마침 문제에서 구하려는 것이 “가장 긴 길이의 스타 수열”이기 때문에 해당 원소가 공통된 원소라고 지목했을 때의 스타 수열 길이를 재고 최대값을 업데이트 해나가야 한다.
  - 처음엔 a 배열에서 가장 많은 빈도 수로 등장한 원소가 가장 긴 길이의 스타 수열을 가질 확률이 높지 않을까 생각하여 빈도수를 기준으로 정렬을 했었다. 근데 이럴 필요 없다는걸 나중에 깨달아서 해당 정렬 부분은 지웠다. 왜냐하면 가장 많이 등장한 원소라고 해서 무조건 가장 긴 길이의 스타 수열이 되는 것은 아니기 때문이다. 빈도수와 스타 수열 길이는 상관이 없다. (어느 정도의 상관관계는 있을 수 있겠지만 늘 그렇진 않기 때문에 정렬에 소요되는 시간 복잡도를 감수할 필요가 없어보인다.) 원소가 등장한 빈도수만큼 모두 공통된 원소가 될 수 있는게 아니다! 조건에 해당하는 만큼만 공통된 원소가 될 수 잇음.
    - 예를 들어 a 가 [3, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3] 이런 배열이라면 가장 많이 등장한 원소는 10번 등장한 1이 되지만 막상 1이 공통된 원소라고 정해놓고 스타수열을 구하면 [0, 1], [1, 3] 즉 [0,1,1,3] 이렇게 4 길이의 스타 수열 정도 밖에 못 만든다. 조건 3️⃣ 때문에 [1, 1] 집합은 만들어질 수 없기 때문이다. 따라서 정렬은 무의미하다. a 에 등장한 모든 원소값들별로 공통된 원소라고 가정되었을 때의 스타수열 길이를 구하는 식으로 일일이 탐색해야 한다는 얘기다!
조건 3️⃣
- 이전 원소 혹은 다음 원소와 집합을 이룰 수 있는지를 검사할 때 같은 값의 원소인지도 검사를 해야 한다. 같은 값을 가지면 안된다.

#include <string>
#include <vector>
#include <unordered_map>
#include <set>
#include <algorithm>

using namespace std;

int solution(std::vector<int> a) {
    int max = 0;
    set<int> elements;
    unordered_map<int, vector<int>> index_storage;

    for (int i = 0; i < a.size(); ++i) {
        elements.insert(a[i]);
        index_storage[a[i]].push_back(i);
    }

    vector<bool> included(a.size(), false);
    for (auto& element : elements) {
        vector<int> indexArray(index_storage[element]);
        if (max > 2 * indexArray.size()) 
            continue;
        int count = 0;
        for (int j = 0; j < indexArray.size(); ++j) {
            bool before = false;
            if (j == 0)
                before = indexArray[j] - 1 >= 0;
            else
                before = (included[indexArray[j] - 1] == false) && (indexArray[j] - 1 != indexArray[j - 1]);

            bool after = false;
            if (j == indexArray.size() - 1)
                after = indexArray[j] + 1 < a.size();
            else if (indexArray[j] + 1 < a.size())
                after = (included[indexArray[j] + 1] == false) && (indexArray[j] + 1 != indexArray[j + 1]);

            if (before || after) {
                count += 2;
                if (before) {
                    included[indexArray[j]] = true;
                    included[indexArray[j] - 1] = true;
                    continue;
                }
                else if (after) {
                    included[indexArray[j]] = true;
                    included[indexArray[j] + 1] = true;
                }
            }
        }

        max = max < count ? count : max;

        fill(included.begin(), included.end(), false);
    }

    return max;
}

1️⃣ 원소값 종류와 그 위치 기록

    int max = 0;
    set<int> elements;
    unordered_map<int, vector<int>> index_storage;

max 👉 a 배열의 원소값 종류마다 스타 수열 길이를 잴 텐데 현재까지 가장 길었던 길이를 담고 계속 업데이트 한다.
elements 👉 a 배열의 원소 종류를 담는다. set 이기 때문에 중복은 걸러지고 딱 원소 종류만 담긴다.
index_storage 👉 원소값 종류마다 a 배열에서 등장했던 인덱스들을 vector Value 로 저장하여 담는 map

    for (int i = 0; i < a.size(); ++i) {
        elements.insert(a[i]);
        index_storage[a[i]].push_back(i);
    }

elements는 set이기 때문에 중복은 알아서 걸러준다. a의 원소 종류들만 딱 elements에 담기게 된다.
- 예를 들어 a가 [5,2,3,3,5,3] 라면 elements 에는 [2, 3, 5] 이렇게 담기게 될 것이다.
index_storage에 해당 원소의 a 에서의 등장 인덱스도 저장해준다.
- 예를 들어 a가 [5,2,3,3,5,3] 라면
  - index_storage[2] = {1}
  - index_storage[3] = {2,3,5}
  - index_storage[5] = {0,4}

2️⃣ 원소의 종류마다 교집합 원소로 설정해두고 스타 수열 길이 재기

    vector<bool> included(a.size(), false);

    for (auto& element : elements) {
        vector<int> indexArray(index_storage[element]);
        if (max > 2 * indexArray.size()) 
            continue;
        int count = 0;
        for (int j = 0; j < indexArray.size(); ++j) {
            bool before = false;
            if (j == 0)
                before = indexArray[j] - 1 >= 0;
            else
                before = (included[indexArray[j] - 1] == false) && (indexArray[j] - 1 != indexArray[j - 1]);

            bool after = false;
            if (j == indexArray.size() - 1)
                after = indexArray[j] + 1 < a.size();
            else if (indexArray[j] + 1 < a.size())
                after = (included[indexArray[j] + 1] == false) && (indexArray[j] + 1 != indexArray[j + 1]);

            if (before || after) {
                count += 2;
                if (before) {
                    included[indexArray[j]] = true;
                    included[indexArray[j] - 1] = true;
                    continue;
                }
                else if (after) {
                    included[indexArray[j]] = true;
                    included[indexArray[j] + 1] = true;
                }
            }
        }

        max = max < count ? count : max;

        fill(included.begin(), included.end(), false);
    }

included 👉 a 배열과 동일한 크기로, 이미 집합에 포함된 원소인지 아닌지를 체크해둘 것이다.
- 공통된 원소가 바뀔 때마다 초기화 된다. 이번 설정할 공통된 원소를 기준으로 방문 체크를 하기 때문에..
- 그래서 큰 for문 안에다가 선언해서 매 for문 마다 새롭게 정의해줘도 되지만 a 크기만한 동적 배열(vector)를 매번 생성하는게 좀 부담스럽지 않을까 싶어 아주 조금이라도 효율성을 높이고자 for문 바깥에 하나를 정의해놓고 다음 반복으로 넘어가기 전에 false로 모두 초기화 하고 계속 재활용 하는 식으로 써먹음
indexArray 👉 index_storage[element] 와 같다. 이번에 공통된 원소로 설정할 원소 종류인 element의 a 배열에서의 등장 인덱스 위치들을 담은 vector가 된다.
- index_storage[element] 를 간단하게 줄여 쓰고자 indexArray 로 치환했다.

예시는 아래로 들도록 하겠다.

a가 [3,0,0,2,7,7,7,7,7,0] 라고 가정 (size = 10)

- elements = {0, 2, 3, 7}

- index_storage[0] = {1,2,9} 👉 indexArray[0] = 1, indexArray[1] = 2, indexArray[2] = 9
- index_storage[2] = {3} 👉 indexArray[0] = 3
- index_storage[3] = {0} 👉 indexArray[0] = 0
- index_storage[7] = {4,5,6,7,8} 👉 indexArray[0] = 4, indexArray[1] = 5, indexArray[2] = 6, indexArray[3] = 7, indexArray[4] = 8

굳이 공통된 원소로 설정하고 스타 수열 길이를 재봐지 않아도 되는 원소도 있을 수 있다. 예를 들어 현재까지의 max가 10 이라면, 즉 현재까지 나온 가장 긴 스타 수열 길이가 10 으로 저장이 되어 있는 상태일 때, a 배열에서 3번 밖에 등장하지 않았던 원소는 그 3 개가 전부 공통된 원소로 포함된 3개의 집합을 만들어도 스타 수열 길이가 6 밖에 되지 않기 때문에 이 max가 갱신될 일이 없다. 따라서 이 원소를 공통된 원소로 삼는다면 최대 스타 수열 길이가 6 밖에 되지 않으므로 굳이 작은 for문 돌려 순회할 필요가 없는 것이다. 따라서 조금이나마 시간 복잡도를 줄이고자 해당 원소 종류가 a 배열에서 등장한 빈도수에서 2 를 곱한 것이 (indexArray는 이 원소의 등장 인덱스들을 모아둔 배열이니 사이즈가 곧 a배열에서 등장한 빈도수가 된다. 따라서 2 * indexArray.size()) max 를 넘지 못하면 아예 검사도 하지 않고 다음 원소 종류 검사하러 넘어가도록 했다.
```
      if (max > 2 * indexArray.size()) 
          continue;
```
해당 원소 종류 element 가 등장한 a 배열에서의 인덱스들을 담은 index_storage[element], 즉 indexArray 을 순회하며 element 가 공통 원소일 때의 스타 수열 길이를 재보자.
```
for (int j = 0; j < indexArray.size(); ++j)
```
- 1️⃣ a[indexArray[j]]가 “이전 원소”와 2 길이의 집합을 이룰 수 있는지를 검사한다.
  - j = 0 일 땐 : 인덱스에서 1 을 뺀게 0 보다 크면 이전 원소와 집합을 이룰 수 있댜고 판단한다.
    - 원소 0 을 공통된 원소로 삼았을 때 0의 첫번째 인덱스인 indexArray[0] = 4은 4 - 1 = 3 이 0 보다 크므로 4 이전 인덱스인 3 인덱스를 가진 원소와 집합을 이룰 수 있다. 일단 첫번째 인덱스이므로 이게 원소 0 의 첫 등장 위치라는 것이 보장되기 때문에 3 인덱스를 가진 어떤 원소는 0 이 아닌게 보장되어 조건 3️⃣을 위반하지 않음. 다만 0의 첫번째 인덱스가 진짜 0일땐, 즉 a 배열에서 가장 처음에 등장할땐 이전 원소가 없을테니 이전 원소와 집합을 이룰 수 없다.
  - j > 0 일 땐 : 인덱스에서 1 을 뺀 인덱스가 다른 집합에 포함 된 적이 없고 (!included[indexArray[j] - 1]) 인덱스에서 1 을 뺀 인덱스가 이전 인덱스가 아닐 때
    - 예를 들어 7을 공통된 원소를 삼고자 할 때 앞에 이미 [0,2] 이렇게 집합이 만들어져 있다면 [2, 7] 로는 집합을 만들 수 없다. 2 는 이미 다른 집합에 포함되어 있기 때문이다.
    - index_storage[7] = {4,5,6,7,8} 에서 세번째 등장하는 7에서 1을 뺀 인덱스는 6이 된다. 이는 즉 7의 두번째 등장 인덱스다. [7,7]이 되는 셈이다. 공통된 원소가 한 집합내에 2개가 들어가므로 조건 3️⃣위반이다. 일단 이전 인덱스 (1을 뺸)가 같은 index_storage[7] 내에 없으면 서로 다른 값이라는게 보장이 된다.
      bool before = false; // 이전 원소와 집합을 이룰 수 있다면 true 가 되도록 if (j == 0) before = indexArray[j] - 1 >= 0; else before = (included[indexArray[j] - 1] == false) && (indexArray[j] - 1 != indexArray[j - 1]);
- 2️⃣ a[indexArray[j]]가 “다음 원소”와 2 길이의 집합을 이룰 수 있는지를 검사한다.
  - 이전 원소 설명과 똑같다.
    bool after = false; // 다음 원소와 집합을 이룰 수 있다면 true 가 되도록 if (j == indexArray.size() - 1) after = indexArray[j] + 1 < a.size(); else if (indexArray[j] + 1 < a.size()) // included.size() 와 같음 after = (included[indexArray[j] + 1] == false) && (indexArray[j] + 1 != indexArray[j + 1]);
- 3️⃣ 이전 원소와 집합을 이룰 수 있다면, 혹은 다음 웡소와 집합을 이룰 수 있다면
  - 스타 수열을 이루는 집합이 되니 count를 2 누적합 한다.
  - 우선적으로 이전 원소와 집합을 이룬다. 이전 원소와 집합을 이룰 수 있다면 이전 원소와 집합을 이루고 그렇지 못할 때에만 다음 원소와 집합을 이루도록 하였다. 나와 내 이전 혹은 다음 원소가 집합에 포함되었다는 체크를 해줌.
    if (before || after) { count += 2; if (before) { included[indexArray[j]] = true; included[indexArray[j] - 1] = true; continue; } else if (after) { included[indexArray[j]] = true; included[indexArray[j] + 1] = true; } }
스타 수열 최대값 업데이트, 그리고 이제 다음 반복으로 넘어가면서 새로운 원소 종류를 공통된 원소로 삼고 다시 그를 바탕으로 새 집합을 만들어갈 예정이니 included 초기화
```
      max = max < count ? count : max;
      fill(included.begin(), included.end(), false);
```

아무래도 a 배열에 등장한 모든 원소의 “종류” 마다 스타 수열 길이를 쟀기 때문인지 시간 초과는 피했지만 상당한 시간이 소요되었다. ㅠ ㅠ

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️

[C++로 풀이] 스타 수열⭐⭐⭐

📌 스타 수열

🚀 문제

🚀 내 풀이 ⭕

1️⃣ 원소값 종류와 그 위치 기록

2️⃣ 원소의 종류마다 교집합 원소로 설정해두고 스타 수열 길이 재기

Programmers 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)