입실 퇴실

문제

https://programmers.co.kr/learn/courses/30/lessons/86048#

코드

import java.util.*;

class Solution {
    public int[] solution(int[] enter, int[] leave) {
        int[] answer = new int[enter.length];
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        HashSet<Integer> his = new HashSet<>();
        for(int i = enter.length-1; i>=0; i--)
            s1.add(enter[i]);

        for(int i=0; i<leave.length; i++){
            int cur_num = leave[i];
            ArrayList<Integer> cur_g = new ArrayList<>();
            while(s1.peek() != cur_num){
                cur_g.add(s1.peek());
                s2.push(s1.pop());
            }
            cur_g.add(cur_num);
            s1.pop();

            int new_face = 0;
            for(int num : cur_g)
                if(his.contains(num) == false)
                    new_face++;
            for(int num : cur_g){
                if(his.contains(num))
                    answer[num-1] += new_face;
                else
                    answer[num-1] += cur_g.size()-1;
            }

            for(int num : cur_g)
                his.add(num);

            while(!s2.isEmpty()){
                his.add(s2.peek());
                s1.push(s2.pop());
            }
        }
        return answer;
    }
}

피드백

• 이 문제는 2021 라인플러스 상반기 공채 기출문제이다.
• 먼저 반드시 만나는 그룹은 다음과 같이 만들어 질 수 있다.
  • 퇴실 대상자가 방에 있을 때 까지 입실 순서대로 입실시키고 바로 퇴실하면 반드시 만나는 그룹이 된다.
• 문제는 다른 그룹이 만들어 질때 그 그룹의 구성원끼리는 이미 만난 경우가 있을 수 있다. 이는 중복처리하여 세지 말아야 한다.
  • 이를 HashSet을 사용하여 이미 포함이 된 적이 있는 구성원은 새로운 구성원이 들어올때만 update 해준다.
  • a가 b를 만났다는 식의 his[][]를 사용하지 않고 그냥 his[]를 사용할 수 있는 이유는 한번 그룹에 포함되면 나갈때 까지는 한 그룹내에 있는 것이기 때문에 그룹에 들어왔는지 안들어왔는지만 판단하여 update해주기만 하면 된다.