[Algorithm] 과일 게임

과일 게임

무더운 여름 김토스는 친구들과 계곡으로 여행을 가게 되었습니다. 계곡을 눈앞에 두고 게임을 놓칠 수 없었던 김토스는 게임을 제안하게 됩니다.

N개의 과일이 있을 때, 연속된 K개의 과일을 골라 K개 중 가장 무거운 과일의 무게를 점수로 해서 가장 높은 점수가 나온 사람이 계곡에 입수하는 게임입니다.

김토스는 게임을 하기 전 N개의 과일의 무게가 주어질 때, 나올 수 있는 모든 점수를 구하고 싶습니다.

입력 예시

`solution(fruitWeights, k)` 함수의 인자는 아래와 같이 전달됩니다.

• N개의 과일의 무게 `W[i]`를 담고 있는 배열 : `fruitWeights` (`1 <= N <= 500000`, `1 <= W[i] <= 2,147,483,647`)
• 상수 K : `k` (`1 <= K <= N`)

출력 예시

주어진 N개의 과일의 무게 목록(`fruitWeights`)과 `k` 값을 바탕으로 나올 수 있는 모든 점수를 중복되지 않게 내림차순으로 정렬해 반환합니다.

예시입력fruitWeights: [30 40 10 20 30] k: 3출력[40 30]설명

'연속된 K개의 과일'의 경우의 수는 `[30 40 10]`, `[10 20 30]`, `[40 10 20]`이 존재하며, 각각의 경우에 대해 40점, 30점, 40점이 나올 수 있습니다. 따라서 `solution(fruitWeights, k)`는 `[40, 30]`을 반환합니다.

참고사항

시간복잡도에 유의하여 함수를 구현해주세요.

풀이

우선 가장 먼저 N개의 과일을 입력 받습니다.
replaceAll이라는 함수를 처음 사용해보았는데, 이 replaceAll 함수에 대해서는 나중에 따로 정리하도록 할게요!
입력 받은 과일을 k개씩 묶은 후 각 묶음마다 가장 큰 값을 구한 후, ArrayList에 넣어주었습니다.
그 후에 중복된 값을 허용하지 않는 HashSet을 사용하여 중복된 값을 제거한 후에 출력해주었습니다.

문제 참고사항에도 시간 복잡도를 유의하여 구현해달라고 하였는데,,,
그건 더 고민해봐야 될 것 같습니다^^;;

public class FruitGame {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String fruitWeightStr[] = br.readLine().replaceAll("fruitWeights: \\[","").replaceAll("]","").split(" ");

        int k = Integer.parseInt(br.readLine().replaceAll("k: ",""));
        int fruitCount = fruitWeightStr.length;
        int fruitWeights[] = new int[fruitCount];
        for (int i=0;i<fruitCount;i++){
            fruitWeights[i] = Integer.parseInt(fruitWeightStr[i]);
        }

        int NumberOfCase = fruitCount-k+1;
        List<Integer> maxWeight = new ArrayList<>();
        int maxInCase = 0;

        for(int i=0;i<NumberOfCase;i++){
            for(int j=i;j<i+k;j++){
                if(maxInCase<fruitWeights[j])
                    maxInCase = fruitWeights[j];
            }
            maxWeight.add(maxInCase);
            maxInCase=0;
        }

        Collections.sort(maxWeight);
        HashSet<Integer> set = new HashSet<>(maxWeight);
        System.out.println(set);
    }
}