[백준] 15654 N과 M (5) - 백트래킹 JAVA

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

15654번: N과 M (5)

코드설명

백트래킹 문제입니다.

 

 

처음에 백트래킹을 활용하면서 서로 같은 수 일때는 어떻게 처리해야할까 싶어서 그냥 반복문으로 만들어진 수열을 확인하면서 이미 더해진 수를 또 더할려고할경우 continue하는 로직을 추가했습니다.

 

하지만, 다른 코드를 확인해본결과 visited로 손쉽게 처리하는 로직이 더 나아보여서 해당 로직으로 수정했습니다.

 

코드

visited 배열 활용 + StringBuilder

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static int N, M;
	public static int[] arr;
	public static int[] answerArr;
	public static boolean[] visited;
	public static StringBuilder sb = new StringBuilder();
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N= Integer.parseInt(st.nextToken());
    	M= Integer.parseInt(st.nextToken());
    	
    	st = new StringTokenizer(br.readLine());
    	arr = new int[N];
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	Arrays.sort(arr);
    	answerArr = new int[M];
    	visited = new boolean[N];
    	simulate(0);
    	System.out.println(sb.toString());
    }
    public static void simulate(int level) {
    	if(level == M) {
    		for(int a : answerArr) {
    			sb.append(a).append(" ");
    		}
    		sb.append('\n');
    		return ;
    	}
    	for(int i=0;i<N;i++) {
    		if(visited[i] == false) {
    			visited[i] = true;
        		answerArr[level] = arr[i];
        		simulate(level + 1);
        		visited[i] = false;
    		}
    		
    	}
    	
    }
    
    
}

 

백트래킹에서 visited 배열 대신 직접 배열을 돌면서 확인 ( 시간이 너무 많이걸립니다. )

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static int N, M;
	public static int[] arr;
	public static int[] answerArr;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N= Integer.parseInt(st.nextToken());
    	M= Integer.parseInt(st.nextToken());
    	
    	st = new StringTokenizer(br.readLine());
    	arr = new int[N];
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	Arrays.sort(arr);
    	answerArr = new int[M];
    	simulate(0);
    }
    public static void simulate(int level) {
    	if(level == M) {
    		for(int a : answerArr) {
    			System.out.print(a+" ");
    		}
    		System.out.println();
    		return ;
    	}
    	for(int i=0;i<N;i++) {
    		boolean flag = false;
    		for(int a : answerArr) {
    			if(arr[i] == a ) {
    				flag = true;
    			}
    		}
    		
    		if(flag == true) continue;
    		answerArr[level] = arr[i];
    		simulate(level + 1);
    		answerArr[level] = -1;
    		
    	}
    	
    }
    
    
}