[백준 15663번 N과 M (9)]

728x90

오늘의 문제는 N과 M(9)이다.

 

 

#고민의 흐름

처음엔 무조건 완전탐색!

 

수가 중복되지 않도록 visited배열을 만들어 방문처리를 해줌과 동시에,

M만큼 수를 골랐을 때, 이미 고른 조합인지를 확인해줘야 했기 때문에.

다 골랐을 때 이 결과를 String으로 만들어 ArrayList에 contains 함수를 통해 이미 있는지를 확인하고

있다면 넣어주고 StringBuilder에 추가 / 없다면 return을 해주었다.

 

코드는 다음과 같다.

( 코드가 너무 커보인다면 "Ctrl + 스크롤 내리기" 하면 잘보여요 ! )

( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )

 

import java.util.*;
import java.io.*;

public class Main {
    static int N, M, arr[], visited[], ans[];
    static ArrayList<String> list = new ArrayList<>();
    static String temp = "";
    static StringBuilder sb = new StringBuilder();
    public static void main (String [] arg) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int [N];
        visited = new int [N];
        ans = new int [M];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        //여기까지가 입력!

        Arrays.sort(arr); 
        // 문제의 조건에 맞춰 사전순 출력을 위해 오름차순으로 정렬을 해준다.

        recur(0, 0);
        System.out.print(sb);
    }
    
    //cur은 현재 arr의 어느 수인지, idx는 ans배열의 현위치이다.
    static void recur(int cur, int idx){
        if(cur == M){ // 만약 다찼다면 싹모아 String으로 만들고 이미 있는지 확인.
            String temp = "";
            for(int i = 0; i<M; i++){
                temp += String.valueOf(ans[i]);
            }
            if(list.contains(temp)){ // 있다면 그냥 return;
                return;
            }else{ // 없다면 넣어주고 sb에도 추가해준다.
                list.add(temp);
                for(int i = 0; i<M; i++){
                    sb.append(ans[i]).append(" ");
                }
                sb.append("\n");
                return;
            }
        }
        
        //방문했으면 continue;
        //안했으면 ans에입력해주고 방문처리해주고 넘어가기 !
        //다녀오면 방문처리 풀어주기까지 !
        for(int i = 0; i<N; i++){
            if(visited[i] != 0) continue;
            visited[i] = 1;
            ans[idx] = arr[i];
            recur(cur + 1, idx + 1);
            visited[i] = 0;
        }
    }
}

 

하지만 생각과 달리 시간초과라는 결과가 나왔다 ...

 

다시 생각해보니 N과 M이 최대이고 모두 같은 수라면 중복되는 경우가 너~무 많아짐을 생각할 수 있었다..

 

중복을 어떻게 없애줄지 고민을 한참하다가 결국 답을 혼자서 찾지 못했다 ..

검색해서 깨달은 다음 풀이방식을 코드와 함께 보자!

 

 

import java.util.*;
import java.io.*;
public class Main {
    static int N, M, arr[], visited[], picked[];
    static StringBuilder sb = new StringBuilder();
    public static void main (String [] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int [N];
        visited = new int [N];
        picked = new int [M];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        //여기까진 같다.

        recur(0);
        System.out.print(sb);
    }

    private static void recur(int cur){
        if(cur >= M){
            for(int i = 0; i<M; i++){
                sb.append(picked[i]).append(" ");
            }
            sb.append("\n");
            return;
        }

        int before = 0; // 이 before 값이 중복을 제거해준다..!
        for(int i = 0; i<N; i++){
            if(visited[i] == 1) continue;
            
            // 직전의 수와 같은지를 확인해주고
            // 같다면 중복이므로 배제해준다.
            // 각 재귀마다 새로 before을 선언하고, 따로 이전의 값을 저장하기 때문에
            // 같은 값들은 허용해주고, 불필요한 중복만 걸러준다.
            if(arr[i] != before){ 
                before = arr[i];
                picked[cur] = arr[i];
                visited[i] = 1;
                recur(cur + 1);
                visited[i] = 0;
            }
        }
    }
}

 

결과는 성공 !

before 값 하나만 추가함으로써 큰 중복을 제거할 수 있다는 점을 새로 깨달았다 ..

다른 문제를 풀이할 때에는 스스로 깨우칠 수 있으면 좋겠다.

오늘도 하나 새로 배워가며 ,,

 

궁금한 점이 있거나 보충할 점이 있다면 언제든 댓글 부탁드립니다 ~

 

https://www.acmicpc.net/problem/15663