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

[ 문제 ]

안녕? 내 이름은 이다솜. 나의 꿈은 포켓몬 마스터야. 일단 포켓몬 마스터가 되기 위해선 포켓몬을 한 마리 잡아야겠지? 근처 숲으로 가야겠어.

 

- 이하 생략 -

 

오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네.

 

[ 코드 ]

1. 내 코드

using System.Text;

StreamReader sr = new (new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new (new BufferedStream(Console.OpenStandardOutput()));
StringBuilder sb = new StringBuilder();

string[] NM = sr.ReadLine().Split();
int n = int.Parse(NM[0]);
int m = int.Parse(NM[1]);

Dictionary<int, string> book = new Dictionary<int, string>();
Dictionary<string, int> reverseBook = new Dictionary<string, int>();

for (int i = 1; i <= n; i++)
{
    string name = sr.ReadLine();
    book[i] = name;
    reverseBook[name] = i;
}

for (int i = 0;i < m; i++)
{
    string name = sr.ReadLine();
    int num;
    
    if (int.TryParse(name, out num))
    {
        sb.AppendLine(book[num]);
    }
    else
    {
        sb.AppendLine($"{reverseBook[name]}");
    }
}

sw.Write( sb.ToString() );
sw.Flush();
sw.Close();
sr.Close();

 

2. 다른 사람 참고 코드

using System.Text;

StreamReader sr = new (new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new (new BufferedStream(Console.OpenStandardOutput()));
StringBuilder sb = new StringBuilder();

string[] NM = sr.ReadLine().Split();
int n = int.Parse(NM[0]);
int m = int.Parse(NM[1]);

Dictionary<string, int> book = new Dictionary<string, int>();
string[] reverseBook = new string[n + 1];

for (int i = 1; i <= n; i++)
{
    string name = sr.ReadLine();
    book[name] = i;
    reverseBook[i] = name;
}

for (int i = 0;i < m; i++)
{
    string name = sr.ReadLine();
    int num;
    
    if (int.TryParse(name, out num))
    {
        sb.AppendLine(reverseBook[num]);
    }
    else
    {
        sb.AppendLine($"{book[name]}");
    }
}

sw.Write( sb.ToString() );
sw.Flush();
sw.Close();
sr.Close();

 

- 딕셔너리 두개 쓰는것보단 이게 딕셔너리+배열이 빠르고 메모리도 덜 잡아먹습니다용

 

3. 시간 초과 코드

- 딕셔너리의 값을 튜플의 키로 받아오는 코드 중 FirstOrDefault 메서드는 선형탐색이라 오래 걸린다 합니다.

using System.Text;

StreamReader sr = new (new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new (new BufferedStream(Console.OpenStandardOutput()));
StringBuilder sb = new StringBuilder();

string[] NM = sr.ReadLine().Split();
int n = int.Parse(NM[0]);
int m = int.Parse(NM[1]);

Dictionary<int, string> book = new Dictionary<int, string>();

for (int i = 1; i <= n; i++)
{
    string name = sr.ReadLine();
    book[i] = name;
}

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

    if (int.TryParse(name, out num))
    {
        sb.AppendLine(book[num]);
    }
    else
    {
        var tuple = book.FirstOrDefault(x => x.Value == name);
        sb.AppendLine($"{tuple.Key}");
    }
}

sw.Write(sb.ToString());
sw.Flush();
sw.Close();
sr.Close();

 

[ 실행화면 ]

case: 1

---

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

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