[코딩테스트] BOJ 3273 - 두 수의 합 (성공)

 

https://www.acmicpc.net/problem/3273

 

 

문제

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

 

 

풀이

배열을 활용해서 풀어봤다. 

 

 

내 코드 

internal class BOJ3273_두_수의_합
{
    static void Main(string[] args)
    {
        // 내 풀이
        // 9
        int n = int.Parse(Console.ReadLine());

        // 5 12 7 10 9 1 2 3 11
        string[] strArr = Console.ReadLine().Split(" ");

        // 13
        int x = int.Parse(Console.ReadLine());

        int[] arr = new int[2000000];
        int index = 0;
        int index2 = 0;
        int answer = 0;
        for (int i = 0; i < n; i++)
        {
            index = int.Parse(strArr[i]);
            index2 = Math.Abs(index - x);
            if (index != index2 && index + index2 == x && arr[index2] == 1)
            {
                answer += 1;
            }

            arr[index] += 1;
        }

        Console.WriteLine(answer);
    }
}

 

 

다른 사람 풀이

나는 int 배열로 숫자가 있는지 없는지를 배열에 기록했다. 이 풀이는 bool 배열로 숫자가 있는지 없는지를 배열에 기록하고 있다. 

 

internal class BOJ3273_두_수의_합
{
    static void Main(string[] args)
    {
        int[] a = new int[1000001];
        bool[] occur = new bool[2000001];
        int answer = 0;


        int n = int.Parse(Console.ReadLine());
        string[] input = Console.ReadLine().Split(" ");
        for(int i = 0; i < n; i++)
        {
            a[i] = int.Parse(input[i]);
        }
        int x = int.Parse(Console.ReadLine());


        for(int i = 0; i < n; i++)
        {
            if(x - a[i] > 0 && occur[x - a[i]])
            {
                answer += 1;
            }

            occur[a[i]] = true;
        }

        Console.WriteLine(answer);
    }
}

 

 

복습1 풀이 (5/5)

수열에서 ai + aj = x를 만족하는 (ai, aj) 쌍의 개수를 구해야 한다. 

 

예전에 이 문제를 어떻게 풀었는지 생각해봤다. 

등장 여부를 저장하는 bool배열을 만들어두고 수열에 있는 숫자를 하나씩 보면서 이전에 등장했던 수였는지 ai+aj=x를 만족했는지를 확인하며 문제를 풀었던 것 같았다. 

 

arr는 int형을 저장하는 수열 배열, flags는 수 등장 여부를 저장하는 bool 배열를 만들었다. 

 

코드를 짜기 전 시뮬레이션을 한번 생각해봤다. 

 

1. 13 - arr[0]가 등장한 적이 있는가? 

(arr[0] = ai, 13 - arr[0] = aj) 

 

2-1. 있다.

-> answer++, flags[ arr[0] ] = true 

 

2-2. 없다. 

-> flags[ arr[0] ] = true 

 

1~2과정을 arr배열(수열 배열) 끝까지 탐색하며 반복하면 되겠다. 

 

이대로 코드를 짜봤다. 

 

 

복습1 코드1 - 오답 

using System.Text;

namespace 배열_구현
{
    internal class BOJ3273_두_수의_합_복습1
    {
        static StreamReader sr = new StreamReader(Console.OpenStandardInput());
        static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
        static StringBuilder sb = new StringBuilder();

        static void Main(string[] args)
        {
            int answer = 0;

            int n = int.Parse(sr.ReadLine());

            // arr 초기화 
            string[] input1 = sr.ReadLine().Split(" ");
            int[] arr = new int[input1.Length];
            for(int i = 0; i < n; i++)
            {
                arr[i] = int.Parse(input1[i]);
            }

            bool[] flags = new bool[2500000];
            Array.Fill(flags, false);

            int x = int.Parse(sr.ReadLine());

            for(int i = 0; i < arr.Length; i++)
            {
                int ai = arr[i];
                int aj = x - ai;

                // ai + aj = x를 만족하는 aj가 있다면 
                if (flags[aj])
                {
                    answer++;
                    flags[ai] = true;
                }
                // ai + aj = x를 만족하는 aj가 없으면 
                else
                {
                    flags[ai] = true;
                }
            }

            sb.Append(answer);

            sw.WriteLine(sb.ToString());

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

 

BOJ가 서비스 종료해서 정답인지 아닌지는 알 수 없다. 

다만 이전 코드를 보니 거의 똑같은 코드가 있었다. 그 코드와 비교해보니 내 코드에서는 flags[aj]가 true인지만 체크하고 있다. 

이러면 x를 초과하는 수열의 수(aj)가 있는 경우를 처리해주지 못하므로 오답이 나올 것 같다. 

이 부분만 조건문에 추가해주자. 

 

 

복습1 코드2 - 정답

using System.Text;

namespace 배열_구현
{
    internal class BOJ3273_두_수의_합_복습1
    {
        static StreamReader sr = new StreamReader(Console.OpenStandardInput());
        static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
        static StringBuilder sb = new StringBuilder();

        static void Main(string[] args)
        {
            int answer = 0;

            int n = int.Parse(sr.ReadLine());

            // arr 초기화 
            string[] input1 = sr.ReadLine().Split(" ");
            int[] arr = new int[input1.Length];
            for(int i = 0; i < n; i++)
            {
                arr[i] = int.Parse(input1[i]);
            }

            bool[] flags = new bool[2500000];
            Array.Fill(flags, false);

            int x = int.Parse(sr.ReadLine());

            for(int i = 0; i < arr.Length; i++)
            {
                int ai = arr[i];
                int aj = x - ai;

                // ai + aj = x를 만족하는 aj가 있다면 
                if (aj > 0 && flags[aj])
                {
                    answer++;
                    flags[ai] = true;
                }
                // ai + aj = x를 만족하는 aj가 없으면 
                else
                {
                    flags[ai] = true;
                }
            }

            sb.Append(answer);

            sw.WriteLine(sb.ToString());

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