(C#) 110 옮기기

https://school.programmers.co.kr/learn/courses/30/lessons/77886

프로그래머스

 

문자열이 싫다

 

 주어진 문자열 x를 앞에서부터 순회하며 "111"을 찾은 뒤, 가장 가까운 "110"과 위치를 바꾸는 방법으로 풀려고 했는데 틀렸다.

 테스트 케이스는 모두 맞았고, 반례도 떠오르지 않았으나 막상 제출했을 때 모든 문제가 실패가 떴다.

 

 그래서 다른 방법으로 풀었다. x를 한 글자씩 스택에 넣는다. 스택에 0이 들어갈 때, 스택을 3개 꺼내서 문자열이 "110"인지 확인한다. "110"의 갯수를 모두 세고, 마지막에 남은 문자열에 "110"들을 끼워넣는다.

 

 이 과정에서도 여러가지 방법을 테스트했는데, 첫번째는 StringBuilder를 사용하는 것이었다. StringBuilder.Append를 사용해 시작 ~ 0까지, "110", 나머지를 추가하는 방법으로 했을 때 대부분은 통과했지만 하나가 시간초과가 떴다.

 그 다음은 string.Insert를 사용해 string을 직접 수정했다. 대부분 시간초과가 떴다.

 마지막으로 "110"을 String.Concat(Enumarable.Repeat())을 써서 미리 만들어두고 Insert하는 방법을 썼다.

 Insert 횟수가 확실히 줄어서 그런지 통과할 수 있었다.

 Enumarable.Repeat가 제일 성능이 좋은가보다.

 

코드

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

public class Solution {
    public string[] solution(string[] s)
    {
        string[] answer = new string[s.Length];
        for (var i = 0; i < s.Length; i++)
        {
            string x = s[i];
            int count = 0;
            Stack<char> stack = new Stack<char>();
            foreach (char c in x)
            {
                stack.Push(c);
                if (stack.Count >= 3 && c == '0')
                {
                    var third = stack.Pop();
                    var second = stack.Pop();
                    var first = stack.Pop();
                    if (first == '1' && second == '1' && third == '0')
                    {
                        count++;
                    }
                    else
                    {
                        stack.Push(first);
                        stack.Push(second);
                        stack.Push(third);
                    }
                }
            }
            var remain = stack.ToArray();
            Array.Reverse(remain);
            var a = String.Join("", remain);
            var idx = a.LastIndexOf('0');
            var z = string.Concat(Enumerable.Repeat("110", count));
            if (idx != -1)
            {
                a = a.Insert(idx + 1, z);
            }
            else
            {
                a = a.Insert(0, z);
            }
            answer[i] = a;
        }
        return answer;
    }
}