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

문제 주소 : programmers.co.kr/learn/courses/30/lessons/70130

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

문제 확인

 

특별한 알고리즘이 필요없는 구현 문제입니다.

나오는 값들을 그래프 형식으로 저장한 후 하나씩 탐색하면서 최대 스타수열의 길이를 찾습니다.

 

풀이

 

수열의 길이가 길어지면 스타 수열을 찾기 위해 배열을 탐색하는 시간이 길어지므로 중복된 숫자를 다시 탐색하는 것은 비효율적입니다. 이를 방지하면서 해당하는 인덱스만 탐색을 하기 위하여 그래프를 사용합니다.

문제에서 나올 수 있는 숫자의 범위가 배열의 길이 이하이므로 2차원 배열 형태를 사용하며, 나오는 인덱스만 저장을 하면 되기 때문에 vector을 사용하여 저장합니다.

ex) {0, 1, 0, 2, 5, 2, 0} -->

v[0] = {0, 2, 6}

v[1] = {1}

v[2] = {3, 5}

v[5] = {4}

 

스타수열의 조건을 생각 해 보면 중복되는 숫자를 하나 선택하면 그 숫자 왼쪽과 오른쪽 중 어느 한곳이라도 중복숫자와 다른 숫자를 둘 수 있다면 이는 스타 수열이 됩니다.

0 선택 --> _0_  _0_  _0_ --> 0,1 0,2 2,0

 

그래프에 저장 시 간선들은 자동으로 정렬되어 저장되며 이를 이용하여 스타수열을 탐색합니다. 스타 수열 탐색 시 이를 3 단계로 분리합니다. 다음 위치에서 왼쪽에 숫자를 둘 수 있는지 체크는 bool 변수를 통해 기록 해 둡니다.

1) 처음위치 i = 1

• 왼쪽에 숫자를 둘 수 있다면 count++, 왼쪽에 숫자를 두게 되므로 오른쪽에 공간이 남습니다.
  
• 왼쪽에 숫자를 둘 수 없다면 오른쪽에 숫자를 두어야 하므로 이를 체크 해 둡니다.

2) 중간위치 i = 1 ~ n - 2 : 3가지 경우로 나눌 수 있습니다

• 전의 위치와 0칸이 차이나는 경우 count를 늘리지 않고 오른쪽에 숫자를 두어야 하므로 이를 체크 해둡니다.
• 1칸이 차이나는 경우 체크해둔 변수와 관계없이 한칸을 사용할 수 있으므로 count를 늘리기만 합니다.
• 2칸 이상 차이나는 경우 자신 위치에서 숫자를 하나 둘 수 있으므로 count를 하나 늘리며, 체크해둔 변수를 통해 전 단계에서 오른쪽에 숫자를 뒀다면 하나 더 늘립니다.

3) 마지막 위치 i = n - 1 : 중간위치와 비슷하게 동작하며 오른쪽에 수를 둘 수 있다는 경우를 추가해서 고려 해 줍니다.

 

의미없는 탐색을 줄이기 위해 현재 구해둔 최대 스타 수열의 길이가 탐색하는 수의 그래프 간선의 개수보다 크다면 이 수는 넘어갑니다.

 

코드

#include <string>
#include <vector>
using namespace std;
 
int solution(vector<int> a) {
    int answer = 0;
    vector<vector<int>> graph(a.size());
    for (int i = 0; i < a.size(); i++)
        graph[a[i]].push_back(i);//그래프 생성
 
    for (auto &t : graph) {
        if (!t.size())continue;//간선이 없는 수
        if (t.size() < answer)continue;//간선의 개수가 최대 스타 수열의 길이보다 작은 경우
        if (t.size() == 1) {//최대 스타수열의 길이가 1인 경우 
            answer = (a.size() > 1 && !answer) ? 1 : answer;
            continue;
        }
 
        int cnt = 0;
        //처음위치
        bool left_possible;//전 단계에서 오른쪽에 수를 둠 = 다음 단계에서 고려해야함
        if (t[0])
            left_possible = true, cnt++;//왼쪽에 둘 수 있는 경우
        else
            left_possible = false;//오른쪽 체크
 
        //중간위치
        for (int i = 1; i < t.size() - 1; i++) {
            if (t[i] - t[i - 1] == 1) {//붙어있는 경우
                left_possible = false;
            }
            else if (t[i] - t[i - 1] == 2) {//1개의 공간이 있는 경우
                cnt++;
            }
            else {//2개 이상의 공간이 있는 경우
                cnt++;
                if (!left_possible)cnt++;//전 단계의 체크 해 둔것을 count로 변환
                left_possible = true;
            }
        }
 
        //마지막 위치
        if (t.back() - t[t.size() - 2] == 1) {//붙어있는 경우
            if (t.back() < a.size() - 1)cnt++;//오른쪽에 둘 수 있다면
        }    
        else if (t.back() - t[t.size() - 2] == 2) {//1개의 공간이 있는 경우
            if (left_possible)cnt++;//왼쪽에 공간이 있는 경우
            else {
                cnt++;
                if (t.back() < a.size() - 1)cnt++;//전 단계 갱신 후 오른쪽에 수를 둘 수 있다면 하나 더 추가
            }
        }
        else {
            if (left_possible)cnt++;
            else cnt += 2;//전 단계 갱신 포함
        }
        
        answer = cnt > answer ? cnt : answer;
    }
 
    return answer<<1;
}