코딩테스트 준비 - 두 수의 합

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

• 응시 사이트 : BOJ

• 문제 : 3273.두 수의 합

• 사용언어 : C#

• 난이도 : Milddle

• 풀이시간 : 20m

• 유형 : 투 포인터

문제

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

예제 입력 1 복사

9
5 12 7 10 9 1 2 3 11
13

예제 출력 1 복사

3

문제 풀이 접근

이 문제는 투 포인터로 해결할 수 있다.
정렬을 해도 그만, 안해도 그만이지만, 값을 비교해서 인덱스를 올리고 내리는 과정이 필요해 나는 정렬하여 풀이를 했다.

아직 투 포인터 문제 관련해 반복 조건식에 조금 익숙치 않아 시간이 걸렸는데,
조건식을
while(_left < (_maxRight 0.5) && right >= (maxRight 0.5))
이렇게 짤때도 있었고,
while(_left < (_right * 0.5))
이렇게 짤때도 있었다.

그러나, 단순하게 조건식을 while(left < right) 로 두면 되는 문제였다.
그 이유는 어차피 둘다 인덱스 용도이기도 하며, 양 끝단의 투포인터 인덱스가 중앙인덱스까지 루프한다는 조건 자체가 맞지 않았다.
arr[7] 배열 0 1 2 3 4 5 6 이 있으면 left가 1 right 가 2 가 온 뒤에 left 가 1 증가해서 끝나는 경우가 있을 것이고 배열의 값 상황에 따라 끝나는 지점을 매번 바뀔 수 있다.

그 점을 항상 생각하면서 투포인터 문제를 접근해야할 것으로 보인다.

작성 코드 (C#)

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

///*
// * Difficulty : Middle
// * URL : https://www.acmicpc.net/problem/3273
//  * Time : 20m
// */

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

    public class Solution
    {
        public int _ret;
        public int _n;
        public int _m;
        public int[] _arr;

        public int _left;
        public int _right;
        public void solve()
        {
            _n = int.Parse(Console.ReadLine());

            _arr = new int[_n];

            string[] _input = Console.ReadLine().Split(' ');

            for(int i =0; i < _n; ++i)
                _arr[i] = int.Parse(_input[i]);

            Array.Sort(_arr);

            _m  = int.Parse(Console.ReadLine());

            _left = 0;
            _right = _n - 1;

            while(_left < _right)
            {
                if(_arr[_left] + _arr[_right] == _m)
                {
                    ++_ret;
                    ++_left;
                    --_right;
                }
                else if (_arr[_left] + _arr[_right] < _m)
                {
                    ++_left;
                }
                else
                {
                    --_right;
                }
            }

            Console.WriteLine(_ret);
        }
    }
}

코드 결과