[PS] 프로그래머스 스타 수열 java 풀이

코딩테스트 연습 - 스타 수열 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

초기 문제 접근

• 부분 수열이니까 백트래킹..?
• length가 6이면 2, 4, 6 으로 길이를 따져서 배열에 모든 조합의 수를 만들고..
• 만들어진 조합으로 스타 수열인지 판별하는 메서드를 구현하면..?

현재 작성된 코드에서는 백트래킹을 사용하여 모든 가능한 부분 수열을 생성하려고 시도합니다. 그러나 이 방법은 매우 비효율적입니다. 특히 배열의 길이가 최대 500,000인 경우, 모든 부분 수열을 생성하고 확인하는 것은 시간 복잡도가 매우 큽니다.

 

위와 같은 대답을 GPT4o 한테 들을 수 있다.

그러면 어떻게 해결할 수 있을까..

다시 문제 접근

1.  int[] count 배열을 만든다. 그리고 수열에서 각 숫자의 빈도를 저장한다.
2. 여기서 현재 빈도 수를 저장하는 이유는 저장되어 있는 최대 길이 값보다 빈도가 덜 나올 경우, 검사를 생략하여 최적화 하기 위함이다.
   예를 들어, 현재 저장된 최대 길이가 6인데, 검사하는 숫자가 나오는 빈도가 2이면 이 값으로 나올 수 있는 최대 길이는 4가 나올 수 밖에 없다.
3. a의 모든 수는 0 이상, a 길이 미만이라는 조건이 있으므로, 0부터 a의 길이까지 순회한다.
4. 즉 이는 등장할 수 있는 모든 수를 따져보는 과정이다.
5. 0부터 n - 1 까지 순회하는 for 문을 작성해서, 현재 검사하는 숫자를 기준으로 a 배열을 순회한다.
6. 현재 원소(a[i])와 그 다음 원소 (a[i+1])가 다르고, 둘 중 하나의 원소라도 현재 기준의 숫자와 같으면 스타 수열의 조건을 만족한다.
7. 따라서 길이를 1 증가시키고, i 또한 증가시킨다. 결과적으로 for 문 안에 i++을 포함하여 2를 더하게 된다. 이는 짝수마다 검사해야 하기 때문이다.
8. 순회가 끝나면 현재 최대 길이와 계산된 길이의 max 값을 저장한다.

코드

import java.util.*;

class Solution {
    public int solution(int[] a) {
        int answer = 0;
        int n = a.length;
        int[] count = new int[n];
        for (int num : a) {
            count[num] += 1;
        }
        
        for(int num = 0; num < n; num++) {
            if (count[num] <= answer) continue; // 이미 등장한 숫자보다 더 빈도가 적거나 같은 경우
            int length = 0;
            for (int i = 0; i < n - 1; i++) {
                if ((a[i] != a[i + 1]) && (a[i] == num || a[i + 1] == num)) {
                    length += 1;
                    i += 1;
                }
            }
            answer = Math.max(length, answer);
        }
        return answer * 2;
    }
}