๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

[TreeSet] 5. K๋ฒˆ์งธ ํฐ ์ˆ˜

์‹œํ๋ฆฌํ‹ฐ์ง€ํ˜ธ 2024. 1. 6.
5. K๋ฒˆ์งธ ํฐ ์ˆ˜
 

์„ค๋ช…

ํ˜„์ˆ˜๋Š” 1๋ถ€ํ„ฐ 100์‚ฌ์ด์˜ ์ž์—ฐ์ˆ˜๊ฐ€ ์ ํžŒ N์žฅ์˜ ์นด๋“œ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฐ™์€ ์ˆซ์ž์˜ ์นด๋“œ๊ฐ€ ์—ฌ๋Ÿฌ์žฅ ์žˆ์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

ํ˜„์ˆ˜๋Š” ์ด ์ค‘ 3์žฅ์„ ๋ฝ‘์•„ ๊ฐ ์นด๋“œ์— ์ ํžŒ ์ˆ˜๋ฅผ ํ•ฉํ•œ ๊ฐ’์„ ๊ธฐ๋กํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. 3์žฅ์„ ๋ฝ‘์„ ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ๊ฒฝ์šฐ๋ฅผ ๊ธฐ๋กํ•ฉ๋‹ˆ๋‹ค.

๊ธฐ๋กํ•œ ๊ฐ’ ์ค‘ K๋ฒˆ์งธ๋กœ ํฐ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์„ธ์š”.

๋งŒ์•ฝ ํฐ ์ˆ˜๋ถ€ํ„ฐ ๋งŒ๋“ค์–ด์ง„ ์ˆ˜๊ฐ€ 25 25 23 23 22 20 19......์ด๊ณ  K๊ฐ’์ด 3์ด๋ผ๋ฉด K๋ฒˆ์งธ ํฐ ๊ฐ’์€ 22์ž…๋‹ˆ๋‹ค.

์ž…๋ ฅ

์ฒซ ์ค„์— ์ž์—ฐ์ˆ˜ N(3<=N<=100)๊ณผ K(1<=K<=50) ์ž…๋ ฅ๋˜๊ณ , ๊ทธ ๋‹ค์Œ ์ค„์— N๊ฐœ์˜ ์นด๋“œ๊ฐ’์ด ์ž…๋ ฅ๋œ๋‹ค.

์ถœ๋ ฅ

์ฒซ ์ค„์— K๋ฒˆ์งธ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค. K๋ฒˆ์งธ ์ˆ˜๊ฐ€ ์กด์žฌํ•˜์ง€ ์•Š์œผ๋ฉด -1๋ฅผ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค.

์˜ˆ์‹œ ์ž…๋ ฅ 1 

10 3
13 15 34 23 45 65 33 11 26 42

์˜ˆ์‹œ ์ถœ๋ ฅ 1

143

 

 

<<ํ’€์ด>>

 

์ผ๋‹จ ์ด ๋ฌธ์ œ๋Š” ์‚ผ์ค‘ for๋ฌธ ์‚ฌ์šฉํ•˜๋ฉด ๋ฐ”๋กœ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค. 

 

ํ•˜์ง€๋งŒ ์‚ผ์ค‘ for๋ฌธ ๋ง๊ณ ๋ฅผ ์ƒ๊ฐํ•˜๋‹ค๊ฐ€ ๋‹ค๋ฅธ ๊ฒฝ์šฐ๋ฅผ ์ƒ๊ฐ ํ•ด๋ดค๋Š”๋ฐ ใ…‹ใ…‹

 

๊ฐ•์‚ฌ๋‹˜๋„ ์‚ผ์ค‘ for๋ฌธ์„ ์‚ฌ์šฉํ•œ๋‹ค๊ณ  ํ•œ๋‹ค ใ…‹ใ…‹ ๊ทธ๋ž˜์„œ ๋‚˜๋Š” ์‚ผ์ค‘ for๋ฌธ์„ ํ™œ์šฉํ•˜๊ณ  ํ•ด์‰ฌ๋งต์„ ์‚ฌ์šฉํ•ด์„œ ๋„ฃ์€ ๋’ค์— 

 

