[Cos Pro 1급 java] [4차] 문제8) n번째 작은 수 구하기

안녕하세요

 

이번 포스팅은 Cos Pro 1급 java 4차 기출 문제 중 8번 문제인 n번째 작은 수 구하기 입니다.

 

개인적으로는 이번 문제가 가장 어려웠다고 생각합니다.

 

□ 문제설명

1 이상 9 이하 숫자가 적힌 카드를 이어 붙여 숫자를 만들었습니다. 이때, 숫자 카드를 조합해 만든 수 중에서 n이 몇 번째로 작은 수인지 구하려 합니다.

예를 들어, 숫자 카드 1, 2, 1, 3로 만들 수 있는 수를 작은 순으로 나열하면 [1123, 1132, 1213, 1231, 1312, ... , 3121, 3211]입니다. n이 1312라면, 숫자 카드를 조합해 만든 수 중 n은 n은 5번째로 작은 수입니다.

숫자 카드를 담은 배열 card, card의 길이 card_len, 수 n이 매개변수로 주어질 때 숫자 카드를 조합해 만든 수 중에서 n이 몇 번째로 작은 수인지 return 하도록 solution 함수를 완성해주세요.

---

□ 매개변수 설명

카드에 적힌 숫자를 담은 배열 card, card의 길이 card_len, 수 n이 solution 함수의 매개변수로 주어집니다.

• card_len은 항상 9 입니다.
• card의 원소는 1 이상 9 이하인 자연수입니다.
• n은 999,999,999 이하인 자연수입니다.
• n의 자릿수는 card_len과 같습니다.
• n의 각 자리의 숫자는 1 이상 9 이하입니다.

---

□ return 값 설명

숫자 카드를 조합해 만든 수 중에서 n이 몇 번째로 작은 수인지 return 해주세요.

• 만약, n을 만들 수 없다면 -1을 return 해주세요.

---

□ 예시

	card	n	return
예시 #1	[1, 2, 1, 3]	1312	5
예시 #2	[1, 1, 1, 2]	1122	-1

---

□ 예시설명

예시 #1
앞서 설명한 예와 같습니다.

 

예시 #2
숫자 카드를 조합하면 [1112, 1121, 1211, 2111]를 만들 수 있습니다. 따라서 1122는 만들 수 없습니다.

 

※ 문제 접근 방식

(1) 먼저 케이스를 봅니다.

 

카드가 항상 4개가 주어집니다.

카드의 종류가 많으면 4개, 적으면 1개인데요.

 

특히 카드의 종류가 2개 3개인 경우를 생각해봐야합니다.

 

카드의 종류가 3개인 경우는 하나는 무조건 두개이므로 4! 에서 0.5배를 해주어야 합니다.

식으로 표현하면 

 

이렇게 표현할 수 있겠네요.

ex) 카드가 int[] card = {1, 1, 2, 3}

==> 1123, 1132, 1213, 1231, 1312, 1321, 2113, 2131, 2311, 3112, 3121, 3211 ==> 이렇게 총 12가지 케이스가 나옵니다.

카드 종류가 4개인 경우는 카드를 조합해서 만들 수 있는 숫자는 4*3*2*1 이므로 24가 나오게 됩니다.

 

카드의 종류가 2가지인 경우는 여기서 또 두 경우로 나뉩니다.

--- 1) 카드의 갯수가 1개, 3개일 때

 

 

--- 2) 카드의 갯수가 2개, 2개일때

 

 

(2) 이번엔 코드를 집중해서 설명하겠습니다.

 

먼저 Map을 생성합니다. 키 : Integer, Value : Integer

 

for문을 돌면서 map에 key값으로 카드를 넣고 갯수를 Value로 넣어줍니다.

 

그 다음, 팩토리얼 값을 받아올 함수를 만듭니다.

 

public int factorial(int n) {
	if(n > 1) return n * factorial(n-1); 
	else return 1;
}

 

이제 위에서 정리한 식의 내용을 반영하여 카드조합 갯수를 계산합니다.

 

caseMap을 생성합니다.

 

whlie문을 돌립니다. 기준은 카드조합갯수만큼 돌립니다.

 

while(k < cnt) {
	String str = "";
	Integer[] temp = shuffle(card);

	for (int i = 0; i < temp.length; i++) str += String.valueOf(temp[i]);

	if(!caseMap.containsKey(str)) {
		caseMap.put(str, 1);
		k++;
	}
}

 

