시간 초과 및 프로그래머스(연속된 부분 수열의 합)

💡 오늘의 학습 키워드

- 시간 초과
- 프로그래머스
    * 연속된 부분 수열의 합 : 미들러 문제(Level 2)

 

오늘의 회고

문제1  : [연속된 부분 수열의 합]

• 어떤 문제가 있었고, 나는 어떤 시도를 했는지

오름차순으로 정렬된 수열이 주어질 때, 부분 수열의 합이 K인 왼쪽, 오른쪽 인덱스를 리턴하는 문제이다.

여러 개인 경우 길이가 짧은 수열이, 길이가 짧은 수열이 여러 개인 경우는 앞쪽의 인덱스를 리턴해야 한다.

 

처음엔 어떻게 할지 몰라서 생각해보다가 수열이니까 BFS/DFS 이런 걸 사용하는 건가 싶어서 찾아봤다.

그런데 재귀인 것도 같고.. 아직 어떤 알고리즘을 어느 문제에 사용해야 하는지 익숙하지 않아 고민하다가 시간이 훌쩍 흘러버렸다. 그래서 결국 해당 문제를 풀이하신 분의 블로그를 찾아보았다.

• 투 포인터

투 포인터를 이용해서 풀이할 수 있다는 Tip을 얻고 투 포인터로 문제를 풀었지만..

처음엔 뭐가 안됐다. 그래서 계속해서 바꿔보다가 해결하신 분의 블로그를 보고 비슷하게 풀이했다.

완전 똑같지는 않았지만, 비슷하게 했는데 시간초과!?! 

근데 아직 뭐가 문제인지 모르겠다. 분명 비슷하게 풀었는데 왜 시간초과지......

 

프로그래머스

 

• 어떻게 해결했는지(통과하지는 못함)

class Solution {
    public int[] solution(int[] sequence, int k) {
        int len = sequence.length;
        int left_idx = 0;
        int right_idx = 0;
        int left = 0;
        int right = len;
        int sum = 0;
        int[] answer = new int[2];
        while (left_idx < len) {
            right_idx = left_idx;
            sum = 0;
            while (right_idx < len && sum < k) {
                sum += sequence[right_idx];
                right_idx++;
            }
            if (sum == k) {
                int range = right_idx - left_idx - 1;
                if ((right - left) > range) {
                    left = left_idx;
                    right = right_idx - 1;
                }
                if (range == 0)
                    break;
            }

            left_idx++;
        }
        
        answer[0] = left;
        answer[1] = right;
        
        return answer;
    }
}

 

* 참고한 블로그

[프로그래머스 Level 2] 연속된 부분 수열의 합 (Java)

 

• 무엇을 새롭게 알았는지

이런 문제는 투 포인터를 이용해서 풀이한다는 걸 깨달았다.

해당 블로그만 보고 이거 작성하다가 다른분이 풀이하신 블로그도 봤는데 투 포인터를 너무 잘 설명해놨다.

그런데 저거 보고 깨달은게 난 투 포인터의 개념을 이상하게 생각하고 있던 것 같은데.. 

아래의 블로그도 보니 어떻게 풀이해야 할 지 감이 잡힌다. 내일도 9-9 수업이기에 시간이 될 지 몰겠지만..

시간 날 때 다시 살펴봐야할 것 같다.

 

* 참고한 블로그

[프로그래머스] 연속된 부분 수열의 합 Lv2 JAVA [투포인터][엄탱]

 

내일 학습할 것은 무엇인지 (최대 3개)

• 정보처리기사 실기
• 자바 형변환 정리
• 클럽99 코딩테스트(미들러)