[프로그래머스,자바] Level2: 위클리챌린지 7주차 [입실 퇴실]

문제분석:

 

처음 읽고 이게 뭘 구현하란거지? 5번은읽어봤다.

 

정리하자면,  입실시간기록과 퇴실시간기록이 없는 그냥 "순서" 만 있는 배열 Enter와 Leave가 주어졌다.

순서를 보고 각 사람이 반드시 만나는 사람의 수를 구하는문제다.

 

근데 순서만보고 각 사람이 반드시 만나는 경우가 도대체 무슨소리며,  도대체 어떤 경우인가?

 

바로,  모두가 들어오자마자 바로 나갔을경우다.

 

모두가 들어오자마자 나갔는데도, 만난경우가 있다면 기록에 상관없이 무조건 만난다

 

예시로 입실순서 [1,4,2,3] 퇴실순서 [2,1,3,4]를 예시로 보겠다.

 

1.  1번이 입실했다. 하지만 퇴실순서가 2번이 먼저니 방에 남는다. room[1]

2.  4번이 입실했다. 하지만 퇴실순서가 2번이 먼저니 방에 남는다. room[1,4] (두 사람은 만났다)

3.  2번이 입실했다. 퇴실순서가 2번이왔으니 들어오고 바로 나갔다. room[1,4,2]->room[1,4]

    (여기서 2번은 들어왓다 바로 나갔지만, 1,4,2번 사람 세사람은 모두 만났다) 

4.  퇴실순서가 1번이되었다. 1번이 나갈수있으니 1번이나갔다. room[4]

5.  퇴실순서가 3번이되었다. 3번은 방에 3번이없으니 넘어간다. room[4]

6. 3번이 입실했다. 퇴실순서가 3번이니 들어오고 바로 나간다. room[4,3]->room[3]

    (여기서 3번은 들어왓다 바로 나갔지만, 4번과 만났다.

7. 퇴실순서가 4번이 되었다. 4번이 나간다. (종료)

 

여기까진 알겟는데.. 구현이 참 어렵다. 구현 고민을 2일한거같다.

이 로직의 첫번째 큰 조건은 방 안에 나갈사람이 있냐? 이다.

 

이 틀을 유지하면서 , 모든 사람이 입실, 모든 사람이 퇴실하면 반복을 종료한다.

 

문제풀이:

중요한 로직만 해설하자면, 사람을 저장할 Room을 Map으로 구현했다.

 

그 이유는, List나 Array로 하면 퇴실할 사람을 찾는데 매번 최대 O(n) 시간이 걸린다.

Map은 상수시간이 걸리니 Map을 이용했다. 

 

첫번째 큰 반복을 벗어날 조건을 (입실과 퇴실이 모두 끝마쳣을때 : i 가 n, j가 n 일때) 로 설정

 

두번째 반복인 퇴실할 사람이 있는 탈출 조건을 방 안에 퇴실할 사람이 없는경우 break를 해줬다.

 

그리고 각 루트마다 만난 사람을 세주었다.

 

import java.util.*;
class Solution {
    public int[] solution(int[] enter, int[] leave) {
      
        int people = enter.length;
        int[] answer = new int[people];
        Map<Integer,Integer> room =new HashMap<>();
        int i=0;
        int j=0;       
        while(i!=people&&j!=people){           
           room.put(enter[i],enter[i]);        
           if(room.size()>1){
               for(int key:room.keySet()){
                   answer[key-1]++;
               }
               answer[enter[i]-1]+=room.size()-2;   
           } 
            
          while(true){                              
           if(j<people&&room.containsKey(leave[j])){
            room.remove(leave[j]);
            j++;
               
           }
           else{ break;}   
          }       
            i++;
        } 
        return answer;
    }
    
    
}