[Lv.3] 스타 수열 -자바

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public int solution(int[] a) {
        int answer = 0;
        Map<Integer,Integer> numberMap=new HashMap<>();
        for (int i : a) {
            if(numberMap.containsKey(i)){
                numberMap.put(i,numberMap.get(i)+1);
            }else{
                numberMap.put(i,1);
            }
        }
        List<Integer> maxKeyList=new ArrayList<>();
        int maxValue=0;
        for (Integer integer : numberMap.keySet()) {
            Integer value = numberMap.get(integer);
            if(value>maxValue){
                maxKeyList=new ArrayList<>();
                maxKeyList.add(integer);
                maxValue=value;
            }else if(value==maxValue)
                maxKeyList.add(integer);
        }

        for (Integer key : numberMap.keySet()) {
            int targetKey=key;
            if(numberMap.get(key)*2<=answer)
                continue;
            int nowAns=0;

            boolean isNumberLeft=false;
            boolean isTarget=false;
            for (int j = 0; j < a.length; j++) {
                if(a[j]==targetKey){
                    if(isTarget){
                        //이번에 target인데, 타겟 존재 플래그가 true면 직전 타겟이 부분수열을 이루지 못했다는 뜻
                        //즉, tt인 상황
                        continue;
                    }
                    isTarget=true;
                    if(isNumberLeft){
                        isTarget=false;
                        isNumberLeft=false;
                        nowAns+=2;
                    }
                }else{
                    if(isTarget){
                        //make Number
                        isTarget=false;
                        isNumberLeft=false;
                        nowAns+=2;
                    }else isNumberLeft=true;
                }
            }

            answer=Math.max(nowAns,answer);
        }


        return answer;
    }
}

 

딱히 어떤 알고리즘을 사용하는 문제는 아니였다.

문제를 보면, 어떤 수열에서 순서대로 숫자를 짝수개만큼 뽑아 부분 수열을 구성하는데,

이 부분 수열을 2개씩 짝지었을 때, 짝지어진 부분 수열(2개의 원소로 이루어진)끼리 교집합이 1개 이상이고, 각 부분 수열(2개의 원소로 이루어진)은 서로 다른 수로 이루어져 있어야 한다.

즉, 순서대로 수를 뽑고 앞에서부터 2개씩 짝지어서 짝지어진 애들 끼리 1개의 원소만 공통으로 가지는 수열을 구하는 문제이다 (교집합 원소가 2개라면 3번째 조건인 각 짝지는 다른 수로 이루어져야 한다는 조건을 위배하게 된다.)

 

구현의 경우 간단하게 생각하니 쉽게 풀렸다.

A. 주어진 수열을 대상으로 현재 값이 현재 target Key와 같은 경우

1. 직전 수가 targetKey인 경우

2. 아닌 경우

로 나뉜다.

1.의 경우 targetKey가 연속으로 나오면 수열을 구성할 수 없으므로 (3번 조건 위배) pass한다.

2.의 경우 targetKey가 구성될 수 있다는 flag를 켜고, 만약 이미 타겟 키가 아닌 다른 수가 앞에 있었다면 해당 수와 현재 타겟을 짝지을 수 있으므로 정답 수열에 추가하고, target flag와 number flag를 모두 끈다. ( XT의 형태이므로 , 즉 타겟이 3이라면 12123인 경우이기에 어떤 구성을 하더라고 3을 포함하는 부분 수열은 길이가 2가 최대임)

 

B. 현재 값이 targetKey와 다른 경우는

1. 앞전에 target이 존재하는 경우

2.아닌 경우

로 나뉜다.

 

1.의 경우, target이 앞에 존재하고 그 후에 타겟이 아닌 수가 처음 온 경우 이므로, 부분 수열에 추가할 수 있다.

(즉, TX의 형태이다.)

2.의 경우 target이 없기에 부분 수열을 구성할 수 없다.

대신, 타겟이 아닌 수가 왔기에 numbe Flag를 켜야한다. ( A의 case에서 부분 수열 가능 여부를 판단하기 위해)

 

뭐 이런식으로 4가지의 경우에 대해서만 구분해주면 로직은 맞게 된다.

 

하지만 , 주의할 점이 전체 key중에서 가장 많이 나온 키들이 항상 가장 큰 부분 수열을 구성하는 것은 아니라는 점이다.

 

예를 들어, 000000121232의 경우

가장 많이 나온 수는 0이지만, 0을 target으로 부분 수열을 구성하면 최대 2의 길이를 가지게 된다.

하지만, 2를 target으로 구성해보면 12 12 32 이렇게 총 6의 길이를 가지게 된다.

 

따라서, 가장 많이 나온 키가 아닌 전체 키를 대상으로 검사를 진행해야 한다.

하지만, 무작정 전체 키를 대상으로 반복을 하게 되면 12345678 ... 이런 수열이 오게되는 경우 시간이 상당히 오래걸리게 된다.

따라서, 현재 구한 최대 부분 수열의 길이보다 길 수 있는 경우에 대해서만 검사를 진행해야 한다.

즉, 현재 최대 부분 수열의 길이가 6이라면 4번 이상 반복된 key들에 대해서만 검사를 하면 된다.

 

*3번 이하로 구성된 키에 대해 검사를 해봤자 어차피 Tx Tx Tx의 형태가 최대이다. 즉, 어떤 수열을 줘도 최대 6의 길이를 가진다.

따라서, 최대 8이상의 부분 수열을 가질 수 있는 키에 대해서만 검사를 진행하는게 훨씬 효율적이다.