shuffle이라는 함수를 만듭니다.

 

public Integer[] shuffle(int[] arr) {
	List<Integer> list = new ArrayList<Integer>();

	for (int i = 0; i < arr.length; i++) list.add(arr[i]);
	Collections.shuffle(list);

	return list.toArray(new Integer[list.size()]);
}

 

shuffle 함수에 배열의 값을 받아 넣을 리스트를 생성합니다.

 

Collections.shuffle() 을 이용하여 리스트를 무작위로 섞습니다.

 

섞인 리스트를 toArray를 사용하여 반환합니다.

 

shuffle된 카드 배열을  while문 안에 있는 Integer 배열로 리턴합니다.

 

Integer배열의 카드들을 문자열로 이어붙입니다.

 

caseMap에 해당 카드조합이 존재하지 않으면 카드 조합을 넣고 순환수를 증가시킵니다

 

섞인 카드 조합을 받을 배열을 생성합니다.

 

순환이 종료되면 Iterator를 생성하여 caseMap의 Keyset을 iterator()로 받습니다.

 

iterator로 키를 하나씩 받아 Integer.parseInt를 사용하여 배열에 넣은 후 i를 증가시킵니다.

 

int[] arr = new int[caseMap.size()];
int i = 0;
Iterator<String> ir = caseMap.keySet().iterator();
while(ir.hasNext()) arr[i++] = Integer.parseInt(ir.next());

 

arr의 크기만큼 순환하는 for문을 생성합니다

 

i번째가 n과 같을 경우 answer에 i+1을 넣어주고 for문을 나갑니다

 

i번째가 arr의 크기만큼 크고 answer가 0이라면 -1을 넣어주고 리턴합니다.

 

package nthSmallNumber;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class NthSmallNumber {
	public static void main(String[] args) {
		Main sol = new Main();
		int card1[] = { 1, 2, 1, 3 };
		int n1 = 1312;
		int ret1 = sol.solution(card1, n1);

		// [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
		System.out.println("solution 메소드의 반환 값은 " + ret1 + " 입니다.");

		int card2[] = { 1, 1, 1, 2 };
		int n2 = 1122;
		int ret2 = sol.solution(card2, n2);

		// [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
		System.out.println("solution 메소드의 반환 값은 " + ret2 + " 입니다.");
	}
}

class Main {
	public int solution(int[] card, int n) {
		int answer = 0;
		Arrays.sort(card);
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		
		for (int i = 0; i < card.length; i++) {
			if(!map.containsKey(card[i])) map.put(card[i], 1);
			else map.replace(card[i], map.get(card[i]) + 1);
		}
		
		int cnt = factorial(card.length);
		
		switch (map.size()) {
			case 1:
				cnt /= cnt;
				break;
			case 2:
				if(map.containsValue(3)) cnt /= 6; 
				else if(map.containsValue(2)) cnt /= 4;
				break;
			case 3 :
				cnt /= 2;
				break;
			default:
				break;
		}
		
		Map<String, Integer> caseMap = new HashMap<String, Integer>();
		int k = 0;
		while(k < cnt) {
			String str = "";
			Integer[] temp = shuffle(card);
			
			for (int i = 0; i < temp.length; i++) str += String.valueOf(temp[i]);
			
			if(!caseMap.containsKey(str)) {
				caseMap.put(str, 1);
				k++;
			}
		}
		
		int[] arr = new int[caseMap.size()];
		int i = 0;
		Iterator<String> ir = caseMap.keySet().iterator();
		while(ir.hasNext()) arr[i++] = Integer.parseInt(ir.next());
		
		Arrays.sort(arr);
		
		for (i = 0; i < arr.length; i++) {
			if(arr[i] == n) {
				answer = i+1; break;
			}
			
			if(i == arr.length -1 && answer == 0) answer = -1;
		}
		
		return answer;
	}
	
	public int factorial(int n) {
		if(n > 1) return n * factorial(n-1); 
		else return 1;
	}
	
	public Integer[] shuffle(int[] arr) {
		List<Integer> list = new ArrayList<Integer>();
		
		for (int i = 0; i < arr.length; i++) list.add(arr[i]);
		Collections.shuffle(list);
		
		return list.toArray(new Integer[list.size()]);
	}
}