๊ทธ ๊ฐ’์„ ๋‹ค์‹œ keySet ๋ฉ”์„œ๋“œ๋ฅผ ์‚ฌ์šฉํ•ด์„œ ํ’€๊ณ  ์ •๋ ฌ ๋˜๋Š” for๋ฌธ์„ ์‚ฌ์šฉํ•ด์„œ ํ’€ ์˜ˆ์ •์ด์—ˆ๋‹ค.

 

๋‹ค๋งŒ!

 

์ด๋ฒˆ์—๋Š” 

์ค‘๋ณต์ œ๊ฑฐ์™€ ์ •๋ ฌ๊นŒ์ง€ ํ•ด์ฃผ๋Š” TreeSet ์„ ํ™œ์šฉํ•ด์„œ ํ’€์—ˆ๋‹ค.

 

-๊ฐ•์‚ฌ๋‹˜ ํ’€์ด-

 

import java.util.Collections;
import java.util.Scanner;
import java.util.TreeSet;

class Main {

    private int solution(int[] arr, int n, int m) {
        int answer = -1;
        TreeSet<Integer> Tset = new TreeSet<>(Collections.reverseOrder());
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    Tset.add(arr[i] + arr[j] + arr[k]);
                }
            }
        }

        int cnt = 0;
        for (int x : Tset) {
            cnt++;
            if (cnt == m) return x;
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        System.out.println(T.solution(arr, n, m));
    }
}

 

์ด๋ ‡๊ฒŒ TreeSet์„ ํ™œ์šฉํ•˜๋ฉด  HashMap์„ ์‚ฌ์šฉํ•˜๋Š” ๊ฒƒ๋ณด๋‹ค ํ›จ์”ฌ ๋” ๊ฐ„ํŽธํ•˜๊ฒŒ ๊ตฌํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค.

 

<<์ถ”๊ฐ€ ํ’€์ด>>

 

TreeSet์˜ ๋ฉ”์„œ๋“œ

 

add() -> ๊ฐ’์„ ๋„ฃ๋Š”๋‹ค. 

 

remove() -> ๋“ค์–ด์žˆ๋Š” ํŠน์ • ๊ฐ’์„ ์ œ๊ฑฐํ•œ๋‹ค.

 

size() -> ์›์†Œ์˜ ๊ฐฏ์ˆ˜๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.

 

first() -> ์˜ค๋ฆ„์ฐจ์ˆœ์ผ ๋•Œ์—๋Š” ์ตœ์†Œ๊ฐ’์„ ๋ฐ˜ํ™˜ํ•˜๊ณ  ๋‚ด๋ฆผ์ฐจ์ˆœ์ผ ๋•Œ๋Š” ์ตœ๋Œ“๊ฐ’์„ ๋ฐ˜ํ™˜ํ•œ๋‹ค. ์ผ๋ฐ˜์ ์œผ๋กœ ์ œ์ผ ์ฒซ๋ฒˆ์งธ ์ธ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

 

last() -> fisrt์™€ ๋ฐ˜๋Œ€์ด๋‹ค.

 

isEmpty() -> ์•ˆ์— ๊ฐ’์ด ์—†์œผ๋ฉด false ์žˆ์œผ๋ฉด true๋ฅผ ๋ฐ˜ํ™˜ํ•œ๋‹ค.

 

TreeSet<Integer> Tset = new TreeSet<>(Collections.reverseOrder());

 

Collections.reverseOrder() -> ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค. 

 

์ด๊ฑฐ ์—†์ด ๊ทธ๋ƒฅ 

TreeSet<Integer> Tset = new TreeSet<>();

 

๋ฅผ ์‚ฌ์šฉํ•˜๋ฉด ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค.

 

์˜ค๋Š˜๋„ ์ œ๋Œ€๋กœ ๋ฐฐ์šฐ๊ณ  ๊ฐ„๋‹ค!!

๋Œ“๊ธ€