[프로그래머스 C#] Lv.3 110 옮기기

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

110을 옮겨 만들 수 있는 모든 문자열 중 사전 순으로 가장 앞에 위치하는 문자열을 찾는 문제

- 모든 "110"을 제외한 문자열에서 마지막에 있는 0 뒤에 110을 모두 붙이면 조건을 만족하게 됨

 ( 남아있는 문자열에 0이 없는 경우 맨 앞에 삽입 )

 

1) Stack : 110 추출을 위해 사용

- 110 추출이 끝난 Stack 안에는 110을 추출하고 남은 문자가 역순으로 담기게 됨

+ 처음에는 String.Replace()를 이용해보려고 했으나 시간초과 ( 풀이 코드 : 게시물 최하단 )

 

2) List : Stack의 후입선출 구조로 인해 역순으로 바뀐 순서를 정순으로 바꾸기 위해 사용

+ List를 쓰지않고, 역순을 가정하여 연산하며 StringBuilder에 넣고 마지막에 문자열을 뒤집어도 될 것

 

3) StringBuilder : 반환할 문자열에 대해 추가가 많이 일어나기 때문에 사용

- 110 삽입 전, 110 삽입, 110 삽입 후 로 나누어 반환할 문자열 완성

 

주석 참조

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

    public class Solution
    {
        public string[] solution(string[] s)
        {
            for (int i = 0; i < s.Length; i++)
                s[i] = Function(s[i]);

            return s;
        }

        public string Function(string str)
        {
            if (str.Length < 3)
                return str;

            var stack = new Stack<char>();
            int count = 0; // 110의 개수

            // 110 추출
            for (int i = 0; i < str.Length; i++)
            {
                if (stack.Count < 2)
                {
                    stack.Push(str[i]);
                    continue;
                }

                // 110이 만들어지는지 탐색
                if (str[i] == '0')
                {
                    char c = stack.Pop();

                    // 110을 발견
                    if (c == '1' && stack.Peek() == '1')
                    {
                        stack.Pop();
                        count++;
                        continue;
                    }

                    // 아닐 경우 되돌리기
                    stack.Push(c);
                }

                stack.Push(str[i]);
            }

            var list = stack.ToList(); // 역순으로 저장됨
            list.Reverse(); // 역순 -> 정순

            var sb = new StringBuilder(); // 반환할 문자열
            int oneCount = 0; // 1의 개수

            // 110 삽입 전 문자열 세팅
            for (int i = 0; i < list.Count; i++)
            {
                if (list[i] == '1')
                {
                    oneCount++;
                    continue;
                }

                // list[i] == '0'
                for (int j = 0; j < oneCount; j++)
                    sb.Append("1");

                oneCount = 0;
                sb.Append("0");
            }

            // 110 삽입
            for (int i = 0; i < count; i++)
                sb.Append("110");

            // 110 삽입 후 문자열 세팅
            for (int i = 0; i < oneCount; i++)
                sb.Append("1");

            return sb.ToString();
        }
    }

+ String.Replace()를 이용한 풀이 코드 // 시간 초과

- Replace()가 한번 호출될 때마다 문자열 전체를 순회하며 대상을 찾기 때문에 시간초과

        public string Function(string str)
        {
            if (str.Length < 3)
                return str;

            int length;
            int count = 0; // 110 개수
            
            // 110 추출
            do
            {
                length = str.Length;
                str = str.Replace("110", "");
                count += (length - str.Length) / 3;
            }
            while (length != str.Length);

            var sb = new StringBuilder(); // 반환할 문자열
            int oneCount = 0; // 1의 개수

            // 110 삽입 전 문자열 세팅
            for (int i = 0; i < str.Length; i++)
            {
                if (str[i] == '1')
                {
                    oneCount++;
                    continue;
                }

                // str[i] == '0'
                for (int j = 0; j < oneCount; j++)
                    sb.Append("1");

                oneCount = 0;
                sb.Append("0");
            }

            // 110 삽입
            for (int i = 0; i < count; i++)
                sb.Append("110");

            // 110 삽입 후 문자열 세팅
            for (int i = 0; i < oneCount; i++)
                sb.Append("1");

            return sb.ToString();
        }