코딩테스트 준비

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

응시 사이트 : BOJ
문제 : 2776.암기왕
사용언어 : C#
난이도 : Easy
풀이시간 : 13m
유형 : 해쉬

문제

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.

입력

첫째 줄에 테스트케이스의 개수 T가 들어온다. 다음 줄에는 ‘수첩 1’에 적어 놓은 정수의 개수 N(1 ≤ N ≤ 1,000,000)이 입력으로 들어온다. 그 다음 줄에 ‘수첩 1’에 적혀 있는 정수들이 N개 들어온다. 그 다음 줄에는 ‘수첩 2’에 적어 놓은 정수의 개수 M(1 ≤ M ≤ 1,000,000) 이 주어지고, 다음 줄에 ‘수첩 2’에 적어 놓은 정수들이 입력으로 M개 들어온다. 모든 정수들의 범위는 int 로 한다.

출력

‘수첩2’에 적혀있는 M개의 숫자 순서대로, ‘수첩1’에 있으면 1을, 없으면 0을 출력한다.

예제 입력 1 복사

예제 출력 1 복사

문제 풀이 접근

이 문제는 설명이 길지만, 필요한 것만 추리면 단순히 배열 "수첩 1" 에 "수첩 2"의 원소가 있는지 하나씩 검사해달라. 있으면 1, 없으면 0 출력해달라는 것이다.

값을 찾는 부분에서 이진 탐색을 이용할 수 있지만, 이 문제를 더욱 쉽게 풀 수 있는 방법은 역시 HashMap을 사용하는 것이다.
이진탐색의 경우 O(LogN)이기도하고, 해쉬는 O(1)이기 때문에, 더 빠르기도 하다.

해쉬 자료구조를 이용한 탐색

값을 먼저, 모두 HashMap에 담는다.
그리고, 값이 존재하는지 확인한다.
이 두가지만 구현한다면 이번 문제는 쉽게 풀 수 있을 것이다.

** 문제에서 케이스도 여러개로 주는 것 같은데, tc 값 마다 넣는 stringbuilder를 굳이 초기화하여 없애지 않고, 모두 이어붙여서 출력하면 문제없이 풀린다.

작성 코드 (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/2776
//  * Time : 13m
// */

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

    public class Solution
    {
        public int _tc;
        public int _n;
        public int _m;

        public HashSet<int> _hs;
        public void solve(){

            // 수첩 1 => 하루동안 본 숫자
            // 수첩 2 => 봤다고 주장

            StringBuilder sb = new StringBuilder();
            _tc = int.Parse(Console.ReadLine());
            _hs = new HashSet<int>();

            while (_tc > 0)
            {
                _hs.Clear();
                //sb.Clear();
                _n = int.Parse(Console.ReadLine());
                string[] _input = Console.ReadLine().Split(' ');

                for(int i = 0; i < _input.Length; ++i)
                    _hs.Add(int.Parse(_input[i]));

                _m = int.Parse(Console.ReadLine());
                _input = Console.ReadLine().Split(' ');

                for (int i = 0; i < _input.Length; ++i)
                {
                    if (_hs.Contains(int.Parse(_input[i]))){
                        sb.AppendLine("1");
                    }
                    else{
                        sb.AppendLine("0");
                    }
                }

                --_tc;
            }
            Console.WriteLine(sb.ToString());
        }
    }
}

코드 결과

코딩테스트 준비 - 암기왕