Inor

[Programmers] Lv 5. 줄 서는 방법 본문

Algorithm/Programmers

[Programmers] Lv 5. 줄 서는 방법

Inor 2017. 11. 20. 17:25

 N명의 사람이 있을때, 사람들의 줄 서는 방법을 계산하는 알고리즘 문제입니다. 예를 들어서 3명의 사람이 있을때 줄 서는 방법은 [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]이 존재하고 줄서는 방법의 총 개수는 3! = 6가지 방법입니다. 문제에서는 2가지 입력(사람의 수, x번째 줄 서는 방법)이 주어집니다. 만약 사람의 수가 3명이고 4번째 줄 서는 방법을 출력할 경우에 [2,3,1]이 출력됩니다.


 4명의 사람이 줄서는 직접 방법을 아래와 같이 나열하며 문제에 접근했습니다. 그리고 가장 앞에 있는 숫자를 기준으로 4가지 종류의 배열이 생긴다는 것을 알았습니다. 그래서 가장 앞에 있는 숫자를 차례로 알아내는 방법으로 문제를 해결했습니다. 앞의 자리를 알아내기 위해서 x번째 줄 서는 방법을 (n-1)!으로 나눈 몫과 나머지를 활용했습니다. 만약 14번째 줄 서는 방법을 찾을 경우에 14/3!의 몫인 2를 이용해서 첫 번째 위치의 사람을 찾았습니다. 그리고 맨 앞의 사람을 제외한 배열을 다시 나열했고, 마찬가지로 맨 앞의 사람을 찾았습니다. 두 번째 위치의 사람을 찾기 위해서 나머지인 2를 이용했습니다. 2/2! 연산을 수행하면 몫 1과 나머지 0를 얻을 수 있습니다. 나머지가 0일 경우에는 (몫-1) 값으로 맨 앞의 수를 찾았습니다. 나머지가 0이면 해당 그룹의 맨 마지막 값이라는 것을 알았고, 남아있는 수들을 역순으로 배치해줬습니다.


첫 번째


[1,2,3,4] [2,1,3,4] [3,1,2,4] [4,1,2,3]

[1,2,4,3] [2,1,4,3] [3,1,4,2] [4,1,3,2]

[1,3,2,4] [2,3,1,4] [3,2,1,4] [4,2,1,3]

[1,3,4,2] [2,3,4,1] [3,2,4,1] [4,2,3,1]

[1,4,2,3] [2,4,1,3] [3,4,1,2] [4,3,1,2]

[1,4,3,2] [2,4,3,1] [3,4,2,1] [4,3,2,1]


두 번째


[1,2,4] [2,1,4] [4,1,2]

[1,4,2] [2,4,1] [4,2,1]




- 문제 : https://programmers.co.kr/learn/challenge_codes/49


- 소스 코드

import java.util.ArrayList; import java.util.Arrays; import java.util.List; class LineCombination { public int[] setAlign(int n, long k) { int[] answer = new int[n]; int index = 0; int tempResult; ArrayList<Integer> remainValues = new ArrayList<Integer>(); long combination = 1; int value; long remain = k; for (int i = 1; i <= n; i++) { remainValues.add(i); } for (int i = n - 1; i > 0; i--) { for (int j = 1; j <= i; j++) { combination *= j; } value = (int) (remain / combination); remain = remain % combination; if (remain == 0) { value--; tempResult = (int) remainValues.get(value); remainValues.remove(value); answer[index++] = tempResult; break; } tempResult = (int) remainValues.get(value); remainValues.remove(value); answer[index++] = tempResult; combination = 1; } for (int i = remainValues.size() - 1; i >= 0; i--) { answer[index++] = (int) remainValues.get(i); } return answer; } // 아래는 테스트로 출력해 보기 위한 코드입i니다. public static void main(String[] args) { LineCombination lc = new LineCombination(); System.out.println(Arrays.toString(lc.setAlign(4, 17))); } }



그리고 문제를 풀었던 흔적...




Comments