[BOJ] 1940번 주몽 C# 사용 풀이 (두포인터 알고리즘 )

 

코드

using System;
using System.IO;

namespace BOJ
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            //int[] AB = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);

            int N = int.Parse(sr.ReadLine()); //재료의 갯수 6
            int M = int.Parse(sr.ReadLine()); //타겟 넘버 9
            //2 7 4 1 5 3
            int[] nums = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
            Array.Sort(nums);

            int i = 0;
            int j = N - 1;
            int cnt = 0;

            while (i < j)
            {                
                if (nums[i] + nums[j] == M)
                {
                    cnt++;
                    i++;
                    j--;
                }
                if (nums[i] + nums[j] > M)
                {
                    j--;
                }
                if (nums[i] + nums[j] < M)
                {
                    i++;
                }
            }

            sw.WriteLine(cnt);

            sr.Close();
            sw.Close();
        }
    }
}

결과창

 

두포인터 알고리즘을 이용한 문제

배열을 정렬하고 해당 배열의 시작과 끝 인덱스부터 탐색하여 M (타겟Num) 이 나오면 카운트를 증가시키는 방법으로 

만약 M이 i인덱스와 j 인덱스를 더 한 값보다 작다면 i를 증가시키고 반대로 크다면 j를 증가시는 방법으로 탐색하면 된다.

또 만약 타겟Num과 같은 숫자가 된다면 둘중 하나만 줄이거나 늘린다고 타겟Num이 나올수는 없으니 둘다 감소,증가 시켜주면 된다.

 

두포인터도 상황에 따라 포인터의 위치를 다르게 해야하는 데 이걸 이런상황에서 이렇게 저런 상황에선 저렇게 등등 사용 방법을 아직 정확하게 파악하지 못한듯 하다 ㅠㅠ

 

좀더 문제를 풀어봐야겠다...