[프로그래머스] 위클리 챌린지 7주차 _ 입실 퇴실 후기

프로그래머스에서 진행하는 위클리 챌린지 7주차 문제이다.

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

코딩테스트 연습 - 7주차

꽤 재밌는 문제였다. 

프로그래머스 레벨2에 존재하는 문제이다.

이 문제 풀면서 느낀 점은... 프로그래머스 레벨2 범위가 생각보다 넓은 것 같다.

월간 코드 챌린지 시즌3 9월의 2번 문제랑, 이 문제랑 동급이라 생각되지 않는데, 둘이 같은 level 2 라는 것이 신기할 따름이다.

 

아무튼 간단하게 후기를 남겨보겠다.

 

*프로그래머스 정책에 따라 지문, 풀이 코드, 테스트케이스 공유는 하지 않습니다.*

---

후기

이 문제는 직접 손으로 써가면서 해야 좀 더 잘 풀린다.

맨 첨에 어렴풋이 생각난 거는 스택이었는데, 조금만 생각해보면 LIFO 구조가 전혀 아님을 생각해낼 수 있다. 아마 들어가는 문과 나가는 문이 동일하기 때문에 스택을 떠올린 것이 아닌가 싶다.

 

그 다음으로 생각난 것이 적절히 그래프 모델링을 해보자는 생각이었는데, 그래프까지 갈 필요도 없이 각 사람의 들어온 타임과 나간 타임을 이어주면 문제의 풀이가 잘 보일 것이다.

 

"나중에 들어온 사람"이 "먼저 들어온 사람"보다 먼저 나갈 경우, 그 경우가 바로 확실하게 만나는 타임이기 때문이다. 또한, "나중에 들어온 사람"보다 먼저 들어온 사람 중 "먼저 들어온 사람"보다 늦게 들어온 사람은 무조건 "먼저 들어온 사람"과 만났다는 점을 이용하여 적절히 구현해주면 된다. (쓰다 보니 말이 굉장히 헷갈리길래 '' 를 추가했는데도 헷갈려보인다...)

 

위와 같이 하면 O(N^2)의 시간복잡도로 문제를 해결할 수 있다.

다른 사람의 풀이를 봤는데 O(N^2) 미만의 빠른 시간복잡도 풀이는 딱히 없는 것 같다. 월요일에 풀어서 너무 일찍 풀었기 때문에 없는 걸수도 있긴 하지만 말이다.

 

원래 위클리 챌린지 문제는 귀차니즘때문에 되게 늦게 푸는 편인데, 월간 코드 챌린지 9월 해설 보다가 우연히 해결하게 되었다.

---

다른 사람의 풀이 창에 접근할 수 있다는 것이 내가 문제를 해결했다는 증거가 될 수 있으므로

이번엔 위 사진으로 대신 인증한다~

 

크게 얻은 건 없는 것 같지만, 재밌게 잘 푼듯하다.