[programmers] > 연습문제 > 줄 서는 방법

문제 바로가기

JAVA

실패한 풀이 - 효율성 실패

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int idx = 0; //현재 idx
    public int[] answer;
    public int[] solution(int n, long k) {
       answer = new int[n];
        ArrayList<Integer> people= range(n);
        int k1 = (int) k-1;
        int fac = factorial(n-1);
        first(fac,k1,people);

        return answer;
    }

    // 사람들에게 번호를 매기는 함수
    public ArrayList<Integer> range(int n) {
       ArrayList<Integer> range = new ArrayList<Integer>(n);
       for(int i=0;i<n;i++) {
          range.add(i+1);
       }
       return range;
    }

    // 첫 번째 idx를 구하는 함수
    public void first(int fac, int k, ArrayList<Integer> people) {
       // 첫 번째 숫자가 바뀌는 주기
       int per = fac;
       // 첫번째 숫자의 idx
       int firstIdx = k / per;
       // 기준 순열로부터의 거리
       int distance = k % per;

        answer[idx] = people.get(firstIdx);
        idx++;

        // 이미 줄은 선 사람은 people list에서 제거한다.
       people.remove(firstIdx);

        if(distance == 0) {
          // 기준순열로부터의 거리가 0이면
          // 지금 현재 people 리스트의 순서가 해당 순서의 줄서는 방법이다.
            for(int j=0;j<people.size();j++){
                answer[idx+j] = people.get(j);
            }

           return;
       }
       int size = people.size();
       first(per/size,distance,people);
    }

    // factorial 함수
    public int factorial(int n) {
       if(n <= 1) {
          return n;
       }
       return factorial(n-1)*n;
    }
}

참고한 풀이

다른 분의 풀이를 참고했다. 너무 간단하게 풀어서 부러웠다. 참고한 블로그

import java.util.ArrayList;
import java.util.List;

class Solution {
	public int[] solution(int n, long k) {
		int[] answer = new int[n];
		List<Integer>list = new ArrayList<>();

		long f = 1;
		for(int i=1;i<=n;i++) {
			list.add(i);
			f*=i;
		}
		k--;
		int idx = 0;
		while(idx<n) {
			f/=n-idx; //첫번째 숫자가 바뀌는 주기
			answer[idx++] = list.remove((int)(k/f)); //현재 인덱스
			k%=f; //구해야 하는 인덱스 번호 변경
		}

		return answer;
	}
}