빠에야는 개발중
줄 서는 방법 본문
N명의 사람이 있을 때, N명의 사람을 서로 다른 방법으로 줄을 세우는 방법은 N!개가 존재합니다.
이 때 각각의 사람들에게 번호를 매겨서 줄을 서는 방법을 표시합니다. 예를들어 [1,2,3,4]는 1번 사람이 제일 앞에, 2번 사람이 2두번째에... 서 있는 상태를 나타냅니다.
이러한 각각의 방법을 사전순으로 정렬했을때 K번째 방법으로 줄을 세우는 방법을 찾아 보려고 합니다.
예를 들어 3명의 사람이 있다면 총 6개의 방법은 다음과 같이 정렬할 수 있습니다.
- 4번째 방법은 [2,3,1]
- 5번째 방법은 [3,1,2]
- 6번째 방법은 [3,2,1]
이 때 K가 5이면 [3,1,2]가 그 방법입니다.
사람의 수 N과 순서 K를 입력받아 K번째 방법으로 줄을 세우는 setAlign 함수를 완성해 보세요. 예를 들어 setAlign(3,5)를 입력받는다면 [3,1,2]를 리턴해주면 됩니다.
딱 봐도 다음순열 문제라고 생각했고 자바는 다음순열 메소드를 가진 라이브러리가 없다. 그래서 열심히 직접 구현했는데 타임아웃이 나버렸다!!
길을 잃은 나는 결국 검색을 했고 엄청난 풀이를 발견하게 됐는데... 순열 전체를 구하는 것이 아니라 앞자리부터 순열을 여러개의 덩어리로 나누어서 순서를 매기고 필요없는 것들은 지워버리는 것이다. 이렇게 하면 매 자리수만 딱 구하면 되기 때문에 빨리 구할 수 있다. 전혀 생각지 못한 풀이법인데, 앞으로는 항상 문제를 풀 때 브루트포스를 최대한 피하는 방법을 처음부터 생각해내야겠다. 오랜 시간을 쓴 다음의 실패는(특히 타임아웃은) 정신적으로 너무 힘들다... ㅠ
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | import java.util.ArrayList; import java.util.Arrays; import java.util.List; class LineCombination { public int factorial(int n) { int result = 1; for(int i = 1; i<= n;i++) { result *= i; } return result; } public int[] setAlign(int n, long k) { int[] answer = new int[n]; List<Integer> list = new ArrayList<>(); for (int i = 0; i < n; i++) { list.add(i+1); } int num = n; long remain; int share; List<Integer> result = new ArrayList<>(); while(num > 0) { num--; remain = k % factorial(num); share = (int) (k/factorial(num)); if(remain == 0) { share--; result.add(list.get(share)); list.remove(share); break; } result.add(list.get(share)); list.remove(share); k = remain; } for(int i = list.size()-1; i>=0;i--) { result.add(list.remove(i)); } for(int i = 0; i<result.size();i++) { answer[i] = result.get(i); } return answer; } // 아래는 테스트로 출력해 보기 위한 코드입니다. public static void main(String[] args) { LineCombination lc = new LineCombination(); System.out.println(Arrays.toString(lc.setAlign(3, 5))); } } | cs |
Comments