[백준 - C#] 17219 비밀번호 찾기

문제링크

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

17219번: 비밀번호 찾기

 

문제

2019 HEPC - MAVEN League의 " 비밀번호 만들기"와 같은 방식으로 비밀번호를 만든 경민이는 한 가지 문제점을 발견하였다. 비밀번호가 랜덤으로 만들어져서 기억을 못 한다는 것이었다!

그래서 경민이는 메모장에 사이트의 주소와 비밀번호를 저장해두기로 했다. 하지만 컴맹인 경민이는 메모장에서 찾기 기능을 활용하지 못하고 직접 눈으로 사이트의 주소와 비밀번호를 찾았다. 메모장에 저장된 사이트의 수가 늘어나면서 경민이는 비밀번호를 찾는 일에 시간을 너무 많이 쓰게 되었다.

이를 딱하게 여긴 문석이는 경민이를 위해 메모장에서 비밀번호를 찾는 프로그램을 만들기로 결심하였다! 문석이를 도와 경민이의 메모장에서 비밀번호를 찾아주는 프로그램을 만들어보자.

조건

시간제한 : 5초 (추가 시간 없음)
메모리 제한 : 256 MB

입력

첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다.

두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번호가 공백으로 구분되어 주어진다. 사이트 주소는 알파벳 소문자, 알파벳 대문자, 대시('-'), 마침표('.')로 이루어져 있고, 중복되지 않는다. 비밀번호는 알파벳 대문자로만 이루어져 있다. 모두 길이는 최대 20자이다.

N+2번째 줄부터 M개의 줄에 걸쳐 비밀번호를 찾으려는 사이트 주소가 한줄에 하나씩 입력된다. 이때, 반드시 이미 저장된 사이트 주소가 입력된다.

출력

첫 번째 줄부터 M개의 줄에 걸쳐 비밀번호를 찾으려는 사이트 주소의 비밀번호를 차례대로 각 줄에 하나씩 출력한다.

 

문제풀이

사이트 주소와 비밀번호를 List에 튜플로 저장하였다가, 시간초과를 당하고 나서 c++에 맵과 관련된 게 머가 있을까 검색해보다가 key value 찾는 거면 Dictionary를 생각해내어서 한번 해보았습니다.

 

List로 비밀번호와 주소를 찾을 때 시간이 O(n)만큼 걸린다고 하고 Dictionary로 찾을 때는 O(1)만큼 걸린다고 하여 통과 한 것 같습니다.

 

아래에 리스트로 구현한 것과 Dictionary로 구현한 코드를 올려두었습니다.

 

C# 코드

static void Main(string[] args)
{
    StringBuilder builder = new StringBuilder();
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    string[] input = reader.ReadLine().Split();
    int n = int.Parse(input[0]); // 저장된 사이트의 주소
    int m = int.Parse(input[1]); // 비밀번호를 찾으려는 사이트 주소의 수
 
    // 리스트로 했을 때 82%에서 통과하지 못했습니다. ( 시간초과로 )
    //List<(string, string)> map = new List<(string, string)>();
    Dictionary<string, string> map = new Dictionary<string, string>();
 
    for (int i = 0; i < n; i++)
    {
        input = reader.ReadLine().Split();
        map.Add(input[0], input[1]);
    }
 
    string email;
    for (int j = 0; j < m; j++)
    {
        email = reader.ReadLine();
        // 리스트로 찾을 때
        //builder.Append($"{(map.Find(o => o.Item1 == email)).Item2}\n");
        builder.Append($"{map[email]}\n");
    }
 
    writer.WriteLine(builder);
 
    writer.Close();
    reader.Close();
}

 

정리

이번에 문제를 풀며 C# 제네릭 타입에 대해서 공부하고 정리할 필요가 있다고 생각을 하였습니다.

제네릭 타입에 대해서 정리가 끝난다면 각각 제네릭타입에 장단점 그리고 시간복잡도를 정리해봐야 할 것 같습니다.