.leetcode(406. Queue Reconstruction by Height)

문제

https://leetcode.com/problems/queue-reconstruction-by-height/

문제 풀기 전

1. 가장 먼저 무얼 놓으면 변함이 가장 적을지를 고민했다. 숫자 크기가 큰 걸 고르면 아무래도 작은걸 먼저 선택했을때 보다 생각할 부분이 적어질 수 있다고 생각했다. 
2. 그런데 만약 같은 크기를 갖고 있으면 아무래도 앞에 있는 요소의 숫자가 적은것을 먼저 배치하는게 나중에 더 쉬울거라 생각해서 아래처럼 정렬을 해야겠다고 먼저 생각했다.
   // [7,0]
   // [7,0] [7,1]
   // [7,0] [6,1] [7,1]
   // [5,0] [7,0] [6,1] [7,1]
   // [5,0] [7,0] [5,2] [6,1] [7,1]
   // [5,0] [7,0] [5,2] [6,1] [4,4] [7,1]

직접 푼 풀이

소요시간: 55분(22:32 ~ 23:27)

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        //1. 우선 정렬
        for (int i=0; i<people.length; i++) {
            for (int j=i+1; j<people.length; j++) {
                if (people[i][0] < people[j][0]
                    || (people[i][0] == people[j][0] && people[i][1] > people[j][1])) {
                    int[] temp = people[i];
                    people[i] = people[j];
                    people[j] = temp;
                }
            }
        }

        //2. 순서에 맞게 정리
        LinkedList<int[]> stack = new LinkedList<>();
        LinkedList<int[]> tempStack = new LinkedList<>();      
        for (int i=0; i<people.length; i++) {
            if (stack.size() > people[i][1]) {
                while(true) {
                    if (stack.size() != 0 && stack.size()  >  people[i][1]) {  
                        tempStack.push(stack.pop());
                    } else {
                        stack.push(people[i]);
                        while(tempStack.size() != 0) {
                            stack.push(tempStack.pop());
                        }
                        break;
                    }
                }
            } else {
                stack.push(people[i]);
            }
        }

        //3. 변환
        int[][] ret = new int[people.length][2];
        for(int i=0; i<people.length; i++) {
            ret[i] = stack.pollLast();
        }

        return ret;
    }
}

느낀점

1. 확실히 medium문제부터는 좀 다르다. 일단 문제 이해하는데만 8분이 걸렸다. 영어에 익숙해져야한다.
2. 직접 풀었을때는 일단 정렬이 필요하다고 생각해서 정렬을 구현하고 그걸 정리하는 2스텝으로 문제를 풀었다. 정렬이 개념으로 아는데 구현하느라 시간이 좀 더 걸렸던거같다.
3. 솔루션도 똑같은데 자바 메소드를 적극활용해서 소스코드를 확연히 줄였다. 1. Arrays.sort, 2.LinkedList.add, 3.output.toArray(new int[n][2]) 이 세개의 코드가 적절히 녹아드니 아주 심플한 로직이 되었다.

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)

나중에다시한번