글 읽기 - [C#] 시간초과 이유를 모르겠습니다.

paraworld 3년 전 0

구현은 된듯한데, 시간초과가 나네요.

앨범 이름을 key로 했고 value에는 사진들 목록, 하위 앨범들 목록을 담았습니다.

public class Drive
    {
        public Dictionary<string, (HashSet<string> photos, Dictionary<string, Drive> albums)> path = new Dictionary<string, (HashSet<string>, Dictionary<string, Drive>)>(); 
    }

현재 보고 있는 앨범은 스택을 이용해 처리했습니다.

static Stack<(string albumName, Drive drive)> currentPath = new Stack<(string albumName, Drive drive)>();

시간초과가 의심되는 부분은 String 비교가 많다는 거랑 사전순으로 정렬하는 과정에서 시간을 잡아먹을 것 같은데 확실하지도 않고, 해결 방안도 모르겠습니다.

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

// CapitalLetters for class names and methods, camelCase for variable names.
// Write your code clearly enough so that it doesn't need to be commented, or at least, so that it rarely needs to be commented.

namespace Testpad
{
    public class BaekJoon20541
    {
        static Stack<(string albumName, Drive drive)> currentPath = new Stack<(string albumName, Drive drive)>(); // 현재 앨범 경로

        static void Main()
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
            Drive drive = new Drive();
            drive.path.Add("album", (new HashSet<string>(), new Dictionary<string, Drive>()));
            currentPath.Push(("album", drive));

            int n = int.Parse(sr.ReadLine()); // 실행할 명령어의 수
            for (int i = 0; i < n; i++)
            {
                string[] input = sr.ReadLine().Split(' '); // 주어지는 명령어

                switch (input[0]) // 명령어 실행
                {
                    case "mkalb":
                        if (Mkalb(input[1], currentPath.Peek().drive) == false)
                        {
                            sw.WriteLine("duplicated album name");
                        }
                        break;

                    case "rmalb":
                        var result = Rmalb(input[1], currentPath.Peek().drive);
                        sw.WriteLine(result.removedAlbumCount + " " + result.removedPhotoCount);
                        break;

                    case "insert":
                        if (Insert(input[1], currentPath.Peek().drive) == false)
                        {
                            sw.WriteLine("duplicated photo name");
                        }
                        break;

                    case "delete":
                        sw.WriteLine(Delete(input[1], currentPath.Peek().drive));
                        break;

                    case "ca":
                        sw.WriteLine(Ca(input[1], currentPath.Peek().drive));
                        break;

                    default:
                        throw new Exception("Invalid order");
                }
            }

            sr.Close();
            sw.Close();
        }
        
        static bool Mkalb(string s, Drive currentDrive) // 앨범 생성, 실패할 경우 false 반환
        {
            if (currentDrive.path[currentPath.Peek().albumName].albums.ContainsKey(s) == true)
            {
                return false;
            }

            currentDrive.path[currentPath.Peek().albumName].albums.Add(s, new Drive());
            currentDrive.path[currentPath.Peek().albumName].albums[s].path.Add(s, (new HashSet<string>(), new Dictionary<string, Drive>()));
            return true;
        }

        static (int removedAlbumCount, int removedPhotoCount) Rmalb(string s, Drive currentDrive) // 앨범 삭제
        {
            int removedAlbumCount = 0, removedPhotoCount = 0; // 삭제한 앨범과 사진의 수

            switch (s)
            {
                case "-1": // 현재 앨범에 속해있는 앨범이 존재한다면, 이름이 사전순으로 가장 빠른 앨범을 삭제
                    if (currentDrive.path[currentPath.Peek().albumName].albums.Count > 0)
                    {
                        var temp = currentDrive.path[currentPath.Peek().albumName].albums.OrderBy(s1 => s1.Key).ToArray();
                        removedPhotoCount += currentDrive.path[currentPath.Peek().albumName].albums[temp[0].Key].path[temp[0].Key].photos.Count;
                        currentDrive.path[currentPath.Peek().albumName].albums[temp[0].Key].path[temp[0].Key].photos.Clear();

                        var result = RmalbBFS(temp[0].Key, currentDrive);
                        removedAlbumCount += result.removedAlbumCount;
                        removedPhotoCount += result.removedPhotoCount;
                        currentDrive.path[currentPath.Peek().albumName].albums.Remove(temp[0].Key);
                    }
                    break;

                case "0": // 현재 앨범에 속해있는 모든 앨범을 삭제
                    if (currentDrive.path[currentPath.Peek().albumName].albums.Count > 0)
                    {
                        foreach (var item in currentDrive.path[currentPath.Peek().albumName].albums)
                        {
                            removedPhotoCount += item.Value.path[item.Key].photos.Count;
                            item.Value.path[item.Key].photos.Clear();

                            var result = RmalbBFS(item.Key, currentDrive);
                            removedAlbumCount += result.removedAlbumCount;
                            removedPhotoCount += result.removedPhotoCount;                            
                        }

                        currentDrive.path[currentPath.Peek().albumName].albums.Clear();
                    }
                    break;

                case "1":
                    if (currentDrive.path[currentPath.Peek().albumName].albums.Count > 0)
                    {
                        var temp = currentDrive.path[currentPath.Peek().albumName].albums.OrderByDescending(s1 => s1.Key).ToArray();
                        removedPhotoCount += currentDrive.path[currentPath.Peek().albumName].albums[temp[0].Key].path[temp[0].Key].photos.Count;
                        currentDrive.path[currentPath.Peek().albumName].albums[temp[0].Key].path[temp[0].Key].photos.Clear();

                        var result = RmalbBFS(temp[0].Key, currentDrive);
                        removedAlbumCount += result.removedAlbumCount;
                        removedPhotoCount += result.removedPhotoCount;
                        currentDrive.path[currentPath.Peek().albumName].albums.Remove(temp[0].Key);
                    }
                    break;

                default:
                    if (currentDrive.path[currentPath.Peek().albumName].albums.Count > 0)
                    {
                        if (currentDrive.path[currentPath.Peek().albumName].albums.ContainsKey(s) == true)
                        {
                            removedPhotoCount += currentDrive.path[currentPath.Peek().albumName].albums[s].path[s].photos.Count;
                            currentDrive.path[currentPath.Peek().albumName].albums[s].path[s].photos.Clear();

                            var result = RmalbBFS(s, currentDrive);
                            removedAlbumCount += result.removedAlbumCount;
                            removedPhotoCount += result.removedPhotoCount;
                            currentDrive.path[currentPath.Peek().albumName].albums.Remove(s);
                        }
                    }
                    break;
            }

            return (removedAlbumCount, removedPhotoCount);
        }

        static bool Insert(string s, Drive currentDrive) // 사진 삽입, 실패할 경우 false 반환
        {
            if (currentDrive.path[currentPath.Peek().albumName].photos.Contains(s) == true)
            {
                return false;
            }

            currentDrive.path[currentPath.Peek().albumName].photos.Add(s);
            return true;
        }

        static int Delete(string s, Drive currentDrive)
        {
            int removedPhotoCount = 0; // 삭제한 사진의 수

            switch (s)
            {
                case "-1":
                    if (currentDrive.path[currentPath.Peek().albumName].photos.Count > 0)
                    {
                        var temp = currentDrive.path[currentPath.Peek().albumName].photos.OrderBy(s1 => s1).ToArray();
                        currentDrive.path[currentPath.Peek().albumName].photos.Remove(temp[0]);
                        removedPhotoCount++;
                    }
                    break;

                case "0":
                    removedPhotoCount += currentDrive.path[currentPath.Peek().albumName].photos.Count;
                    currentDrive.path[currentPath.Peek().albumName].photos.Clear();
                    break;

                case "1":
                    if (currentDrive.path[currentPath.Peek().albumName].photos.Count > 0)
                    {
                        var temp = currentDrive.path[currentPath.Peek().albumName].photos.OrderBy(s1 => s1).ToArray();
                        currentDrive.path[currentPath.Peek().albumName].photos.Remove(temp[temp.Length - 1]);
                        removedPhotoCount++;
                    }
                    break;

                default:
                    if (currentDrive.path[currentPath.Peek().albumName].photos.Contains(s) == true)
                    {
                        currentDrive.path[currentPath.Peek().albumName].photos.Remove(s);
                        removedPhotoCount++;
                    }
                    break;
            }

            return removedPhotoCount;
        }

        static string Ca(string s, Drive currentDrive) // 보고 있는 앨범 이동
        {
            switch (s)
            {
                case "..":
                    if (currentPath.Count > 1)
                    {
                        currentPath.Pop();
                    }
                    break;

                case "/":
                    while (currentPath.Count > 1)
                    {
                        currentPath.Pop();
                    }
                    break;

                default:
                    var temp = currentPath.Peek().albumName;
                    if (currentDrive.path[temp].albums.ContainsKey(s) == true)
                    {
                        currentPath.Push((s, currentDrive.path[temp].albums[s]));
                    }
                    break;
            }

            return currentPath.Peek().albumName;
        }

        static (int removedAlbumCount, int removedPhotoCount) RmalbBFS(string s, Drive currentDrive)
        {
            int removedAlbumCount = 0, removedPhotoCount = 0;

            Queue<Drive> tempPath = new Queue<Drive>();
            tempPath.Enqueue(currentDrive.path[currentPath.Peek().albumName].albums[s]);

            while (tempPath.Count > 0)
            {
                int thisTime = tempPath.Count;
                removedAlbumCount += tempPath.Count;
                for (int i = 0; i < thisTime; i++)
                {
                    var thisOne = tempPath.Dequeue();
                    foreach (var item1 in thisOne.path)
                    {
                        removedPhotoCount += item1.Value.photos.Count;
                        item1.Value.photos.Clear();

                        foreach (var item2 in item1.Value.albums)
                        {
                            tempPath.Enqueue(item2.Value);
                        }

                        item1.Value.albums.Clear();
                    }
                }
            }

            return (removedAlbumCount, removedPhotoCount);
        }
    }

    public class Drive
    {
        public Dictionary<string, (HashSet<string> photos, Dictionary<string, Drive> albums)> path = new Dictionary<string, (HashSet<string>, Dictionary<string, Drive>)>(); 
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C#] 시간초과 이유를 모르겠습니다.

paraworld 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말