백준 C# - 1406 +) 문제 설명,풀이

계속 시간초과가 나와서 열받은 문제

 

시도 풀이 방법

01 String

첫번째로 StringBuilder로 풀었는데 금방 풀려서 신나게 제출했다. 근데 계속 시간초과가 나와서 뭐가 잘못 됐나 봤더니

Stack 2개 or LinkedList로 풀어야 한다는 정보를 얻었다.

---

02 LinkedList

코드도 짧게 잘 짠 것 같은데 계속 2%가 되면 틀렸습니다가 나왔다. 하루 종일 반례를 못찾다가 질문 게시판에 반례하나를 보고 이마를 탁 쳤다.

if (cursor.Value != sb.First.Value && cursor.Previous != null)

틀렸습니다의 원인은 LinkedList첫번째 Value와 cursor.Value가 같아야 되는 조건을 사용한 것이었다.

aaa
4
L
B
D
B

---

풀이

문제의 커서가 위치할 곳은 L+1만 잘 적용하면 금방 풀린다.

01 변수 설정

string s = Console.ReadLine();
int n = int.Parse(Console.ReadLine());
LinkedList<char> sb = new LinkedList<char>(s);
sb.AddLast(' '); 
LinkedListNode<char> cursor = sb.Last;

마지막에 공백란 추가하는 것이 몹시몹시 중요하다

sb.AddLast(' ');

---

02 L

cursor 왼쪽으로 옮기기

if (cursor.Previous != null)
    cursor = cursor.Previous;

03 D

cursor 오른쪽으로 옮기기

if (cursor.Next != null)
    cursor = cursor.Next;

04 B

cursor가 맨 앞이 아닌 경우 왼쪽에 있는 거 삭제

if (cursor.Previous != null)
{
    sb.Remove(cursor.Previous);
}

05 P

커서 왼쪽에 문자 추가하기

char charToAdd = char.Parse(token[1]);                     
sb.AddBefore(cursor, charToAdd);

---

전체 코드

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

namespace baek2
{
    class Class1
    {
        class Program
        {
           static void Main(string[] args)
           {
                string s = Console.ReadLine();
                int n = int.Parse(Console.ReadLine());
                LinkedList<char> sb = new LinkedList<char>(s);
                sb.AddLast(' ');
                LinkedListNode<char> cursor = sb.Last;
                
                for (int i = 0; i < n; i++)
                {
                    string m = Console.ReadLine();
                    string[] token = m.Split(' ');
                    string a = token[0];

                    switch (a)
                    {
                        case "L":
                            { 
                                if (cursor.Previous != null)
                                    cursor = cursor.Previous;
                          
                                break;
                            }
                        case "D":
                            {
                                if (cursor.Next != null)
                                    cursor = cursor.Next;
                             
                                break;
                            }
                        case "B":
                            {
                                if (cursor.Previous != null)
                                {
                                    sb.Remove(cursor.Previous);
                                }
                               
                                break;
                            }
                        case "P":
                            {
                                char charToAdd = char.Parse(token[1]);                     
                                sb.AddBefore(cursor, charToAdd);                       
                                break;
                            }
                    }
                }
                sb.RemoveLast();
                StringBuilder result = new StringBuilder();
                foreach (var x in sb)
                {
                    result.Append(x);
                }
                Console.WriteLine(result.ToString());
            }
        }
    }
}