프로그래밍2 /leetcode23/ Merge k Sorted Lists k 개의 정렬된 연결 리스트를 병합하여 하나의 정렬된 리스트로 만드는 문제이다. C++ STL의 priority_queue를 이용한 풀이를 통해, 우선순위 큐의 사용방식을 이해해본다. https://leetcode.com/problems/merge-k-sorted-lists/discuss/458432/C%2B%2B-20ms-beat-98.78-and-Python-84ms-beat-99.50 ListNode 구조체의 val 값을 비교하므로 < 연산자를 오버로딩하거나 bool operator( )를 갖는 구조체나 클래스를 정의해서 사용해야 한다. priority_queue의 정의는 priority_queue 방식으로 한다. 컨테이너는 기본설정과 동일한 vector컨테이너로 지정하였다. 우선 k 개의 벡터를 .. 2019. 12. 24. /leetcode 11/ Container With Most Water n 개의 0이 아닌 정수 a(1), a(2), ... , a(n)는 각각 수직으로 그려진 막대의 높이를 의미한다. x축과 함께 두 개의 막대로 만들 수 있는 컨테이너 중에서 가장 많은 물을 담을 수 있는 경우를 찾아서 그 때의 넓이를 반환한다. 가장 쉽게 생각해볼 수 있는 방법은 모든 경우의 넓이를 구해서, 최대 넓이를 구하는 방식이다. 이러한 brute force 방식은 time complexity가 O(n^2)이므로 효율적일 수 없다. ( leetcode runtime에서 실행시간 1240ms, 메모리 사용량은 9.8MB가 사용되었다.) 이에 따라서 Solution에 제시된 Two Pointer Approach를 적용해본다. Two Pointer Approach는 컨테이너에 담는 물은 두 개의 막대 .. 2019. 12. 23. 이전 1 다음