[Java] 2021 위클리 챌린지 7주차 - 입실 퇴실

모기업 코딩테스트의 기출문제로 당시 너무 어려워서 이것을 빼고 제출했던 기억이 있다. 프로그래머스의 정답자 수가 다른 주차수에 비해서 적은 것을 보면 풀기 어려운 문제임을 직감할 수 있다.

나는 그림을 그려서 문제의 규칙을 찾아보고자 했다. 먼저 입실을 1, 4, 2, 3 순으로 하고, 퇴실을 2, 1, 4, 3으로 하는 경우를 살펴보자.

입실과 퇴실을 일렬로 쓰고, 같은 번호를 선으로 이었다. 선으로 둘러쌓아진 부분이 각 번호가 존재한 시간을 나타내게 된다. 1번과 다른 번호들의 관계를 보면서 어떤 경우일 때 확정적으로 만나게 되는지 알아보자.

- 1번과 2번의 관계

1번의 파란선이 2번의 노란선을 감싸고 있는 구조가 보이게 되는데, 이 경우에는 1번과 2번이 무조건 만났다는 것을 알 수 있다.

그래서 x와 y번을 이용해 수식으로 표현해보면,  x번의 입실순서 < y번의 입실순서 and  x번의 퇴실순서 > y번의 퇴실순서 의 경우 x와 y는 만난것이 된다.

- 1번과 3번의 관계

그림 상으로는 헷갈릴 수 있지만, 3번의 퇴실순서가 1번의 퇴실순서보다 뒤쪽에 있기 때문에, 3번의 입실순서가 1번의 퇴실순서보다 앞에 있는지는 모른다.

- 1번과 4번의 관계

1번과 3번의 관계와 비슷한 상황이지만 여기서는 1번이 확정적으로 만난 2번의 입실 순서보다 4번의 입실순서가 앞쪽에 위치하고 있으므로, 적어도 1번의 퇴실 전에 4번을 만났음을 알 수 있다. 1번과 4번의 관계에서 2번과 같은 관계 있는 사람이 있으면 만나게 되는 것이므로 이를 찾아서 추가해준다.

수식으로 표현해보면 x번의 입실순서 < y번의 입실순서 x번의 퇴실순서 < y번의 퇴실순서 의 경우 z != x and z!=y의 z에 대해서 z번의 입실순서 > x번의 입실순서 and z번의 퇴실순서 < x번의 입실순서 and y번의 입실순서 < z번의 입실순서 의 z가 존재하면 y를 만난것이 된다. 퇴실의 경우에도 적용을 할 수 있다. 

이렇게 풀게되면 O(n^3) 의 시간복잡도가 나오기 때문에 n이 1000인 상황에서 효율성부분이 아슬아슬하다고 생각되었지만, 정답처리가 되었다. 다른 사람들의 풀이를 보니 나보다 훨씬 간단하게 풀어서 제출한 사람들이 있어서 부끄러운 풀이이지만, 다른 사람들에게 도움이 될 것이라 생각해 올린다.

class Person {
    int enterOrder;
    int leaveOrder;
}

class Solution {
    public int[] solution(int[] enter, int[] leave) {
        int n = enter.length;
        int[] answer = new int[n];

        Person[] people = new Person[n];
        for (int i = 0; i < n; i++) {
            people[i] = new Person();
        }
        for (int i = 0; i < n; i++) {
            people[enter[i] - 1].enterOrder = i;
            people[leave[i] - 1].leaveOrder = i;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 자기 자신의 경우는 제외
                if (i == j)
                    continue;
                // j가 i에 안쪽으로 포함되는 경우
                if (people[j].enterOrder > people[i].enterOrder && people[j].leaveOrder < people[i].leaveOrder) {
                    answer[i]++;
                    // j가 i에 바깥쪽으로 포함되는 경우
                } else if (people[j].enterOrder < people[i].enterOrder && people[j].leaveOrder > people[i].leaveOrder) {
                    answer[i]++;
                    // j의 입실 시간이 i에 포함되는 경우
                } else if (people[j].enterOrder > people[i].enterOrder && people[j].leaveOrder > people[i].leaveOrder) {
                    for (int k = 0; k < n; k++) {
                        if (k != i && k != j) {
                            if (people[k].enterOrder > people[i].enterOrder
                                    && people[k].enterOrder > people[j].enterOrder
                                    && people[k].leaveOrder < people[i].leaveOrder) {
                                answer[i]++;
                                break;
                            }
                        }
                    }
                    // j의 퇴실 시간이 i에 포함되는 경우
                } else if (people[j].enterOrder < people[i].enterOrder && people[j].leaveOrder < people[i].leaveOrder) {
                    for (int k = 0; k < n; k++) {
                        if (k != i && k != j) {
                            if (people[k].enterOrder > people[i].enterOrder
                                    && people[k].leaveOrder < people[i].leaveOrder
                                    && people[k].leaveOrder < people[j].leaveOrder) {
                                answer[i]++;
                                break;
                            }
                        }
                    }
                }
            }
        }
        return answer;
    }
}