Programmers - 줄 서는 방법 with JAVA

 

 

문제

1~n번 까지 번호를 갖는 사람이 있다. n은 20이하의 자연수이다. 사람을 사전순으로 나열할때, k번째 줄은 어떤 순서인가?

 

 

 

 

로직

사실 이 문제는 효율성 테스트에서 애를 많이 먹었다. 하지만 로직에 문제가 있던게 아닌 long이 아닌 int를 사용해서 오류가 낫던 것이다. 이런 실수를 줄이는 게 중요한 것 같다.

 

로직은 간단하다

예를 들어, 20명이 줄을 선다면, 19! 간격으로 앞자리가 바뀐다. 이 아이디어만 고려하면 된다.

 

 

항상 자료형을 신경쓰자 !!

 

 

 

코드

import java.util.*;
class Solution {
    public List<Integer> solution(int n, long k) {
        List<Integer> answer = new ArrayList<>();
        List<Integer> check = new ArrayList<>();
        long count = 1;
        for(int i=1; i<=n; i++){
            count *= i;
            check.add(i);
        }
        while(true){
            if(n == 0){
                break;
            }
            int index = 1;
            while(true){
                if(k <= count/n*index){
                    break;
                }
                index += 1;
            }
            answer.add(check.remove(index-1));
            k -= count/n*(index-1);
            count /= n;
            n -= 1;
        }
        return answer;
    }
}

 

import java.util.*;
class Solution {
    public List<Integer> solution(int n, long k) {
        List<Integer> answer = new ArrayList<>();
        List<Integer> numbers = new ArrayList<>();
        long sum = 1;
        for(int i=1; i<=n; i++){
            numbers.add(i);
            sum *= i;
        }
        while(true){
            long now = sum/n;
            int index = 0;
            for(int i=1; i<=n; i++){
                if(k <= now*i){
                    index = i-1;
                    break;
                }
            }
            answer.add(numbers.get(index));
            numbers.remove(index);
            k -= now*index;
            sum /= n;
            n -= 1;
            if(n == 0){
                break;
            }
        }
        return answer;
    }
}