프로그래머스 - 위클리 챌린지 7주차 - 입실 퇴실 - swift

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

코딩테스트 연습 - 7주차

 

문제 유형은 구현문제 일수도 있고, 나는 스택으로 풀어냈다. 

 

구현문제로 접근하려고 논리를 세워봤지만 코드로 작성할 수 있는 깔끔한 논리가 떠오르지 않았다. 

예를들어, 확실하게 만난 사람은, 다음과 같을 수 있겠다

1. 자신이 들어온다음에 들어온 사람들 중에서,  자신이 나가기전에 있는 사람들에 속한다면 반드시 만났겠다.

2. 자신이 들어오기 전에 사람들 중에서, 자신이 나간 후에도 있는 사람들에 속한다면 반드시 만났겠다. 

이 논리가 부족한 이유는,

입실 [1, 4, 2, 3]  퇴실 [2, 1, 3, 4] 와 같이 4번이 1번을 만났다라는 것을 알 수가 없다. 

여기서 조건을 추가해서 할 수도 있겠지만 너무 복잡해지는 것 같아서 그만두었다. 

 

스택으로 접근

그래서 최대한 시간 순서대로 순차적으로 접근해보았고, 스택을 찾을 수 있었다.

 

현재 방안에 있는 사람을 표현하기 위한 rooms 배열로 만든다. 

입실 [1, 4, 2, 3]  퇴실 [2, 1, 3, 4] 인경우에, 

처음에는 rooms에 아무도 없다.

입실에는 1번이 가장 먼저 들어왔다는 건 당연하고, rooms에 추가하기에 앞서

우선 퇴실에 가장먼저 퇴실한 사람이 rooms에 속하는지 확인한다. 

없으니까 rooms에 1번을 추가한다. 

rooms = [ 1 ] ,  입실 예정 [ 4, 2, 3 ], 퇴실 예정 [ 2, 1, 3, 4]

 

마찬가지로 4번을 추가하기전에, 퇴실에 가장 먼저 퇴실할 사람이 2번인데, 없으니 4번을 rooms에 추가한다.

rooms = [ 1, 4 ],  입실 예정 [ 2, 3 ], 퇴실 예정 [ 2, 1, 3, 4]

 

여기서 알 수 있는 사실이 4번과 1번은 반드시 만났다는 점이다. 

 

마찬가지로 2번을 추가하기전에 가장 먼저 퇴실할 사람이 2번인데, 아직 입실을 안했으니 퇴실시킬 수 없고, 그러므로 2번을 추가한다.

rooms = [ 1, 4, 2 ], 입실 예정 [ 3 ], 퇴실 예정 [ 2, 1, 3, 4]

 

자명하게도 1, 4, 2 번이 각각 서로 만났다는 것을 알 수 있다.

 

그럼 이제 3번을 추가하기 전에, 가장 먼저 퇴실한 사람이 속하는지 보는데, 2번이 속하므로, rooms에서 2번을 삭제한다. 

rooms = [1, 4 ] 입실 예정 [ 3 ], 퇴실 예정 [ 1, 3, 4]

 

그럼 3번을 추가하기 앞서, 퇴실예정에 1번이 속하므로, rooms에서 1번을 삭제한다.

rooms = [ 4 ] 입실 예정 [ 3 ], 퇴실 예정 [ 3, 4]

 

이제 3번을 추가할 수 있고, 마찬가지로 4번과 3번은 반드시 만났다는 것을 알 수 있다. 

rooms = [4, 3 ] 입실 예정 [ ], 퇴실 예정 [ 3, 4]

 

이제 3번을 퇴실시키고, 

rooms = [4 ] 입실 예정 [ ], 퇴실 예정 [ 4 ]

 

4번을 퇴실시킨다. 

rooms = [ ] 입실 예정 [ ], 퇴실 예정 [ ]

 

이거를 코드로 풀어내기 위해서 enter와 leave를 거꾸로 된 배열로 만들어서 removeLast를 하도록 했다. 

func solution(_ enter:[Int], _ leave:[Int]) -> [Int] {
    var ans = Array(repeating: 0, count: enter.count)
    var enter = Array(enter.reversed())
    var leave = Array(leave.reversed())
    var rooms = [Int]()
    
    while !enter.isEmpty || !leave.isEmpty {
        while !leave.isEmpty, rooms.contains(leave.last!) {
            let x = leave.removeLast()
            rooms.remove(at: rooms.firstIndex(of: x)!)
        }
        if enter.isEmpty { continue }
        rooms.forEach {
            ans[$0-1] += 1
        }
        let x = enter.removeLast()
        ans[x-1] += rooms.count
        rooms.append(x)
    }
    
    return ans
}