풀이법이 많이 안 와닿아서 몇 번을 봤는지 몰랐던 D2 레벨 문제
문제 설명이 길지 않아서 금방 풀 것 같았지만, 생각보다 고민해 볼 수 있는 포인트가 많은 문제였다.
문제 설명은 위의 이미지에 보다시피 어렵게 보이지 않았다. 다만, 문제를 어떻게 접근할지에 대해 고민을 해보게끔 하는 포인트들이 많았다.
게다가 input.txt 값을 보면 조금 경악을 하게 되는데 백만 이하라고 하면 Nested Loop를 사용하는 형태로 코드를 짜게되면 시간 초과가 거의 100% 나올 것이다.
연산 속도를 O(N) 정도로 생각하고 풀어야될 것 같았고, 사람에 따라 가능하다면 O(logN)도 도전해볼 수 있지 않을까 싶었다.
처음 이 문제를 접했을 때, 2가지 풀이의 가능성을 염두했었다.
- 탐욕 알고리즘 (Greedy Algorithms)
- 분할 탐색 (Binary Search)
“최대한의 이득”이라는 문구 덕에 처음에는 탐욕 알고리즘이 떠올랐지만, 해당 알고리즘 풀이법으로 접근하기는 어려웠던 것 같고, 두번째로 떠올린 게 max 값을 기준으로 분할 탐색하는 것이었다.
그러나 분할 탐색의 경우, 정렬이 된 상태에서 왼쪽 오른쪽 배열을 균등하게 나눠야해서 접근하는 방식이 틀렸고, 한참을 고민했었다.
그래서 다른 사람들의 코드를 많이 참조했었는데, 이 코드의 경우 탐색을 뒤에서부터 진행하는 것을 굉장히 자주 목격하게 되었다.
왜 뒤에서부터 탐색을 할까? 예를 들면, 4 5 8 6 2 라는 테스트 케이스가 주어졌다고 가정해보자.
이 경우, 시작하는 값이 마지막 값인 2부터 시작하기 때문에 마지막날에 팔면 안되고, 최대값을 변경해줘야한다. 이 조건문이 실행되는 기간이 8 ~ 10 줄이고, 마지막 값이 바로 옆의 값보다 크다면, 두 수의 차이만큼 결과 값에 더해주는 방식으로 접근하는 것이었다.
워낙 코드를 구현하는 방식이 다양하다보니, 생각하는 방식을 한 가지 방향으로 제한하면 안된다는 생각이 많이 든다.
꾸준히 코딩테스트 문제 정리하면서 기업 코테를 실전 겸 연습이라 생각하고 풀자.
충분한 연습과 시간으로 더 좋은 결과를 얻어낼 수 있다.
Ryan
