코딩테스트 준비 F - 수들의 합 2

다시푸는 코딩 테스트 준비 일지

• 응시 사이트 : BOJ

• 문제 : 2003.수들의_합_2

• 사용언어 : C#

• 난이도 : Easy

• 풀이시간 : 31m +

• 유형 : 투 포인터

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

예제 입력 1 복사

4 2
1 1 1 1

예제 출력 1 복사

3

예제 입력 2 복사

10 5
1 2 3 4 2 5 3 1 1 2

예제 출력 2 복사

3

문제 풀이 접근

이 문제는, 투 포인터, DFS 등 여러 방법을 활용할 수 있는 문제로 보인다.
제시하는 문제의 조건은 수열은 정해져있고, 수열의 i 번째 수 부터 J 번째 수 까지 M이 되는 경우의 수를 구하는 것인데, 이는 무슨의미냐면 1 2 3 4 5 이고 M 7일때, 경우의 수를 구하라. 이는 3+4, 1개만 존재하는데 연속되는 배열을 더했을 때 M이 되는 경우의 수를 출력하라는 의미다.

나는 문제를 해결하기 위해 앞선 시리즈인 수들의합5 처럼 기준이 되는 인덱스(Standard)부터 출발하여 좌측에서 우측으로 더하는 방식을 선택했고 투 포인터 알고리즘이기때문에, 우측 기준부터 좌측으로 넘어가는 것도 동일하게 작성했다.

중간의 _IsSuccess 로 시작하는 필터링 구문은 LeftIndex 와 rightIndex가 동일한데, leftIndex에서 이미 Pass 처리를 했다면 중복으로 처리할 필요는 없기 때문에, 예외처리를 한 구문이다.

작성 코드 (C#)

using System;
using System.Collections;
using System.Collections.Generic;
using System.Xml.Linq;
using static CodingTestProj.Program;
using System.Text;

///*
// * Difficulty : 
// * URL : https://www.acmicpc.net/problem/2003
//  * Time : 
// */

namespace CodingTestProj
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solu = new Solution();
            solu.solve();
        }
    }

    public class Solution
    {
        int _n;
        int _m;

        int _left;
        int _right;

        int[] _arr;
        public void solve()
        {
            string[] input = Console.ReadLine().Split(' ');
            _n = int.Parse(input[0]);
            _m = int.Parse(input[1]);

            _arr = new int[_n];

            //Array.Sort(_arr);

            input = Console.ReadLine().Split(' ');

            for (int i = 0; i < input.Length; i++)
                _arr[i] = int.Parse(input[i]);

            _left = 0;
            _right = _arr.Length - 1;

            int _rightMax = _arr.Length -1 ;

            int _StandardLeft = 0;
            int _StandardRight = 0;

            int _addLeft = 0;
            int _addRight = 0;

            int _ret = 0;

            while( _left <= (_rightMax * 0.5))
            {
                _StandardLeft = _left;
                _StandardRight= _right;

                _addLeft = 0;
                _addRight = 0;

                bool _isSuccess = false;

                while (_StandardLeft <= (_rightMax* 0.5))
                {
                    _addLeft += _arr[_StandardLeft];

                    if (_addLeft == _m)
                    {
                        ++_ret;
                        _isSuccess = true;
                        break;
                    }
                    else if (_addLeft > _m)
                        break;
                    else
                        ++_StandardLeft;
                }

                if (_isSuccess && _StandardLeft == _StandardRight)
                {
                    ++_left;
                    --_right;
                    continue;
                }

                while (_StandardRight >= (_rightMax * 0.5))
                {
                    _addRight += _arr[_StandardRight];

                    if (_addRight == _m)
                    {
                        ++_ret;
                        break;
                    }
                    else if (_addRight > _m)
                        break;
                    else
                        --_StandardRight;
                }

                ++_left;
                --_right;
            }

            Console.WriteLine(_ret);
        }
    }
}

코드 결과

** 질문 게시판의 반례를 모두 통과하였는데 통과하지 못해서 다시 풀 예정이다.