[C#] 백준 20920번 문제풀이

안녕하세요.

C#을 이용한 백준 20920번 '영단어 암기는 괴로워' 문제 풀이를 해보도록 하겠습니다.

해당 문제는 다음과 같은 3가지 우선순위에 따라 화은이가 외워야할 단어를 정렬하는 문제입니다.

 

- 자주 나오는 단어일수록 앞에 배치한다.

- 해당 단어의 길이가 길수록 앞에 배치한다.

- 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다

 

해당 문제를 풀기 위해 딕셔너리로 단어 글자와 글자가 나온 수를 키와 값으로 저장하는 방식을 사용하였는데 시간초과가 나버렸습니다. 입출력 시간을 최소로 단축하기 위해서 StringBuilder 를 사용하였습니다.

 

예제입력

7 4
apple
ant
sand
apple
append
sand
sand

 

예제출력

sand
apple
append

첫번째줄 입력에 N(단어의 개수) 과 M(최소 단어의 길이) 가 주어집니다.

이후에는 N에 따라 단어가 한줄에 하나씩 입력됩니다.

 

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

int[] nm = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
int n = nm[0];
int m = nm[1];

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

스트링리더와 라이터, 빌더를 선언해줍니다. 그리고 첫번째 입력으로 들어온 n,m을 변수로 나눠 저장해주고 딕셔너리 wordDict을 선언해줍니다. wordDict의 키는 string, 값은 int로 만들어주었습니다.

 

for (int i = 0; i < n; i++)
{
    string word = sr.ReadLine();

    if (word.Length >= m)
    {
        if (wordDict.ContainsKey(word))
            wordDict[word]++;
        else
            wordDict[word] = 1;
    }
}

단어를 정렬하기 전에 중복되는 단어는 wordDict에 넣지 않고 카운트를 올려주는 작업을 진행했습니다.

반복문을 단어의 개수만큼 돌려 단어 하나씩 받아오고, 받아온 단어가 wordDict에 존재하는지 검사한 후, 존재한다면 카운트를 올리고 만약 존재하지 않는다면 카운트를 1로 설정하고 wordDict에 추가합니다.

 

var wordList = wordDict.ToList();

wordList.Sort((a, b) =>
{
    int cmp = b.Value.CompareTo(a.Value); // 1. 자주 나오는 단어
    if (cmp != 0) return cmp;

    cmp = b.Key.Length.CompareTo(a.Key.Length); // 2. 길이 긴 단어
    if (cmp != 0) return cmp;

    return a.Key.CompareTo(b.Key); // 3. 사전 순
});

다음으로는 3가지 우선순위에 따라 정렬해주는 코드를 작성하였습니다.

우선 딕셔너리는 Sort(정렬) 기능을 지원하지 않기 때문에 리스트 배열로 변환해주었습니다. 이후 Sort 정렬을 사용하여 정렬코드를 작성하였습니다.

첫번째로 wordDict 에 저장해둔 값끼리 비교하여 정렬합니다. wordDict 값 부분에는 단어의 중복 개수가 저장되어있기 때문입니다.

두번째로는 단어의 길이를 비교해 정렬합니다. 단어는 wordDict의 키에 저장되어있기 때문에 Key.Length로 길이를 비교합니다.

마지막으로 사전순으로 정렬해주면 끝이 납니다.

 

foreach (var item in wordList)
{
    sb.AppendLine(item.Key);
}

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

빠른 출력을 위해 맨 처음 만들어두었던 스트링빌더에 정렬된 wordList(wordDict이 List로 변환되었음)를 순서대로 추가해줍니다.

이후 스트링라이터를 이용해 답을 출력해줍니다. 정답입니다 👍

 

전체코드

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

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

            int[] nm = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
            int n = nm[0];
            int m = nm[1];

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

            for (int i = 0; i < n; i++)
            {
                string word = sr.ReadLine();

                if (word.Length >= m)
                {
                    if (wordDict.ContainsKey(word))
                        wordDict[word]++;
                    else
                        wordDict[word] = 1;
                }
            }

            var wordList = wordDict.ToList();

            wordList.Sort((a, b) =>
            {
                int cmp = b.Value.CompareTo(a.Value); // 1. 자주 나오는 단어
                if (cmp != 0) return cmp;

                cmp = b.Key.Length.CompareTo(a.Key.Length); // 2. 길이 긴 단어
                if (cmp != 0) return cmp;

                return a.Key.CompareTo(b.Key); // 3. 사전 순
            });

            foreach (var item in wordList)
            {
                sb.AppendLine(item.Key);
            }

            sw.Write(sb.ToString());
            sw.Flush();
        }
    }
}