[프로그래머스] 입실 퇴실 - Java

- 링크 : https://programmers.co.kr/learn/courses/30/lessons/86048?language=java 

코딩테스트 연습 - 7주차

- 풀이 

 - 처음에 생각해야 할 부분이 무조건 만나는 경우를 생각하기 위해서는 worst case를 생각해야 한다.

    이는 leave 의 조건이 충족하자마자 바로 나가는 경우이다.

    떠날 수 있을 때 바로 떠나는 경우를 기준으로 생각하고 푼다면 답을 얻을 수 있다.

 

 - 설정 부분

 

 1. 들어온 사람이 중복되지 않으므로 enter length 길이가 들어온 사람 수이다.

 2. 이를 이용해 map을 초기화

 3. leave 배열 생성 (remove 가 많이 일어나고 search가 별로 없을 것 같아서 linkedlist로 선택)

 4. room 배열 생성 (방에 들어왔다가 나갔다하는 배열 이 역시 add remove 가 많을 것 같아서 linkedlist로 선택)

 

 - 로직 부분

 

 1. enter 배열에서 room으로 방에 들어온 사람을 확인한다.

 2. room에 2명 이상의 사람이 들어올 때 count 시작

 3. ex. room : [1, 2] 이고 3이 방에 들어왔다고 할 때
   기존에 있던 사람(1, 2) 에게는 현재 카운트 + 1, 현재 새로 들어온 사람(3)은 이전에 들어와 있던 사람 수(2명) 을 기록한다.

  이를 마지막으로 들어왔을 때까지 해주면 된다.

 

 - 코드

import java.util.*;

class Solution {
    public int[] solution(int[] enter, int[] leave) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i=1; i<=enter.length; i++) {
            map.put(i, 0);
        }
        
        List<Integer> lArr = new LinkedList<>();
        for (int i=0; i<leave.length; i++) {
            lArr.add(leave[i]);
        }
        
        List<Integer> room = new LinkedList<>();    
        
        for (int i=0; i < enter.length; i++) {
            int a = enter[i];
            room.add(a);
            
            if (room.size() > 1) {
                for (int j=0; j < room.size(); j++) {
                    int peopleNum = room.get(j);
                    map.put(peopleNum, map.getOrDefault(peopleNum, 0) + 1);
                }
            }
            
            map.put(a, room.size()-1); // 나 자신을 제외한 만난 사람 수
            
            while(lArr.size() > 0 && room.contains(lArr.get(0))) {
                room.remove(lArr.get(0));
                lArr.remove(0);
            }
        }
        
        int[] answer = new int[map.size()];
        int i = 0;
        for (int key : map.keySet()) {
            answer[i++] = map.get(key);
        }
        return answer;
    }
}

 

 - 처음에 틀렸던 풀이

 

  - 나름 고민했는데 틀렸지만 기록해 두려고 한다.

  - 시도한 부분

    - 방에서 나가는 시점을 기준으로 반드시 그 사람이 있었던 경우를 2가지로 나누었다.

     a가 반드시 b를 만나는 경우

    1. b가 a보다 늦게 들어왔지만 b가 먼저 나갔다.

    2. b가 a보다 늦게 들어왔고 b가 늦게 나갔지만 b보다 더 늦게 들어온 c가 먼저 나갔다.

        (더 늦게 들어온 사람이 더 늦게 나갔다면 a를 만났는 지 확신할 수 없음)

 

  - 문제점

    - 해당 코드가 내 생각에는 O(N^4)까지 갈 수 있는 코드였다. 이는 시간 초과를 이끄는 코드였고 해당 코드는 실패했다.

    - 시간 복잡도를 고려한 풀이가 생각나지 않아서 시도한 코드였지만 이 방법을 기록 해 놓고 싶었다.

 

 - 실패 코드

import java.util.*;

class Solution {
    public int[] solution(int[] enter, int[] leave) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i=1; i<=enter.length; i++) {
            map.put(i, 0);
        }
        
        for (int i=0; i<enter.length; i++) {
            for (int j=i+1; j<enter.length; j++) {
                int a = enter[i];
                int b = enter[j];
                int eaIdx = i;
                int laIdx = getLeaveIndex(a, leave);
                int ebIdx = j;
                int lbIdx = getLeaveIndex(b, leave);
                if (laIdx - lbIdx > 0) {
                    // b가 a보다 늦게 들어왔는데 b가 먼저 나감
                    map.put(a, map.getOrDefault(a, 0) + 1);
                    map.put(b, map.getOrDefault(b, 0) + 1);
                    continue;
                }
                
                // b가 a보다 늦게 들어오고 b가 늦게 나갔지만 b보다 더 늦게 들어온 c가 먼저 나감
                for (int k=j+1; k<enter.length; k++) {
                    int c = enter[k];
                    int lcIdx = getLeaveIndex(c, leave);
                    if (lcIdx < laIdx) {
                        lbIdx = lcIdx;
                        break;
                    }
                }
                
                if (laIdx - lbIdx > 0) {
                    // b가 a보다 늦게 들어왔는데 b가 먼저 나감
                    map.put(a, map.getOrDefault(a, 0) + 1);
                    map.put(b, map.getOrDefault(b, 0) + 1);
                    continue;
                }
            }
        }
        
        int[] answer = new int[map.size()];
        int i = 0;
        for (int key : map.keySet()) {
            answer[i++] = map.get(key);
        }
        return answer;
    }
    
    public int getLeaveIndex(int num, int[] leave) {
        for (int i=0; i<leave.length; i++) {
            if (leave[i] == num) {
                return i;
            }
        }
        
        return -1;
    }
}