프로그래머스 (C/C++, Java) 70130 : 스타 수열

https://school.programmers.co.kr/learn/courses/30/lessons/70130

프로그래머스

---

풀이

모든 경우의 수를 확인했을 때 최악의 경우 50만 * 50만이라 이중 반복문을 사용하는 방법은 아닐 거라 생각해서 인덱스 쌍을 짝수, 홀수로 나누어 스타 수열이 될 수 있는 쌍의 개수를 구해 최대인 값을 반환했다. 하지만 이는 숫자 쌍이 아닌, 단순히 양 옆의 숫자가 다를 때 추가하는 로직으로, 해당 문제와는 맞지 않았다.

안 풀려 답을 봤고 각 숫자가 나온 횟수를 저장한 후, 최댓값이 현재 탐색값보다 작을 때만 주어진 배열 전체를 탐색하여 최대 스타 수열의 길이를 구했다. 시간초과가 발생하지 않는 이유에 대해 생각해보니 

if (cnt[i] <= maxCnt) continue;

 

이 부분에서 n번의 반복을 줄여주기에 가능한 것 같다.

---

C/C++ 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(std::vector<int> a) {
    int n = a.size();
    int cnt[500000] = {0, };

    for (int n : a)
        cnt[n]++;

    int maxCnt = 0;
    for (int i = 0; i < n; i++) {
        if (cnt[i] <= maxCnt) continue;

        int count = 0;
        for (int j = 0; j < n - 1; j++) {
            if ((a[j] == i || a[j + 1] == i) && a[j] != a[j + 1]) {
                count++;
                j++;
            }
        }
        maxCnt = max(maxCnt, count);
    }
    return maxCnt * 2;
}

 

Java 코드

class Solution {
    public int solution(int[] a) {
        int n = a.length;
        int[] cnt = new int[n];
        
        for (int i = 0; i < n; i++)
            cnt[a[i]]++;
        
        int maxCnt = 0;
        for (int i = 0; i < n; i++) {
            if (cnt[i] <= maxCnt) continue;
            
            int count = 0;
            for (int j = 0; j < n - 1; j++) {
                if ((a[j] == i || a[j + 1] == i) && a[j] != a[j + 1]) {
                    count++;
                    j++;
                }
            }
            maxCnt = Math.max(maxCnt, count);
        }
        return maxCnt * 2;
    }
}