오늘의 문제는 정수로 이뤄진 nums라는 list가 주어질 때, continuous subarray를 구하는 문제이다. 이 때, subarray는 무작위로 2개의 원소를 뽑았을 때, 그 차이가 0이상 2이하를 만족해야 한다. 나는 이 문제를 처음엔 1) brute-force 방식으로 풀었고, 다음으론 2) impossible_set을 구하고 set을 활용해 여집합을 구하는 방식으로 풀었다. 하지만, 두 방식 모두 Time Limit Exceeded가 발생하여, 다른 사람의 풀이를 참고하였다. 2)와 같이 여집합을 활용한 문제 풀이의 경우 더 최적화 할 수 있는 방법이 있으리라 판단되나 정확한 풀이를 떠올리기까진 다소 오랜 시간이 소요될 것 같아 다른 사람의 풀이를 참고하였다.
그 중 직관적인 dfs를 활용한 풀이는 다음과 같았다.
0 ~ n-1까지 모든 i를 dfs 돌린다.
dfs는 다음과 같이 구성한다. ⇒ max값과 min 값을 갱신하고, 이 값이 2이하라면, dfs에 해당 max, min, i+1 값을 넣어 같 은 방식으로 찾는다.
⇒ 이와 같은 방식은 시간 복잡도가 높긴하지만, 가장 직관적인 것 같아 이 풀이를 참고하였다.
오늘은 Subarray를 다루는 문제를 풀이하였다. dfs, two-pointer, dp 등과 같이 다양한 유형을 활용하여 풀이할 수 있는 문제였다. 시간 복잡도를 고려하여 좋은 방법을 떠올리긴 하였으나, 아직 끝까지 알고리즘을 짜는 것이 부족한 것 같다. 이에 대한 연습이 필요하다.
열심히 연습하기.