tryhello 줄 서는 방법 feat. Algorithm Study

알고리즘 스터디를 진행하면서, 오늘 처럼 놀라운 경험을 한 적 처음인 것 같다.

줄 서는 방법 이라는 문제를 진행하는데, 나는 그냥 라이브러리를 이용해 풀었는데, 스터디원 2분이서 새로운 효율적인 생각? 알고리즘 설계를 하셨다.

문제는 다음과 같다.

N명의 사람이 있을 때, N명의 사람을 서로 다른 방법으로 줄을 세우는 방법은 N!개가 존재합니다.

이 때 각각의 사람들에게 번호를 매겨서 줄을 서는 방법을 표시합니다. 예를들어 [1,2,3,4]는 1번 사람이 제일 앞에, 2번 사람이 2두번째에... 서 있는 상태를 나타냅니다.

이러한 각각의 방법을 사전순으로 정렬했을때 K번째 방법으로 줄을 세우는 방법을 찾아 보려고 합니다.

예를 들어 3명의 사람이 있다면 총 6개의 방법은 다음과 같이 정렬할 수 있습니다.

• 1번째 방법은 [1,2,3]
• 2번째 방법은 [1,3,2]
• 3번째 방법은 [2,1,3]
• 4번째 방법은 [2,3,1]
• 5번째 방법은 [3,1,2]
• 6번째 방법은 [3,2,1]

이 때 K가 5이면 [3,1,2]가 그 방법입니다.

스터디 한 분의 생각은 이렇다. N = 3 , K = 5라면, 문제를 이렇게 볼 수 있다. 

1 x o 

1 x o

------- 

2 x o 

2 x o 

-------

3 x o 

3 x o 

무조건, 가장 앞 자리는 3! 가지수가 모두 나오는데 이 나오는 더미수는 2!로 끊을 수 있다. 

이렇게 끊는다면, 필요 없는 앞의 가지를 버리고 K 번째에 대해서 구할 수 있지 않을까?에 대한 이야기이다. 

그래서 결국 일반화를 만들었다. 

N = 5, K = 70 인경우 

70 / 4! 로 나누면 몫은 2 .. 나머지는 22가 된다. 다시 22 / 3!로 나누면 몫은 3 .. 나머지는 4가 되고, 

4 / 2!로 나누면 몫은 2 나머지는 0이 된다. 

고로, 몫은 arr = [1,2,3,4,5] 배열의 index 번호가 된다. 이 것을 이용해 수도 코드 형태로 만들었다. 

TODO 1. 1..n 의 arr 만든다.
TODO 2. division job
    num = n;
    while(num>0)
    num--
    2-1. remain = k % fac(num);
    2-2. share = k / fac(num);
    2-3. result.add(arr[share]);
    2-4. arr.remove(share) // arr = [1,2,4,5] - > result = [3, ]
    2-5. if remain == 0 {
             share--
            result.add(arr[share])
            arr.remove(share)
            break;
        }
    2-6. k = remain;
TODO 3. arr내에 있는 값을 역으로 Result에 넣어준다.
TODO 4. 펙토리얼 함수에 대한 정의
def fac(num):
    result = 1
    num to 1:
    result *= num
return result

위 코드는 내가 처음에 라이브러리로 풀었던 코드이다.

아래는 변형한 코드 ( 위 수도 코드 형태와 유사하다. )

물론, 아래 방법이 훨씬 효율적이다. 필요 없는 더미를 뭉텅이로 잘라내고 바로 K번째를 구해버리니까...

이런 생각은 어찌 하시는 건지들...다들 천재인줄 알았다...