[C#] 1620번: 나는야 포켓몬 마스터 이다솜

목차

---

백준 단계별로 풀어보기

25.10.31

14단계: 집합과 맵

1620번: 나는야 포켓몬 마스터 이다솜

문제 링크 : https://www.acmicpc.net/problem/1620

 

문제를 풀기 위해 알아야 할 개념

>> Dictionary<Key, Value>

: 숫자 index 대신 Key를 Value와 함께 저장하는 Collection이다.

 

- 특징

• Key를 통해 Value 값에 빠르게 접근할 수 있다. --> O(1)의 시간복잡도를 가진다.
• Value는 중복될 수 있지만 Key는 중복될 수 없다.

 

- 주요 메서드

• Add(Key, Value) : Dictionary에 Key와 Value를 저장한다.
• Remove(Key) : Dictionary에 있는 Key를 제거한다. 따라서 해당 Key에 있는 Value 값도 전부 제거된다.
• ContainsKey(Key) : Dictionary에 해당 Key가 있는지 확인한다. 해당 Key가 있다면 true, 없다면 false를 반환한다.
• ContainsValue(Value) : Dictionary에 해당 Value가 있는지 확인한다. 해당 Value가 있다면 true, 없다면 false를 반환한다. --> 모든 Key를 순회하며 Value가 있는지 확인하기 때문에 O(n)의 시간복잡도를 갖는다.
• TryGetValue(Key, out Value) : Dictionary에 해당 Key가 있는지 확인하고 그 값을 반환한다. 해당 Key가 있다면 true를 반환하면서 'Value' 로 값을 사용할 수 있고, 없다면 false를 반환한다.

 

※ 공식 문서 - Dictionary<TKey, TValue> 클래스

Dictionary<TKey,TValue> 클래스 (System.Collections.Generic)

 

문제 풀이

: 오박사가 시험을 낼 때, 포켓몬의 번호를 줄 수도 있고 포켓몬의 이름을 줄 수도 있기 때문에 번호와 이름을 묶어서 기억할 필요가 있다. 따라서 Dictionary 를 사용하는 것이 적절하다.

└ 오답노트

>> 첫 오답

: Dictionary에 번호와 이름 모두 string 으로 저장한 뒤, 주어진 시험의 입력값이 번호라면 그에 해당하는 이름을, 이름이라면 그에 해당하는 키를 StringBuidler에 담아 출력한다. --> 시간 초과로 실패했다.

→ ContainsValue() 함수와 FirstOrDefault() 함수를 호출하면 내부적으로 모든 항목을 순회하기 때문에 각각 시간복잡도가 O(n)인 것이 문제였다.

 

※ 참고 개념 - FirstOrDefault()

: LINQ 함수로, 조건에 충족하는 첫 번째 요소를 반환하거나 이러한 요소가 없다면 지정된 기본값을 반환한다.

--> FirstOrDefault(x => x.Value == quiz) : (Key, Value) 쌍을 앞에서부터 하나씩 검사해서 Value 값이 'quiz'인 조건을 처음으로 만족하는 (Key, Value) 쌍을 반환한다. 못 찾았을 경우 그 타입의 기본값을 반환하는데, 여기서는 둘다 string 값이므로 (null, null)을 반환한다.

--> (Key, Value).Key : 해당 Key를 반환한다.

 

- 공식 문서 - FirstOrDefault()

Enumerable.FirstOrDefault 메서드 (System.Linq)

 

- 작성한 코드

using System.IO;
using System.Text;

class Backjoon
{
    static void Main(string[] args)
    {
        using var sr = new StreamReader(Console.OpenStandardInput());
        using var sw = new StreamWriter(Console.OpenStandardOutput());
        StringBuilder sb = new StringBuilder();

        string[] input = sr.ReadLine().Split();
        int n = int.Parse(input[0]);
        int m = int.Parse(input[1]);
        Dictionary<string, string> dict = new Dictionary<string, string>();

        for (int i = 1; i <= n; i++)
        {
            string temp = i.ToString();
            dict.Add(temp, sr.ReadLine());
        }

        for (int i = 0; i < m; i++)
        {
            string quiz = sr.ReadLine();

            if (dict.TryGetValue(quiz, out var value))
                sb.AppendLine(value);
            else if (dict.ContainsValue(quiz))
                sb.AppendLine(dict.FirstOrDefault(x => x.Value == quiz).Key);
        }
        sw.Write(sb.ToString());
    }
}

 

>> 최종 수정

: Dictionary에서 Key 값으로 찾는 것은 시간복잡도가 O(1)로 빠르므로, Dictionary를 두개 만들어서 하나는 번호를 Key 값으로, 하나는 이름을 Key값으로 저장하도록 만들고 각각 Key 값으로 Value를 찾아 반환하도록 만든다.

1. StreamReader로 입력값을 받아 각각 int값으로 변환하여 포켓몬의 개수를 담을 변수 n 과 문제의 개수를 담을 변수 m 에 담는다.
2. 포켓몬의 번호를 Key, 이름을 Value로 받을 Dictionary 'nameDict' 와 포켓몬의 이름을 Key, 번호를 Value로 받을 Dictionary 'numDict' 를 초기화 한다.
3. for 반복문을 통해 도감에 들어갈 포켓몬의 이름을 입력받아 번호와 이름을 각각의 Dictionary에 추가한다.
4. for 반복문을 통해 문제를 입력받아 int로 변환하려 시도하고, 변환된다면 입력값이 번호이므로 StringBuilder에 번호에 해당하는 포켓몬의 이름을 담고, 변환되지 않는다면 입력값이 이름이므로 StringBuilder에 이름에 해당하는 포켓몬의 번호를 담는다.
5. StringBuilder에 담은 내용을 출력한다.

 

정답 코드

using System.IO;
using System.Text;

class Backjoon
{
    static void Main(string[] args)
    {
        using var sr = new StreamReader(Console.OpenStandardInput());
        using var sw = new StreamWriter(Console.OpenStandardOutput());
        StringBuilder sb = new StringBuilder();

        string[] input = sr.ReadLine().Split();
        int n = int.Parse(input[0]);
        int m = int.Parse(input[1]);
        Dictionary<int, string> nameDict = new Dictionary<int, string>();
        Dictionary<string, int> numDict = new Dictionary<string, int>();

        for (int i = 1; i <= n; i++)
        {
            string name = sr.ReadLine();
            nameDict.Add(i, name);
            numDict.Add(name, i);
        }

        for (int i = 0; i < m; i++)
        {
            string quiz = sr.ReadLine();

            if (int.TryParse(quiz, out int num))
                sb.AppendLine(nameDict[num]);
            else
                sb.AppendLine(numDict[quiz].ToString());
        }
        sw.Write(sb.ToString());
    }
}