Do it! 알고리즘 코딩 테스트 (80번 ~ 81번)

80번 조약돌 꺼내기

---

내가 떠올린 풀이 해설

단순하게 확률로 풀었습니다. 조약돌 개수를 배열에 담아서 한 색깔의 조약돌만 뽑을 확률을 색깔별로 모두 구하고 각각의 확률을 더해 정답으로 출력했다.

ex) 5개 조약돌이 있는 색만 뽑을 확률 : 5/18 * 4/17

---

정확한 풀이 1

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

public class Baek13251 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int M = Integer.parseInt(br.readLine());
		
		int[] cnt = new int[M];
		double sum = 0.0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < M; i++) {
			cnt[i] = Integer.parseInt(st.nextToken());
			sum += cnt[i];
		}
		int K = Integer.parseInt(br.readLine());
		
		double answer = 0.0;
		for(int i = 0; i < M; i++) {
			double max = 1.0;
			for(int j = 0; j < K; j++) {
				max *= (cnt[i] - j) / (double)(sum - j);
			}
			answer += max;
		}
		System.out.println(answer);
	}
}

---

81번 순열의 순서

---

내가 떠올린 풀이 해설

이 문제는 조합 문제와 다르게 순열의 개념을 알아야 풀 수 있다. 순열은 순서가 다르면 다른 경우의 수로 인정된다. N자리로 만들 수 있는 순열의 경우의 수를 구해야 한다는 것이 이 문제의 핵심이다. 먼저 각 자리에서 사용할 수 있는 경우의 수를 구한다. 각 자리에서 구한 경우의 수를 모두 곱하면 모든 경우의 수가 나온다. 4자리로 표현되는 모든 경우의 수는 4! = 24이다. N자리로 만들 수 있는 순열의 모든 경우의 수는 N!이다.

k번째 순열 출력하기

1. 주어진 값(k)과 현재 자리(n) - 1에서 만들 수 있는 경우의 수를 비교한다.
2. 1에서 k가 더 작아질 때까지 경우의 수를 배수(cnt)로 증가시킨다.(순열의 순서를 1씩 늘림)
3. k가 더 작아지면 순열에 값을 저장하고 k를 k - (경우의 수 * (cnt - 1))로 업데이트한다.
4. 순열이 완성될 때까지 1 ~ 3을 반복하고 완료된 순열을 출력한다.

입력된 순열 순서 구하기

1. N자리 순열의 숫자를 받아 몇 번째 순서의 숫자인지 확인한다.(현재 숫자 - 자기보다 앞 숫자 중 이미 사용한 숫자)
2. 해당 순서 * (현재 자리 - 1에서 만들 수 있는 순열의 개수)를 k에 더한다.
3. 모든 자릿수에 관해 1 ~ 3을 반복한 후 K값을 출력한다.

---

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1722 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		ArrayList<Integer> arr[] = new ArrayList[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int m = Integer.parseInt(st.nextToken());
		long f[] = new long[21];
		int[] s = new int[21];
		boolean visit[] = new boolean[21];
		f[0] = 1;
		for(int i = 1; i <= n; i++) {  // 팩토리얼 초기화 -> 각 자리수에서 만들 수 있는 경우의 수 
			f[i] = f[i - 1] * i;
		}
		
		if(m == 1) {
			long k = Long.parseLong(st.nextToken());
			for(int i = 1; i <= n; i++) {
				for(int j = 1, cnt = 1; j <= n; j++) {
					if(visit[j]) {
						continue;  // 이미 사용한 숫자는 사용할 수 없음 
					}
					if(k <= cnt * f[n - i]) { // 주어진 k에 따라 각 자리에 들어갈 수 있는 수 찾기 
						k -= ((cnt - 1) * f[n - i]);
						s[i] = j;
						visit[j] = true;
						break;
					}
					cnt++;
				}
			}
			for(int i = 1; i <= n; i++) {
				System.out.print(s[i] + " ");
			}
		}
		else {
			long k = 1;
			for(int i = 1; i <= n; i++) {
				s[i] = Integer.parseInt(st.nextToken());
				long cnt = 0;
				for(int j = 1; j < s[i]; j++) {
					if(visit[j] == false) {
						cnt++;   // 미사용 숫자 개수 만큼 카운트 
					}
				}
				k += cnt * f[n - i]; // 자릿수에 따라 순서 더하기 
				visit[s[i]] = true;
			}
			System.out.println(k);
		}
	}
}

---

오늘의 회고

오늘은 조합 중에 좀 어려운 문제 2문제를 풀었습니다. 두 번째 푼 문제는 아이디어를 떠올리는데 안 떠올라서 풀지 못했습니다. 알고리즘 문제를 잘 풀고 싶습니다. 아직은 많이 부족한 것 같습니다. 열심히 나아가겠습니다.