[프로그래머스] 위클리 챌린지(7주차) - "입실 퇴실" (Java)

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

코딩테스트 연습 - 7주차

 

입실 퇴실

---

 

난이도 :  Level 2

 

 이 문제는 적절한 자료구조를 이용하고, 문제를 정확히 이해하는 것이 핵심이라고 생각합니다. 개인적인 생각이지만 이러한 문제는 문제에서 의도하는 풀이가 있는 것 같습니다.  

 

 다음과 같은 로직으로 문제를 설계했습니다. 

1. 자료구조를 이용하여 각 사람마다 만난 사람의 수를 저장한다. 

2. 나간 순서를 기준으로 반복문을 탐색한다. 

3. 자료구조를 이용하여 들어온 사람을 저장한다. 

4. 현재 나갈 순서의 사람이 존재할 때까지 사람을 입장시킨다. 

5. 자료구조의 크기가 2 이상이 되면, 각 사람마다 만난 사람의 수를 저장한다. 

 

 이 문제에서 핵심은 각 사람별로 반드시 만난 사람은 몇 명인지 구하는 것입니다. 최대한 모든 사람이 각자 만나지 않게 하는 것이 반드시 만난 사람을 구하는 방법이라고 생각합니다. 그리고 그 방법은 회의실에 들어오는 사람이 퇴실 순서가 됐으면 바로 내보내는 것입니다. 예를 들어, 입실 순서도 1번이고 퇴실 순서도 1번이면 다른 사람이 들어오기 전에 바로 내보내는 것입니다. 

 

 또한, 각 사람마다 만난 사람의 수를 저장하는 과정에서 시간 초과를 발생하였습니다. 기존에는 이중 배열로 첫 번째 반복문에서 사람을 기준으로 잡고 두 번째 반복문에서 다른 사람들을 탐색하여 Set 자료구조에 저장하는 형식으로 했지만 시간 초과를 발생했습니다. 

 

 시간 초과 이슈는 로직을 바꿔줌으로써 해결했습니다. HashMap <Integer, Integer> 자료 구조를 사용하였습니다. 새로운 사람이 들어왔을 경우를 판단하는 boolean 변수를 생성하였고, 새로 들어온 사람(Key)은 기존 HashMap 사이즈의 -1 한 값(Value)을 저장하였고, 기존에 있는 사람들(Key)한테는 +1 한 값을(Value) 추가하였습니다. 

 

 

 

- static HashMap<Integer, Integer> meetPeople;

 각 사람마다 만난 사람의 수를 저장하는 자료구조입니다. Key는 각 사람의 번호이고, Value는 그 사람이 만난 사람의 수입니다. 

 

 

 

- static List<Integer> in = new LinkedList <>();

 회의실에 들어오는 사람을 저장하는 자료구조입니다. 

 

 

 

- static int inIndex = 0;

 회의실로 들어올 사람을 정하는 index 변수입니다. 

 

 

 

- int [] solution(int[] enter, int[] leave)

 HashMap 자료구조를 초기화하고 각 사람마다 만난 사람의 수를 0으로 정합니다. 이 과정이 있어야 Test Case 1번을 통과할 수 있었습니다. 

 

 나간 사람의 순서를 기준으로 반복문을 순회합니다. 그리고 나갈 순서의 사람이 회의실에 존재할 때까지 사람을 입실시킵니다. 

 

 

 

- void enterCheck(int outPerson , int [] enter)

 회의실로 들어올 사람을 검사하는 함수입니다. 예를 들어, 현재 나갈 사람이 2번 사람이면 2번 사람이 들어올 때까지 회의실에 입실시킵니다.

 

 회의실에 들어온 사람이 2명 이상이고 새로 들어온 사람이 존재하면, 새로 온 사람은 기존에 있는 사람 수만큼 만나게 되므로 Map 자료구조에 list 자료구조 사이즈 -1 한 값을 저장합니다. 기존에 있는 사람들한테는 새로 들어온 사람 1명이 추가된 것이므로, 기존 Value에 +1 한 값을 다시 저장합니다.

 

 이 과정을 거친 후, 현재 방 안에 남아 있는 사람들 중 떠날 사람이 존재하는지 체크하는 LeaveCheck 함수를 호출합니다. 

 

