3. 프로그래머스 - 연속된 부분 수열의 합

 

문제 설명  비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.   - 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.   - 부분 수열의 합은 k입니다.   - 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.   - 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.  수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분  수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요.  이때 수열의 인덱스는 0부터 시작합니다.

 

문제 해결  1. 주어지는 건 1차원 배열이지만 s ~ e 까지의 합이라는 조건 때문에 2차원 배열처럼 사용할 수 있다.     이를 통해 조건을 맞추면 맵에서 이동하듯 0,0 부터 4,4 까지 원하는 수를 밟아가며 이동할 수 있게 된다.  2. Start와 End는 0부터 시작  3. 현재 수가 원하는 수보다 작거나 같다면 End를 증가  4. 현재 수가 원하는 수보다 크다면 Start를 증가  5. Start는 End보다 커질 수 없음  6. 원하는 수를 찾았다면 Start를 증가시킴  7. 만약 End가 끝에 도달했다면 Start를 증가시킴  8. 정답을 고를때 밟은 곳의 Start와 End거리가 가장 가까운것을 우선적으로 선택함

 

    public class Node
    {
        public Node(int s, int e)
        {
            str = s;
            end = e;
            len = e - s;
        }

        public int len;
        public int str;
        public int end;
    }

    public int[] solution(int[] sequence, int k)
    {
        int start = 0;
        int end = 0;
        int sum = sequence[0];

        List<Node> nodes = new List<Node>(sequence.Length);

        if (sum == k)
        {
            return new int[] { start, end };
        }
        
        int limit = sequence.Length - 1;
        while (true)
        {
            //값이 작거나 같고 끝에 닿지 않았을때
            if (sum <= k && end < limit)
            {
                sum += sequence[++end];
            }
            //값이 크거나 end가 끝에 도달했다면
            else if(sum > k || end == limit)
            {
                sum -= sequence[start++];
            }
            
            if (sum == k)
            {
                Node n = new Node(start, end);
                if (n.len == 0)
                {
                    return new int[] { start, end };
                }

                nodes.Add(new Node(start, end));
            }

            //둘다 끝에 도달했다면
            if (end == limit && start == limit)
            {
                break;
            }
        }

        nodes.Sort((item1, item2) => item1.len.CompareTo(item2.len));

        return new int[] { nodes[0].str, nodes[0].end };
    }

 

어떻게 해야할지 해매다가 일단 공책에 표를 만들어보니 맵처럼 이동이 가능하겠다는 생각이 들어서 해결한 문제

문제를 풀고나서 다른 사람의 풀이를 보니 내가 사용한 방법이 투 포인터라는 이름으로 이미 있었다.