쉬운 문제지만 작은 실수때매 망치지 말자라는 마인드를 가지고 문제 푸는 연습을 하고자 하는 마음가짐으로 오늘은 백준에 최소 회의실 개수 문제를 풀었다. 이 문제는 분명히 전에 봤었던 문제 유형이었는데 무슨 이유에서인지 내가 못풀어서 넘어갔지만 제목만 다르고 정말 문제 유형이 일치하는 추천문제를 봐서 다시 풀어봤다.
솔직히 테스트 케이스까지는 쉬워서 전부 통과 한다 하더라도 전체 테스트케이스를 통과 하는데 있어서 여럿 어려움이 있었다. 내가 처음에 풀었던 방식은 분명히 로직까지는 전부 맞았지만 디테일한 부분에서 여러가지 틀렸던 부분이 있었던거같다. 그래서 문제를 고치고 다시 보안하고자 아예 싹 다 갈아엎었고 두가지의 방식으로 풀어봤었다.
보면은 내가 주석으로 전부 지운 부분이 있을텐데 저 주석을 전부 풀어도 똑같은 답이 나오기에 풀이를 다시 해석해보자면, 먼저 시간을 pair<int,int> 로 입력해준다음에 강의에 시작순서를 기준으로 정렬을 해주었다. 즉, times 벡터안에서의 순서는 가장 먼저 시작하는 시간이 맨 앞에 순서대로 있다는것이다. 그리고 여기서 주목 할 점은 priority_queue (줄여서 pq)에 끝나는 시간을 넣어줬단건데 이 이유는 뭐냐면 문제에서 요구하는 상황을 좀 더 효율성 있게 지키려고 했기때문이다. 강의가 끝나는 시간이 다음강의가 시작하는 시간보다 같거나 크다면 한 강의실을 연속해서 사용할수있다, 그 점을 완전 탐색인 중첩 for 문으로 찾게되면은 이미 10만단위에 N이 100만 단위에 시간으로 늘어날수도 있다는 소리다.
그렇기 때문에 pq를 이용하여 끝나는 시간을 기준으로 min_heap 을 유지해줬다. 그리고 정렬된 타임스 벡터를 읽으면서 만약에 다음 강의가 시작되는 시간이 pq가 유지하고 있는 가장 적게 끝나는 시간보다 작다면은, (예: 0,40 -> 5,10) 0-40 에 유지하고 있는 강의시간은 무조건 적으로 회의실 하나가 필요한거다. 그렇기 때문에 더 유지할 필요가 없으므로 pq를 pop() 해주고 새롭게 끝나는 시간을 넣어준다. 그 외에 강의가 연속으로 이어질수 있을경우에는 pq에다가 계속 push 를 해주고 마지막에 남는 pq의 크기가 최소한으로 유지할수있는 강의에 시간이기 때문에 답으로 리턴을 해주면 된다.
솔직히 조금 더 문제에 흐름처럼 이해하고 싶다면은 pop된 강의를 다른 벡터안에 넣어두던지, 다른 pq 안에 넣어두던지 하는 방법도 있곘지만 앞으로 이런 유형의 greedy 문제가 나온다면 좀 더 자연스럽게 대처할수있겠다.
배운점:
1. pq 를 이용한 greedy 방법
2. 문제 요구사항 따라가기
