[220711][Tany][인프런](4-5) K번째 큰 수

[juni8453]

📌 문제

• 문제

⭐️ 아이디어

• 슬라이딩 윈도우를 통해 합을 저장하고, Set 을 통해 중복되는 수를 제거해 저장한다.
• K번째 큰 수이므로 역 정렬을 통해 K번째 값을 얻어내 출력하면 될 듯 ??
• K번째 수가 없는 경우는 배열의 길이보다 K 값이 더 큰 경우인 것 같아서 분기문으로 -1 이 바로 리턴되도록 했다.

🤔 고민한 내용

• 이상하다 ... Hash 부분인데 내 생각에는 Hash 를 사용하는 부분이 딱히 없을 것 같다. 왜냐하면 저번 문제들과 다르게 배열에 숫자형이 들어가는 간단한 슬라이딩 윈도우기 때문에 ?
• IDE 내에서 몇 번 도전해봤는데, 슬라이딩 윈도우로는 입력받은 배열 내 3가지의 모든 경우의 수의 합을 뽑아내지 못하는 것 같다. 나는 3번째로 큰 수가 100 몇으로 나오는데 예제 정답은 143 ..
• 브루트 포스를 사용해야 할까 ? 근데 이러면 2중 ~ 3중 for 문이 들어가는데 이 방법은 아닌 것 같다.

💪 새롭게 배운 내용

• 단순 슬라이딩 윈도우로는 모든 경우의 수를 구할 수 없다.
• 슬라이딩 윈도우를 사용할 때 조건으로, 배열 내 연속된 것들을 비교할 때? 사용할 수 있는 것 같고 이런 경우는 아닌 듯.

🆘 이해가 어려운 내용

❌ 해결하지 못한 이유

• 완전 탐색 말고 방법이 따로 떠오르지 않는다.
• 완전 탐색으로는 시간 초과 날 것 같고, 초과가 아니더라도 찝찝하기 때문에 ㅠ..

✅ 본인 풀이

🏋️‍♀️ 시도횟수 : n회 | ⏱ 걸린시간 : 100ms | 💾 메모리 : 100MB

package study.section4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Section0405 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer firstLine = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(firstLine.nextToken());
        int k = Integer.parseInt(firstLine.nextToken());

        StringTokenizer secondLine = new StringTokenizer(br.readLine());
        int[] arr = new int[n];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(secondLine.nextToken());
        }

        int answer = solution(n, k, arr);
        System.out.println(answer);
    }

    private static int solution(int n, int k, int[] arr) {
        Set<Integer> answerSet = new HashSet<>();
        int answer = 0;
        int sum = 0;

        // 크기가 k 인 창문 만들기
        for (int i = 0; i < k; i++) {
            sum += arr[i];
        }

        answerSet.add(sum);

        // 한 칸씩 밀고나가면서 answerList 에 추가해놓기.
        // 나중에 List 는 정렬해야 한다.
        for (int i = k; i < n; i++) {
            sum += (arr[i] - arr[i - k]);
            answerSet.add(sum);
        }

        // k 번째 숫자가 없는 경우는 -1 을 리턴하기 위해 분기문 추가
        if (answerSet.size() < k) {
            return -1;
        }

        // K 번째로 큰 수를 출력하기 위해 역 정렬
        List<Integer> list = new ArrayList<>(answerSet);
        list.sort(Collections.reverseOrder());

        list.stream().forEach(s -> System.out.println(s + " "));
        System.out.println();

        answer = list.get(k - 1);

        return answer;
    }
}

// K 번째 수 출력하기
// K 번째 수가 존재하지 않다면 -1 을 리턴하라.
// 슬라이딩 윈도우만으로는 모든 3가지 경우의 수가 나오지 않는 것 같다.

참고한 자료

• 링크