[프로그래머스/Programmers] 줄 서는 방법 (Java - Level2)

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

프로그래머스

---

⭐️ 코드

public int[] solution(int n, long k) {
    long num = 1;
    ArrayList<Integer> arrayList = new ArrayList<>();
    for(int i  = 1; i<=n; i++) {
        arrayList.add(i); // 1,2,,...,n-1,n
        num *= i; // 총 경우의 수 -> n!
    }

    k--;

    int[] answer = new int[n];
    int answerArrIdx = 0;

    while(n>0) {
        num = num / n; // num = 6/3;
        answer[answerArrIdx] = arrayList.get((int)(k / num));
        answerArrIdx++;
        arrayList.remove((int)(k / num));
        k = k % num;
        n--;
    }

    return answer;
}

---

💡 문제 풀이

풀이 방법 까지는 풀었지만 코딩으로 옮기기가 좀 힘든 문제였다....

long num = 1;
ArrayList<Integer> arrayList = new ArrayList<>();
for(int i  = 1; i<=n; i++) {
    arrayList.add(i); // 1,2,,...,n-1,n
    num *= i; // 총 경우의 수 -> n!
}

 

 

먼저 팩토리얼 계산을 했을 때 전체 경우의 수를 담을 long num 변수를 선언하고 값을 포문을 통해 곱한다.

ArrayList에는 1부터 n까지의 수를 ArrayList의 index [0] 번째부터 순서대로 담아준다.

 

index[0] 번째부터 담는다는 걸 꼭 기억해 두자

 

문제에서 보여주는 예시는 n = 3 이기 때문에 규칙을 찾기가 좀 어렵기 때문에 n = 4라고 가정해서 문제를 풀어보자.

우리는 n = 4 일 때 4!(24) 개의 경우의 수 중에서 한 열이 만들 수 있는 수는 (n-1)! 개라는 것을 알 수 있다. 

따라서 n! / n을 하고 찾고자 하는 k = 20이기 때문에 k / (n-1)! 을 하게 될 것이다.

 

하지만 문제가 하나 있다.

20을 6으로 나누게 되면 몫은 3, 나머지는 2가 나오게 되는데, 몫인 3이 가리키는 것이 맨 앞에 와야 할 가장 큰 수가 된다. 

그 몫에 대한 값을 ArrayList에서 가져오면 ArrayList [3] = 4 가 출력되어 버린다. 우리가 찾는 수는 [ 4,1,3,2 ] 있어야 하는데 나머지가 2이기 때문에 2만큼 더 내려가면 [ 4,2,1,3 ]이 될 것이다.

 

k는 0부터 시작하는 것이 아닌 1부터 시작하기 때문에 k가 올바른 인덱스를 가질 수 있도록 k에서 1을 빼주고 진행한다.

 

int[] answer = new int[n];
int answerArrIdx = 0;

while(n>0) {
    num = num / n; // num = 6/3;
    answer[answerArrIdx] = arrayList.get((int)(k / num));
    answerArrIdx++;
    arrayList.remove((int)(k / num));
    k = k % num;
    n--;
}

나머지 연산들은 while문을 통해 n == 1이 될 때 끝날 수 있도록 진행하였다. 

그림을 그려보며 하나씩 진행해 보면 이해하기가 더 쉬우니까 그림을 그리면서 한 번 해보도록 하자!!

 

---

👀 후기

생각을 엄청 오래 했는데 뭔가 어렵지는 않지만 규칙 찾기가 힘들고 코드로 계산식을 옮기기가 어렵다...

어떻게 하면 빠르게 문제에 접근할 수 있을까.....

ArrayList는 시간초과가 안 나지만 LinkedList는 시간 초과가 났었다...ㅜ

ArrayList와 LinkedList 중 어떤 것을 어떤 상황에서 쓰는 게 더 좋을까?