[25192] 인사성 밝은 곰곰이

RudinP·2023년 4월 19일

BaekJoon

목록 보기

50/77

알고리즘 입문방 오픈 채팅방에서는 새로운 분들이 입장을 할 때마다 곰곰티콘을 사용해 인사를 한다. 이를 본 문자열 킬러 임스는 채팅방의 기록을 수집해 그 중 곰곰티콘이 사용된 횟수를 구해 보기로 했다.
ENTER는 새로운 사람이 채팅방에 입장했음을 나타낸다. 그 외는 채팅을 입력한 유저의 닉네임을 나타낸다. 닉네임은 숫자 또는 영문 대소문자로 구성되어 있다.
새로운 사람이 입장한 이후 처음 채팅을 입력하는 사람은 반드시 곰곰티콘으로 인사를 한다. 그 외의 기록은 곰곰티콘을 쓰지 않은 평범한 채팅 기록이다.
채팅 기록 중 곰곰티콘이 사용된 횟수를 구해보자!

입력

-첫 번째 줄에는 채팅방의 기록 수를 나타내는 정수
$N$ 이 주어진다. (
$1 \le N \le 100\,000$ )
두 번째 줄부터
$N$ 개의 줄에 걸쳐 새로운 사람의 입장을 나타내는 ENTER, 혹은 채팅을 입력한 유저의 닉네임이 문자열로 주어진다. (문자열길이
$1 \le \texttt{문자열 길이} \le 20$ )
첫 번째 주어지는 문자열은 무조건 ENTER이다.

출력

채팅 기록 중 곰곰티콘이 사용된 횟수를 출력하시오.

생각

ENTER이 입력되는 것이 기준이다.
즉, 같은 사람이 두번 말했어도, ENTER이 그 사이에 있다면 둘 다 곰곰티콘을 사용한것이다.
리스트에 계속 이름을 추가하되, ENTER 이 입력되면 이 리스트를 초기화해준다.
이후 리스트의 원소 개수를 출력한다.

처음 코드

namespace SongE
{
    public class Program
    {
        static void Main(string[] args)
        {
            using var input = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            int intInput() => int.Parse(input.ReadLine());
            //int[] intsInput() => Array.ConvertAll(input.ReadLine().Split(), s => int.Parse(s));
            
            int n = intInput();
            List<string> list = new List<string>();

            int count = 0;

            for(int i = 0; i < n; i++)
            {
                string s = input.ReadLine();

                if (s.Equals("ENTER"))
                {
                    count += list.Count;
                    list.Clear();
                    continue;
                }

                if (list.Contains(s)) continue;
                else list.Add(s);
            }

            count += list.Count;

            print.WriteLine(count);
            
        }
    }
}

시간초과

두번째 코드

namespace SongE
{
    public class Program
    {
        static void Main(string[] args)
        {
            using var input = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            int intInput() => int.Parse(input.ReadLine());
            //int[] intsInput() => Array.ConvertAll(input.ReadLine().Split(), s => int.Parse(s));
            
            int n = intInput();
            List<string> list = new List<string>();

            int count = 0;

            for(int i = 0; i < n; i++)
            {
                string s = input.ReadLine();

                if (s.Equals("ENTER"))
                {
                    list.Clear();
                    continue;
                }

                if (list.Contains(s)) continue;
                else 
                {
                    list.Add(s); 
                    count++; 
                }
            }
            print.WriteLine(count);
            
        }
    }
}

시간초과..
다른사람들은 이렇게 해서 냈던데
이게 C#...?!

찾아보니까 Clear()가 시간복잡도가 O(n)이라고 한다.
걍 새로 뽑자^^

세번째 코드

namespace SongE
{
    public class Program
    {
        static void Main(string[] args)
        {
            using var input = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            int intInput() => int.Parse(input.ReadLine());
            //int[] intsInput() => Array.ConvertAll(input.ReadLine().Split(), s => int.Parse(s));
            
            int n = intInput();
            List<string> list = new List<string>();

            int count = 0;

            for(int i = 0; i < n; i++)
            {
                string s = input.ReadLine();

                if (s.Equals("ENTER"))
                {
                    list = new List<string>();
                    continue;
                }

                if (list.Contains(s)) continue;
                else 
                {
                    list.Add(s); 
                    count++; 
                }
            }
            print.WriteLine(count);
            
        }
    }
}

또 시간초과임.
찾아보니까 리스트를 쓴 문제였다...
중복 찾는 거에는 HashSet가 적합하다고 한다.

마지막 코드

namespace SongE
{
    public class Program
    {
        static void Main(string[] args)
        {
            using var input = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            int intInput() => int.Parse(input.ReadLine());
            //int[] intsInput() => Array.ConvertAll(input.ReadLine().Split(), s => int.Parse(s));
            
            int n = intInput();
            HashSet<string> list = new();

            int count = 0;

            for(int i = 0; i < n; i++)
            {
                string s = input.ReadLine();

                if (s.Equals("ENTER"))
                {
                    list.Clear();
                    continue;
                }

                if (list.Contains(s)) continue;
                else 
                {
                    list.Add(s); 
                    count++; 
                }
            }
            print.WriteLine(count);
            
        }
    }
}