코딩테스트 준비 - Pair Sum

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

• 응시 사이트 : BOJ

• 문제 : 9728.Pair Sum

• 사용언어 : C#

• 난이도 : Easy

• 풀이시간 : 13m

• 유형 : 투 포인터, 해시

문제

You are given an integer array of size N and an integer M. This array has (N*(N-1))/2 different pairs. You need to calculate how many of those pairs have the sum equal to M. For example, if the array is {1,2,3,4} and M is 5, then there are exactly 2 pairs {1,4} and {2,3} whose sum is equal to M. 

입력

The first line has a positive integer T, T <= 100,000, denoting the number of test cases. This is followed by each test case per line. 

Each test case consists of two lines. The first line contains 2 integers N and M separated by a single space. N is between 2 and 20,000 inclusive. The second line consists of the N integers separated by a single space, denoting the values of the given array. All the numbers in the array are between 1 and 1,000,000,000 inclusive. They are distinct and sorted in increasing order.

출력

For each test case, the output contains a line in the format Case #x: R, where x is the case number (starting from 1) and R is the number of pairs whose sum is exactly the given M. 

예제 입력 1 복사

5
8 100
19 25 32 48 52 68 75 81
8 100
19 28 31 49 51 61 72 81
8 100
16 22 38 46 58 62 73 81
8 100
13 21 32 48 52 67 78 87
8 100
13 24 34 43 57 61 76 81

예제 출력 1 복사

Case #1: 4
Case #2: 3
Case #3: 1
Case #4: 2
Case #5: 2

문제 풀이 접근

문제가 영어라 이해를 하기 쉽지않은데, 문제 자체의 조건은 단순하다.

1. Arr Size 를 N으로 주겠다. 그리고 정수하나를 M으로 주겠다.

2. 배열 내에서 두개의 페어(원소)의 합이 M와 동일한 값을 갖는 수의 갯수를 찾아라.

3. 그리고 출력처럼 양식 맞춰서 출력하라.

크게 투포인터 유형의 전형적인 문제라서 문제 풀이 전략을 간단히 적어본다면,

1. Left = 0. Right = _arr.Length -1 로 양 끝점에 인덱스를 배치한다.

2. while ( Left < Right ) 의 조건을 사용하여 Left가 Right 에 도달하면 루프 종료하도록 한다.

**인덱스를 연산하는 것 때문에, 보통 정렬된 배열에서 투포인터 알고리즘을 사용한다.

작성 코드 (C#)

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

///*
// * Difficulty : Easy
// * URL : https://www.acmicpc.net/problem/9728
//  * Time : 13m
// */

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

    public class Solution
    {
        int _n; // 배열 사이즈
        int _m; // 정수 M

        int _loopCnt;
        int[] _arr;
        Dictionary<int, int> _dic;

        public void solve()
        {
            _dic = new Dictionary<int, int>();
            _loopCnt = int.Parse(Console.ReadLine());

            for (int i = 0; i < _loopCnt; ++i)
            {
                string[] _input = Console.ReadLine().Split(' ');
                _n = int.Parse(_input[0]);
                _m = int.Parse(_input[1]);

                _arr = new int[_n];
                _input = Console.ReadLine().Split(' ');

                for (int j = 0; j < _input.Length; ++j)
                    _arr[j] = int.Parse(_input[j]);
                // 데이터 설정

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

                while (_left < _right)
                {
                    if (_arr[_left] + _arr[_right] == _m)
                    {
                        if (_dic.ContainsKey(i) == false)
                            _dic.Add(i, 0);

                        _dic[i]++;
                        ++_left;
                    }
                    else if (_arr[_left] + _arr[_right] < _m)
                    {
                        ++_left;
                    }
                    else
                    {
                        --_right;
                    }
                }
            }

            foreach (var pair in _dic)
            {
                int key = pair.Key;
                int value = pair.Value;

                Console.WriteLine($"Case #{key + 1}: {value}");
            }
        }
    }
}

코드 결과