[순열/해시맵] 백준 5568번 카드놓기 - JAVA

 

---

1. 출처

---

 

5568번: 카드 놓기

 

 

 

 

---

2. 설계

---

 

먼저 나는 카드의 조합을 생각했다.

만약 카드가 1,2,3,4가 있다고 할 때, 1과 2를 선택해서 12를 만드는 것과 2와 1을 선택해서 21을 만드는 것을 구분해야 한다고 생각했다.

그래서 순열을 써야한다고 생각했다. (만약 12, 21이 같다고 생각했다면 조합을 써야했다.)

 

 

1) 순열 설계

package BJ5568;

import java.util.Scanner;

public class 카드놓기 {
	
	static int n;
	static int k;
	static int[] nums;
	
	static boolean[] sel; //이미 선택된 숫자를 체크 
	static int[] sel_nums;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		k = sc.nextInt();
		
		nums = new int[n];
		sel = new boolean[n];
		sel_nums = new int[k];
		
		
		for(int i=0;i<n;i++) {
			nums[i]=sc.nextInt();
		}
		
		permutation(0);

	}
	
	//순서가 중요 => 순열
	public static void permutation(int depth) {
		
		if(depth==k) {
			for(int i=0;i<k;i++) {
				System.out.printf(sel_nums[i]+" ");
			}
			System.out.println();
			return;
		}
		
		else if(depth==n) {
			return;
		}
		
		
		for(int i=0;i<n;i++) {
			//나랑 같은 수는 또 뽑을 수 없음
			if(sel[i]) continue;
			
			sel_nums[depth] = nums[i];
			sel[i]=true;
			
			permutation(depth+1);
			
			sel[i]=false;
			
		}
	}

}

 

카드를 선택했는지 선택안했는지를 판단해 똑같은 카드를 2번 뽑을 수 없게 했다.

그리고, DFS를 다녀온 다음에 내가 뽑았던 카드를 false 해줘야 그 이전 depth에서 해당 카드를 뽑을 수 있게 된다.

만약 depth0에서 1을 뽑고, depth1에서 2를 뽑았다면, depth1에서 2를 놓아줘야 depth0에서 2를 뽑을 수 있는 기회를 주는 것이다.

 

(결과)

 

여기까지는 숫자들을 뽑은 것에 불과하지만, 이젠 나온 조합들을 새로운 숫자형태로 바꿔줘야 한다.

 

2) 숫자로 변경

//순서가 중요 => 순열
	public static void permutation(int depth) {
		
		int result = 0;
		if(depth==k) {
			for(int i=0;i<k;i++) {
				//10의 자리면 10을 더 곱해주는 과정이 필요 
				if(sel_nums[i]>=10) result = result*100 + sel_nums[i];
				else result = result*10 + sel_nums[i];
			}
			System.out.println(result);
			return;
		}
		
		else if(depth==n) {
			return;
		}
		
		
		for(int i=0;i<n;i++) {
			//나랑 같은 수는 또 뽑을 수 없음
			if(sel[i]) continue;
			
			sel_nums[depth] = nums[i];
			sel[i]=true;
			
			permutation(depth+1);
			
			sel[i]=false;
			
		}
	}

수는 99까지 나오기 때문에 2자리 수인 경우는 100을 곱해주고, 아닌 경우는 10을 곱해준다.

 

(결과)

 

그리고 나올 수 있는 경우의 수를 카운트하는 것이기 때문에 같은 수는 카운트하지 않게 해야한다. (12, 12는 1개로 친다)

이 과정을 조금 빠르게 진행할 수 있도록 HashMap을 쓸 것이다.

 

 

 

3) 나올 수 있는 숫자 카운트

package BJ5568;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class 카드놓기 {
	
	static int n;
	static int k;
	static int[] nums;
	
	static boolean[] sel; //이미 선택된 숫자를 체크 
	static int[] sel_nums;
	
	static Map<Integer, Integer> nums_map = new HashMap<>();
	static int count; //몇 가지 숫자가 나오냐?

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		k = sc.nextInt();
		
		nums = new int[n];
		sel = new boolean[n];
		sel_nums = new int[k];
		
		
		for(int i=0;i<n;i++) {
			nums[i]=sc.nextInt();
		}
		
		permutation(0);
		
		System.out.println(count);

	}
	
	//순서가 중요 => 순열
	public static void permutation(int depth) {
		
		int result = 0;
		if(depth==k) {
			for(int i=0;i<k;i++) {
				//10의 자리면 10을 더 곱해주는 과정이 필요 
				if(sel_nums[i]>=10) result = result*100 + sel_nums[i];
				else result = result*10 + sel_nums[i];
			}
			
			if(!nums_map.containsKey(result)) {
				count++;
				nums_map.put(result, result);
			}
			
			return;
		}
		
		else if(depth==n) {
			return;
		}
		
		
		for(int i=0;i<n;i++) {
			//나랑 같은 수는 또 뽑을 수 없음
			if(sel[i]) continue;
			
			sel_nums[depth] = nums[i];
			sel[i]=true;
			
			permutation(depth+1);
			
			sel[i]=false;
			
		}
	}

}

 

nums_map을 이용해 이미 해당 수가 나왔는지 확인하고, 없으면 count+1을 해주고, 해쉬맵에 해당 수를 넣어주는 과정을 진행한다.

이것이 전체코드라고 봐도 무방하다.

 

 

(결과)

 

 

---

3. 전체코드

---

 

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
	
	static int n;
	static int k;
	static int[] nums;
	
	static boolean[] sel; //이미 선택된 숫자를 체크 
	static int[] sel_nums;
	
	static Map<Integer, Integer> nums_map = new HashMap<>();
	static int count; //몇 가지 숫자가 나오냐?

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		k = sc.nextInt();
		
		nums = new int[n];
		sel = new boolean[n];
		sel_nums = new int[k];
		
		
		for(int i=0;i<n;i++) {
			nums[i]=sc.nextInt();
		}
		
		permutation(0);
		
		System.out.println(count);

	}
	
	//순서가 중요 => 순열
	public static void permutation(int depth) {
		
		int result = 0;
		if(depth==k) {
			for(int i=0;i<k;i++) {
				//10의 자리면 10을 더 곱해주는 과정이 필요 
				if(sel_nums[i]>=10) result = result*100 + sel_nums[i];
				else result = result*10 + sel_nums[i];
			}
			
			if(!nums_map.containsKey(result)) {
				count++;
				nums_map.put(result, result);
			}
			
			return;
		}
		
		else if(depth==n) {
			return;
		}
		
		
		for(int i=0;i<n;i++) {
			//나랑 같은 수는 또 뽑을 수 없음
			if(sel[i]) continue;
			
			sel_nums[depth] = nums[i];
			sel[i]=true;
			
			permutation(depth+1);
			
			sel[i]=false;
			
		}
	}

}

 

---

오랜만에 순열 문제 풀었다!