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

문제 링크:

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

코딩테스트 연습 - 7주차

 

굉장히 좋은 문제라고 생각합니다!

저는 처음에는 약간 단순한 방법으로 풀었는데...

1. 들어온 시간 기준 a > b, 나간 시간 기준 a < b이거나 그 반대이면 반드시 만난다.

2. 그렇지 않은 경우, 들어온 두 사람의 시간 사이에 들어오지 않은 사람이 먼저 나간 사람보다 더 먼저 나간 경우, 두 사람은 반드시 만난다.

 

위 조건을 매번 확인하는 식으로 구현했으나 시간 초과에 걸렸습니다.

#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

bool has_different_order (int enter_i, int enter_j, int leave_i, int leave_j) {
    
    //a가 b보다 먼저 들어왔고
    //b가 a보다 먼저 나갔으면
    //a와 b는 반드시 만났다.
    if (enter_i < enter_j && leave_i > leave_j) return true;
    if (enter_j < enter_i && leave_j > leave_i) return true;
    return false;
}

bool has_elements_between (int enter_i, int enter_j, int leave_i, int leave_j, vector<int> &enter, vector<int> &leave) {
    
    int enter_min = min(enter_i, enter_j);
    int enter_max = max(enter_i, enter_j);
    int leave_min = min(leave_i, leave_j);
    int leave_max = max(leave_i, leave_j);
    
    //O(n)
    int iter = 0;
    for (iter = 0; iter < leave_min; iter++) {
        int current = leave[iter];
        
        int enter_enter_i = enter[enter_i];
        int enter_enter_j = enter[enter_j];
        
        bool could_meet = false;
        //O(n)
        for (int i = 0; i < enter_max; i++) {
            if (enter[i] == enter_enter_i || enter[i] == enter[enter_j])
                continue;
            if (current == enter[i]) {
                could_meet = true;
                break;
            }
        }
        if (!could_meet) return true;
    }

    return false;
}

vector<int> solution(vector<int> enter, vector<int> leave) {
    
    int n = enter.size();
    vector<int> answer(n);
    map<int, int> enter_count;
    map<int, int> leave_count;
    
    //배열 내에서 각자의 위치를 기록한다.
    for (int i = 0; i < enter.size(); i++) {
        enter_count.insert({enter[i], i});
    }
    for (int i = 0; i < leave.size(); i++) {
        leave_count.insert({leave[i], i});
    }
    
    //모든 인원에 대해 위 조건을 확인한다. O(n^2)
    for (int i = 1; i < n; i++) {
        for (int j = i+1; j <= n; j++) {
            
            bool temp  = false;
            if (has_different_order(enter_count[i], enter_count[j], leave_count[i], leave_count[j]))
                temp = true;
            else {
                if (has_elements_between(enter_count[i], enter_count[j], leave_count[i], leave_count[j], enter, leave))
                    temp = true;
                else temp = false;
            }            

            if (temp) {
                answer[i-1]++;
                answer[j-1]++;
            }
        }
    }
    return answer;
}

 

그래서 위 방법으로는 답이 없다고 생각하여 다시 고민해 보다가...

얼마 전에 접했던 투-포인터 방식을 생각해 냈습니다.

 

두 포인터는 front, end 두 개를 두었습니다.

조건 내에서, end에 해당하는 수가 list (room) 내에 존재한다면, 내보내고 end 포인터를 하나 증가시킵니다.

존재하지 않는다면, 현재 들어온 사람에 해당하는 answer list에 room list를 복사하고, room list에 현재 들어온 사람을 넣습니다.

 

위 과정을 반복하고 나면, a와 만난 사람 = [b, c, d...] 와 같은 리스트가 완성됩니다.

여기서, a가 b와 만났다면, b 또한 a와 만났으므로 이를 역으로 추가해 주는 작업을 해야 합니다.

중복인 경우도 있지만 이는 뒤에서 걸러내면 됩니다.

 

모두 추가한 후에는 set 자료구조를 활용합니다.

set은 중복을 허용하지 않으므로, a와 만난 사람 = {b, b, c, d, e, e}인 경우, 해당 원소를 set에 전부 집어넣고 그 크기를 구하면 4가 됩니다.

이 크기를 정답 배열에 적어 주고, 정답 배열을 반환하면 됩니다.

 

채점 결과

 

앞에서 풀었던 매우 비효율적인 방법에 비해 시간이 훨씬 덜 걸리는 것을 확인할 수 있었습니다!

투-포인터 문제를 좀 많이 풀어봐야겠습니다.