티스토리 뷰

IT & Programming

[LeetCode] Median of Two Sorted Arrays

시부야에 사는 사람 2017.06.06 22:46

음.. 오랜만에 LeetCode 에서 문제를 풀어 보았다. 할일이 없도록 엄청나게 한가해서는 아니고, 나는 언제나 무엇이든지 빨리 질리고 불만을 찾아내는 특출난 능력을 가지고 있기 때문에, 언젠가 하게 될 이직 준비를 위해, 또한 나의 사고를 확장 시키기 위해 알고리즘 문제를 풀어보았다. 요즘 Scala로 코딩을 하다 보니까 ';' 을 찍어야 하는 Java가 불편하게 느껴지고 있고, Scala 가 좀 더 깔끔하다는 생각도 든다. 하지만, LeetCode 에서는 Scala 를 지원하지 않는다. 그래서 그냥 Java 로 하는거다. Java 가 알고리즘 연습하기에는 좀 더 나을지도?


문제는 Median of Two Sorted Arrays 이다. 

문제를 읽어 보면 알겠지만 두개의 정렬된 배열이 주어지고, 그 두개의 배열을 합쳐 중간값을 찾아내는 문제이다. 

코딩상으로 제일 깔끔한 방법은, 두개의 배열을 하나의 배열로 일단 합친 후에 쫙~정렬을 하는 것일 것이다. 하지만, 문제를 보면 정렬된 배열이 주어진다고 되어 있고, 문제에서 주어진 상황은 Merge Sort의 중간 과정처럼 보인다. 그래서 Merge Sort 의 마지막 단계에서 하는 마지막 두개의 정렬된 배열을 하나의 배열로 정렬하면서 합치는 작업을 하도록 했고, 중간값의 위치에 도달 했을 때 값을 빼내도록 해서 완벽하게 정렬 작업을 하지 않아도 값을 구해내도록 했다. 코드는 아래와 같다.

이 알고리즘의 시간복잡도는 아마도 O(n). 

댓글
댓글쓰기 폼