20240308 TIL

Today I Learned :

 

프로그래머스 133502.

using System;
using System.Collections.Generic;
public class Solution {
    public int solution(int[] ingredient) {
        int answer = 0;
//         string s = String.Join("", ingredient);
//         while(true){
//             string temp = ReplaceFirst(s); //s.Replace("1231","");
//             //Console.WriteLine($"{s} / {temp}");
//             // Console.WriteLine(s);
//             if(temp != s) {
//                 // 변환됨
//                 s=temp;
//                 answer++;
//             }
//             else{
//                 break;
//             }
//         }

        Stack<int> stack = new Stack<int>();

        foreach(int item in ingredient) {
            stack.Push(item);
            if(stack.Count >= 4) {
                int fth = stack.Pop();
                int trd = stack.Pop();
                int snd = stack.Pop();
                int fst = stack.Pop();

                if(fst == 1 && snd == 2 && trd == 3 && fth == 1) {
                    answer++;
                } else {
                    stack.Push(fst);
                    stack.Push(snd);
                    stack.Push(trd);
                    stack.Push(fth);
                }
            }
        }

        return answer;
    }

    // public string ReplaceFirst(string text)
    // {
    //     int pos = text.IndexOf("1231");
    //     if (pos < 0)
    //     {
    //         return text;
    //     }
    //     return text.Substring(0, pos) + text.Substring(pos + 4);
    // }
}

 

처음에는 스트링으로 Join 한후 리플레이스로 하나씩 제거하고 카운트를 세려고 했는데 타임아웃.

문자열 수가 적으면 정상작동하나 문자열이 길어지는 경우 연산에 비용이 생각보다 더 큰 것으로 보인다.

 

또한 불필요한 전체 탐색을 계속 반복하여 이를 개선하기위해 스택을 사용하였다.