들어온 사람을 바로 내보내기 위하여 위와 같은 순서로 코드를 작성하였습니다.

 

 

 

- boolean leaveCheck (int outPerson)

 떠날 순서가 된 사람이 회의실에 존재하면 내보내는 함수입니다. 

 

 

  정답 코드

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

class Solution {
	static HashMap<Integer, Integer> meetPeople;
	static List<Integer> in = new LinkedList<>();
	static int inIndex = 0;
    
    public int[] solution(int[] enter, int[] leave) {
        int[] answer = new int[enter.length];
        // Map 초기화 
        meetPeople = new HashMap<>();
        for(int i=1; i<=enter.length; i++) {
        	meetPeople.put(i, 0);
        }
        for(int i=0; i<leave.length; i++) {
        	int outPerson = leave[i];
        	enterCheck(outPerson, enter);
        }
        
        for(int i=0; i<answer.length; i++) {
        	answer[i] = meetPeople.get(i+1);
        }
        return answer;
    }
    
    public void enterCheck(int outPerson ,int[] enter) {
    	
    	while(inIndex < enter.length) {
    		boolean inRoom = false; // 새로온 사람이 들어왔는지 체크
    		int newPerson = 0; // 새로온 사람이 누군지
    		if(enter[inIndex] != 0) {
    			in.add(enter[inIndex]);
    			newPerson = enter[inIndex];
    			// 방문 체크 
    			enter[inIndex] = 0;
    			inRoom = true;
    		}
 
    		// in size가 2 이상이고, 새로운 사람이 들어왔다면 
    		if(in.size() >= 2 && inRoom) {
    			// 새로온 사람은 기존에 있는 사람들 수 만큼 만난다. 
    			meetPeople.put(newPerson, in.size()-1);
    			
    			// 기존에 있는 사람들한테는 1명이 추가된 것이다. 
    			for(int person : in) {
    				if(person == newPerson) continue;
    				meetPeople.put(person, meetPeople.get(person)+1);
    			}
    		}
    		if(leaveCheck(outPerson)) {
    			return;
    		}
    		inIndex++;
    	}
    	
    }
    
    public boolean leaveCheck (int outPerson) {
    	if(in.contains(outPerson)) {
    		int i = in.indexOf(outPerson);
    		in.remove(i);
    		return true;
    	}
    	return false;
    }
}

 

 

  시간 초과가 난 코드 

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class PM_86048 {
   static Set<Integer>[] meetPeople;
   static List<Integer> in = new LinkedList<>();
   static int inIndex = 0;
   
    public static int[] solution(int[] enter, int[] leave) {
        int[] answer = new int[enter.length];
        meetPeople = new Set[enter.length];

        for(int i=0; i<meetPeople.length; i++) {
           meetPeople[i] = new HashSet<>();
        }
        for(int i=0; i<leave.length; i++) {
           int outPerson = leave[i];
           check_in(outPerson, enter);
        }
        
        
        for(int i=0; i<meetPeople.length; i++) {
           answer[i] = meetPeople[i].size();
        }
        return answer;
    }
    
    public static void check_in(int outPerson ,int[] enter) {
       
       while(inIndex < enter.length) {
          // 방문 체크 
          if(enter[inIndex] != 0) {
             in.add(enter[inIndex]);
             enter[inIndex] = 0;
          }
 
          // in size가 2 이상이면 meetPeople 배열에 값 추가 
          if(in.size() >= 2) {
             for(int i=0; i<in.size(); i++) {
                int person = in.get(i)-1;
                for(int j=0; j<in.size(); j++) {
                   if(i == j) continue;
                   meetPeople[person].add(in.get(j));
                }
             }
          }
          if(check(outPerson)) {
             return;
          }
          inIndex++;
       }
       
    }
    
    public static boolean check (int outPerson) {
       // in 리스트에 나갈 사람이 있으면 삭제 후 return
       if(in.contains(outPerson)) {
          int i = in.indexOf(outPerson);
          in.remove(i);
          return true;
       }
       return false;
    }
}

 

 

 

 

 

피드백 환영합니다.