5568번 카드놓기

링크 : https://www.acmicpc.net/problem/5568

5568번: 카드 놓기

 

---

 

문제

상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?

예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다.

n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

- 입력 : 첫째 줄에 n이, 둘째 줄에 k가 주어진다. 셋째 줄부터 n개 줄에는 카드에 적혀있는 수가 주어진다.

- 출력 : 첫째 줄에 상근이가 만들 수 있는 정수의 개수를 출력한다.

예제 입력 1 

4
2
1
2
12
1

예제 출력 1 

7

 

---

 

풀이 방법

N개의 숫자를 입력받은 뒤, 조합을 이용하여 중복되지 않고 순서가 상관 없는 K개의 원소를 가지는 모든 경우를 구해줍니다. 그 뒤, 순열을 이용하여 뽑은 원소들이 중복되지 않게 순서를 변경해줍니다. 그리고 해당 원소가 이미 만든 목록 안에 없다면 추가해 줍니다.

 

ex ) N = 4       K = 2

      주어진 수 목록  = 1, 2, 12, 1

 

step1. 조합을 이용하여 4개의 숫자 중 2개의 숫자를 뽑는 모든 경우를 구합니다.

   => combination을 이용하여 구한 숫자 목록 : [1, 2], [1, 12], [1, 1], [2, 12], [2, 1], [12, 1] 

 

step2. 2개의 숫자를 순열을 이용하여 다른 순서로 나열합니다.

   => [1, 2] -> [1, 2] [2, 1] 
        [1, 12] -> [1, 12] [12, 1] 
        [1, 1] -> [1, 1] [1, 1] 
        [2, 12] -> [2, 12] [12, 2] 
        [2, 1] -> [2, 1] [1, 2] 
        [12, 1] -> [12, 1] [1, 12] 

 

step3. 다른 순서로 나열한 숫자들을 문자열을 이용해 합치고, 결과 배열에 없다면 추가해줍니다.

   => [12, 21, 112, 121, 11, 212, 122]    size : 7

 

 

 

구현 코드

import java.io.*;
import java.util.*;
public class Main {
	static int N,K;
	static String[] numbers;
	static String[] picked;
	static List<String> result;
	static boolean[] isSelected;
	static String[] mixed;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		K = Integer.parseInt(br.readLine());
		
		numbers = new String[N];
		for(int i =0;i<N;i++) {
			numbers[i] = br.readLine();
		}
		
		picked = new String[K];
		result = new ArrayList<String>();
		isSelected = new boolean[K];
		mixed = new String[K];
		combination(0,0);

		bw.write(result.size()+"");
		bw.flush();
		br.close();
		bw.close();
	}
	public static void combination(int cnt, int start) {
		if(cnt==K) {
			permutation(0);
			return;
		}
		for(int i=start; i<N;i++) {
			picked[cnt] = numbers[i];
			combination(cnt+1,i+1);
		}
	}
	public static void permutation(int cnt) {
		if(cnt == K) {
			String temp="";
			for(int i=0; i<K; i++) {
				temp+=mixed[i];
			}
			if(!result.contains(temp)) result.add(temp);
			return;
		}
		for(int i =0;i<K;i++) {
			if(isSelected[i]) continue;
			mixed[cnt] = picked[i];
			isSelected[i] = true;
			permutation(cnt+1);
			isSelected[i] = false;
		}
	}
}

 

---

 

다른 사람 코드 참조

 

오로지 순열을 이용하여 수들을 뽑아가며 문자열을 만든뒤 원하는 개수만큼 뽑았다면 hashSet에 저장

https://velog.io/@phjppo0918/%EB%B0%B1%EC%A4%80-5568-%EC%B9%B4%EB%93%9C-%EB%86%93%EA%B8%B0-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-JAVA

백준 5568 카드 놓기 문제풀이 (JAVA)

https://coder-in-war.tistory.com/entry/BOJ-JAVA5568-%EC%B9%B4%EB%93%9C-%EB%86%93%EA%B8%B0

[ BOJ ][JAVA][5568] 카드 놓기