4-5 K번째 큰 수

링크 : https://cote.inflearn.com/contest/10/problem/04-05

 

** 변경 전 틀린 코드

import java.util.*;
import java.util.stream.Stream;
import java.io.*;
 
class Solution{
    static int n,m,k;
    static StringTokenizer st;
    static StringBuilder sb;
    static int[] arr;
    static ArrayList<Integer> list;
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        list = new ArrayList<>();
        ArrayList<Integer>test = new ArrayList<>();
        dfs(0,0,test);
        Collections.sort(list, Collections.reverseOrder());
        if(list.size()<m) {
            System.out.println(-1);
        }else {
            System.out.println(list.get(m-1));
        }
        br.close();
        bw.close();
    }
    static void dfs(int cnt,int index, ArrayList<Integer> test) {
        if(index>=n) {
            if(cnt==3) {
                int sum=0;
                for(int i=0; i<3; i++) {
                    sum+=test.get(i);
                }
                list.add(sum);
            }
            return;
        }
        if(cnt==3) {
            int sum=0;
            for(int i=0; i<3; i++) {
                sum+=test.get(i);
            }
            list.add(sum);
            return;
        }
        test.add(arr[index]);
        dfs(cnt+1, index+1, test);
        test.remove(test.size()-1);
        dfs(cnt, index+1, test);
    }
}
 

- 완전탐색을 진행하여 list에 값을 저장하였으나, 중복된 값에 대한 생각을 하지 않음

- 당연하게 틀린 코드일 수 밖에 없음. (list에 중복된 값이 있어도 이를 토대로 순번을 매겼기 때문)

 

 

** 변경 코드(1차, ArrayList와 Set 사용)

import java.util.*;
import java.util.stream.Stream;
import java.io.*;
 
class Solution{
    static int n,m,k;
    static StringTokenizer st;
    static StringBuilder sb;
    static int[] arr;
    static ArrayList<Integer> list;
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        list = new ArrayList<>();
        ArrayList<Integer>test = new ArrayList<>();
        dfs(0,0,test);
        Set<Integer>set = new HashSet<>();
        for(int i : list) {
            set.add(i);
        }
        list.clear();
        for(int i : set) {
            list.add(i);
        }
        Collections.sort(list,Collections.reverseOrder());
        if(list.size()<m)System.out.println("-1");
        else System.out.println(list.get(m-1));
        br.close();
        bw.close();
    }
    static void dfs(int cnt,int index, ArrayList<Integer> test) {
        if(index>=n) {
            if(cnt==3) {
                int sum=0;
                for(int i=0; i<3; i++) {
                    sum+=test.get(i);
                }
                list.add(sum);
            }
            return;
        }
        if(cnt==3) {
            int sum=0;
            for(int i=0; i<3; i++) {
                sum+=test.get(i);
            }
            list.add(sum);
            return;
        }
        test.add(arr[index]);
        dfs(cnt+1, index+1, test);
        test.remove(test.size()-1);
        dfs(cnt, index+1, test);
    }
}
 

- 마찬가지로 완전탐색을 통해 list에 값을 저장하고, 이를 Set에 다시 저장함.

- Set으로의 변환을 통해 중복된 값을 제거할 수 있었고, 다시 List로 변환하여 값을 찾아낼 수 있었음.

- 그러나 불필요한 변환과정이 2번이나 이어짐

 

 

* 변경 최종 코드(TreeSet 사용)

import java.util.*;
import java.util.stream.Stream;
import java.io.*;
 
class Solution{
    static int n,m,k;
    static StringTokenizer st;
    static StringBuilder sb;
    static int[] arr;
    static ArrayList<Integer> list;
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        TreeSet<Integer> set = 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++) {
                    set.add(arr[i]+arr[j]+arr[k]);
                }
            }
        }
        int cnt=0;
        int answer=-1;
        for(int i : set) {
            cnt++;
            if(cnt==m) answer=i;
        }
        System.out.println(answer);
        br.close();
        bw.close();
    }
}
 

- TreeSet이라는 자료구조를 통해 불필요한 변환과정을 없애고, 코드도 간결해질 수 있었음.