[프로그래머즈 Lv2, Java] 줄 서는 방법

n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.

제한사항

• n은 20이하의 자연수 입니다.
• k는 n! 이하의 자연수 입니다.

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

프로그래머스

 

---

처음 문제를 보고 든 생각은, "이거 무조건 규칙성이 있다"였다.

그래서 한 10분동안 수열을 보면서 팩토리얼... 나누기.. 막 이러면서 하다가 규칙을 찾아냈는데.

앞에서 부터 팩토리얼이랑 나누기 뭐 이런거 막 써가면서  푸는거였다.

점화식이라고 해야할지는 모르겠지만, 코드짜기전에 생각으로 짯던 느낌은 이런 느낌이다.

for(int c = 1 ; k > 0 ; c++) {

 fact = factorial(n-c);

 divide = k / fact;

 [c-1] = ceil(divide)번째로 작은 사람

 k -= floor(divide) * fact

}

 

실제로 이렇게 풀면 맞는다.

근데 문제는 Java에서 ceil, floor를 쓰기 위해 double형으로 코드를 짰더니 효율성에서 시간초과가 나기 시작했다.

그래서 아니 이걸 더 어떻게 줄이라는거야... 진짜 말도안된다.. 라고 생각하면서 이것저것 마구마구 바꿔봤는데 안깨지길래 결국 질문하기를 들어가서 앞사람들이 뭐라했는지를 봤다.

봤더니 double를 쓰지말고 정수형을 쓰라고 하길래 진짜 좀 억지다란 생각하면서 int형으로 대체했는데 그 코드는 다음과 같다.

 

변수명이 z인거는 이게 되나? 란 생각으로 대충 이름 짓고 해서 그런거고..

대충 위의 점?화식을 보면 ceil(divide)가 있는데, 나누기를 정수형으로 때려버리면 무조건 내림이 되버린다.

그래서 그냥 +1을 해줬더니 나머지가 0일때도 +1되버려서 에러가나길래

나머지가 0이면 그냥 쓰고, 나머지가 0이 아니면 1을 더해줬다.

 

로직짤때까지만 해도 재밌었는데... 정수형 억지가 문제를 망쳤어... 라고 생각합니다