<Lv.3> 110 옮기기 (프로그래머스 : C#)

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

📕 문제 설명

0과 1로 이루어진 어떤 문자열 x에 대해 다음의 행동을 해 x를 최대한 사전 순으로 앞에 오도록 만들고자 함

=> x에 있는 "110"을 뽑아 임의의 위치에 다시 삽입

• Input
  변형시킬 문자열 x가 여러 개 들어있는 문자열 배열 s
• Output
  위의 행동으로 변형해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에오는 문자열을 배열에 담아 반환

예제

풀이

1. 주어진 string에 대해 110의 개수를 먼저 센다. (stack을 활용해 해당 110이 빠지면 앞으로 당겨지는 부분을 고려해준다.)
2. 110이 빠진 string에 대해 뒤에서부터 연속되는 1의 개수를 세준다.
3. 110이 빠진 string의 처음부터 연속되는 1이 나오기 직전까지 정답 문자열에 붙여준다.
4. 110의 개수만큼 정답 문자열에 붙여준다.
5. 연속되는 1의 개수만큼 정답 문자열에 붙여준다.

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

public class Solution {
    public string[] solution(string[] s) {
        string[] answer = new string[s.Length];
        
        for (int i = 0; i < s.Length; i++)
        {
            answer[i] = GetTransformedString(s[i]); 
        }
    
        return answer;
    }
    
    public string GetTransformedString(string s)
    {
        if (s.Length < 3) return s;
        // list로도 할 수 있을것같기도..?
        Stack<char> stack = new Stack<char>();
        int targetCount = 0; // 110 개수
        int oneCount = 0; // 남은 문자에 대해 뒤에서부터 연속되는 1의 개수
     
        for (int i = 0; i < s.Length; i++)
        {
            char currentS = s[i];
            
            if (stack.Count < 2)
            {
                stack.Push(currentS);
                continue;
            }
            
            char prevS = stack.Pop();
            char prevprevS = stack.Peek();
            
            if (prevprevS == '1' && prevS == '1' && currentS == '0')
            {
                targetCount += 1;
                stack.Pop(); // prevprev도 제거
            }
            else
            {
                stack.Push(prevS); // 뺐었던 prev S 넣기
                stack.Push(currentS); // 현재 S 넣기
            }
        }
        
        List<char> remainChars = stack.ToList(); // 순서 top -> bottom 순으로 list 만들어짐
        
        for (int i = 0; i < remainChars.Count; i++)
        {
            if (remainChars[i] != '1') break;
            oneCount += 1;
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = remainChars.Count - 1; i >= oneCount; i--)
        {
            sb.Append(remainChars[i]);
        }
        
        string transformedString = "";
        transformedString += sb.ToString();
        transformedString += String.Concat(Enumerable.Repeat("110", targetCount));
        transformedString += new String('1', oneCount);
        
        return transformedString;
    }
}

결과