[Java] 연습문제 - 줄 서는 방법 (Lv2)

https://school.programmers.co.kr/learn/courses/30/lessons/12936

프로그래머스

 

 

 

✔ 입출력 예시

 

 

1️⃣ 첫번째 시도

❓ 풀이과정

     👉 1️⃣ 숫자 배열 생성 및 초기화

           2️⃣ 숫자의 조합을 담을 List 생성 후 재귀를 이용한 조합의 경우들 List에 담기

           3️⃣ 사전순으로 정렬

           4️⃣ 문자열을 한글자씩 잘라서 int형 배열에 담기

 

❗ 결과

   👉 정확성과 효율성 테스트 모두 실패

 

✔ 소스코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Solution { // 줄 서는 방법

	public static void main(String[] args) {
		int n = 3;
		long k = 5;

		System.out.println(solution(n, k));
	}

	private static int[] solution(int n, long k) {
		// 1. 배열 입력
		int[] num = new int[n];
		for(int i=1; i <= n; i++) {
			num[i-1] = i;
		}
		
		// 숫자의 조합을 담을 List
		line = new ArrayList<>();
		Combination(num, "", new boolean[n], 0);
		Collections.sort(line); // 3. 사전순으로 정렬
		
		int[] answer = new int[n];
		// 4. 문자열을 한글자씩 잘라서 int형 배열에 담기
		for(int i=0; i<n; i++) {
			answer[i] = line.get((int)k-1).charAt(i)-'0';
		}
		
		return answer;
	}

	static List<String> line;
	// 2. 조합 함수
	private static void Combination(int[] num, String str, boolean[] v, int cnt) {
		if(cnt == num.length) {
			line.add(str);
			return;
		}
		
		for(int i=0; i<num.length; i++) {
			if(v[i]) continue;
			v[i] = true;
			Combination(num, str+String.valueOf(num[i]), v, cnt+1);
			v[i] = false;
		}
	}
}

 

 

2️⃣ 두번째 시도

❓ 풀이과정

     👉 1️⃣ n팩토리얼 구하기

                 👉 각 자리에 나오는 수마다 몇 개의 경우의 수가 나오는지 판단하기 위해

           2️⃣ 구해야하는 수인 n이 0보다 클때까지만 반복문 진행

           3️⃣ 앞에서부터 차례로 수 찾아 answer배열에 담고 사용된 수는 list에서 제거

 

❗ 결과

    👉 테스트 통과

 

✔ 소스코드

import java.util.ArrayList;
import java.util.List;

public class Solution { // 줄 서는 방법

	public static void main(String[] args) {
		int n = 3;
		long k = 5;

//		int n = 4;
//		long k = 6;
		
		System.out.println(solution(n, k));
	}

	private static int[] solution(int n, long k) {
		int[] answer = new int[n];
		List<Integer> list = new ArrayList<>();  // 숫자를 담을 list
		long factorial = 1;
		
		// 1. n팩토리얼 구하기
		for(int i = 1; i <= n; i++) {
			factorial *= i;
			list.add(i);
		}
		
		int idx = 0;
		k--;  // 앞으로 반복해야하는 수 ([1,2,3]의 예시에서 0번째로 나오는 수의 조합은 [1,2,3])
		
        // 2. 구해야하는 수인 n을 1씩 감소하면서 반복문 돌리기
		while(n > 0) {
			factorial /= n;  // 정해지지 않은 자리 중 가장 맨 앞을 제외한 factorial(경우의 수)
			int num = (int)(k/factorial);  // 경우의 수 몇번 반복하는지
			answer[idx] = list.get(num);  // 정해진 수 입력
			list.remove(num);  // 사용한 수 제거
			
			k %= factorial;  // 나머지 위치 판단
			idx++;  // 다음 인덱스로 넘어가기
			n--;  // 가장 맨 앞의 수 정해짐
		}

		return answer;
	}

}

 

너무 당연하게 재귀를 돌려 순열을 이용한 경우의 수를 찾았지만 시간초과로 걸려서 당황했던 문제...

혼자 풀고 풀다가 다른 분들의 블로그도 정말 많이 보고 지인들에게 물어보기도 많이 물어봤던 문제였는데, 사실 아직도 내가 잘 이해한건지 정확하지 않아 아직 연구가 많이 필요할 것 같다.

알고리즘을 푸는 방법들은 정말 다양하고 많은 방법들을 연구해야 하는 것 같다.