20240328_A로 B 만들기(프로그래머스)

오늘의 TIL은 A로 B만들기라는 프로그래머스의 문제에 대한 내용이다.

 

문제 링크

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

프로그래머스

 

 

문제 설명

문자열 before와 after가 매개변수로 주어질 때,

before의 순서를 바꾸어 after를 만들 수 있으면 1을,

만들 수 없으면 0을 return하시오.

 

 

제한 조건

0 < before의 길이 == after의 길이 < 1,000

before와 after는 모두 소문자로 이루어져 있다.

 

 

해결 방안

1번 방안

for 문을 이중으로 사용하여 after의 0번 index부터 마지막 index까지

각 index에 해당하는 문자가 before에 있는지 확인하고

있다면 해당하는 문자를 before에서 삭제한다.

이를 반복하여 before가 모두 삭제됬다면(사용되었다면)

after를 만든 것이므로 1을 return하고

before에 남은 원소가 있다면 0을 return한다.

 

예를 들어서 "olleh"를 이용하여 "hello"를 만든다면

after[0]은 h로 before에서 h를 삭제하여 "olle"이 남고

after[1]은 e로 before에서 e를 삭제하여 "oll"이 남고

이를 반복하면 before가 모두 삭제되므로 1을 return.

"allpe"를 이용하여 "apple"를 만든다면

after[0]은 a로 before에서 a를 삭제하여 "llpe"가 남고

after[1]은 p로 before에서 p를 삭제하여 "lle"가 남고

after[2]는 p로 before에 남은 p가 없으므로 0을 return.

 

 

통과한 답안

using System;

public class Solution {
    public int solution(string before, string after) {
        
        for (int i = 0; i < after.Length; i++)
        {
            bool found = false;
            
            for (int j = 0; j < before.Length; j++)
            {
                if (after[i] == before[j])
                {
                    before = before.Remove(j, 1);
                    found = true;
                    break;
                }
            }
            
            if (!found)
                return 0;
        }
        
        return 1;
    }
}

 

이 코드는 간단하므로 분류를 나누지 않고 정리하면

외부 for문에서 after의 모든 원소에 대해 확인을 진행하는데

bool 값을 사용하여 after의 원소와 같은 before의 원소를 찾았는지 확인한다.

만약 찾지 못했다면 바로 0을 return하고 코드를 종료하도록 설정했다.

 

내부의 for문에서 before의 모든 원소에 대해서

지금 검사하는 after의 원소가 before에 있는지 확인하고 있다면

해당하는 원소를 지우고 bool 값을 true로 만들어준다.

 

이를 계속 반복해서 before의 모든 원소를 삭제했다면 1을 return한다.

 

 

StringBuilder를 사용한 풀이

이 문제의 경우에는 stringbuilder를 사용해서도 문제를 풀 수 있다.

using System;
using System.Text;

public class Solution {
    public int solution(string before, string after) {
        
        StringBuilder sb = new StringBuilder(before);

        for (int i = 0; i < after.Length; i++)
        {
            bool found = false;

            for (int j = 0; j < sb.Length; j++)
            {
                if (after[i] == sb[j])
                {
                    sb.Remove(j, 1);
                    found = true;
                    break;
                }
            }

            if (!found)
            {
                return 0;
            }
        }

        return 1;
    }
}

 

코드는 위와 같은데 이전 풀이와의 차이점은 before를 stringbuilder로 변경하고

내부 for문에서 before에서 문자를 삭제하는 부분이 달라졌는데,

전체적인 코드는 차이가 없으나 이 두 부분이 성능적인 면에서는 큰 차이를 발생시킨다.

 

C#에서 string은 참조 형식이지만 값 형식의 특징을 가진다.

이는 string의 값을 변경하는 경우, 그 string의 값을 수정하는 것이 아니라

새로운 string을 생성하고 이를 연결하는 과정을 가지는 것이다.

 

즉, 위의 코드에서 before.Remove를 사용하여 하나의 문자를 삭제하면

before에서 문자가 하나 삭제되는 것이 아니라

문자가 하나 삭제된 새로운 문자를 만들고 이를 before에 연결하는 것이다.

 

따라서 위의 코드에서 최대 after의 길이 만큼의 문자가 생성되게 되므로

이는 모두 가비지가 되므로 문자열의 길이가 길거나

이러한 작업들이 많이 일어난다면 그만큼 성능에 문제가 생기게 된다.

 

하지만 stringbuilder는 이러한 string의 문제를 해결할 수 있는 방법으로

값을 수정하는 것이 가능한 string이라고 할 수 있다.

따라서 이러한 문제를 푸는 경우에는 stringbuilder를 사용하는 것이

string을 사용하는 것보다 훨씬 좋다고 할 수 있다.

 

실제로 짧은 문자열(길이가 최대 1000)인 이 문제에서도 아래와 같이 결과를 얻을 수 있었는데

좌측이 stringbuilder를 사용한 결과, 우측은 string을 사용한 결과

 

주어지는 string을 stringbuilder로 변환하는 과정이 있기 때문에

최소값은 string을 사용한 결과가 더 빠르지만,

전체적인 분포를 살펴보면 stringbuilder를 사용하는 것이 고른 표준편차를 보이는데

이를 차트로 나타내면 아래와 같다.

 

 

파란색이 stringbuilder를 사용한 경우의 시간, 빨간색이 string을 사용한 경우의 시간인데

전체적으로 파란색 그래프들이 모여있다는 것을 알 수 있다.

이는 string 사용하는 경우에는 길이에 따라서 소요되는 시간이 커질 수 있다는 것을 의미한다.

또 표준편차의 경우 stringbuilder는 약 0.134, string은 약 0.285로

string을 사용하는 경우에 문제에 따라서 성능 차이가 심하다는 것을 의미한다.

즉, 이러한 string을 조작하는 문제를 풀이하는 경우에는 최대한 stringbuilder를 사용하는 것이 좋다는 것이다.

 

 

오늘은 간단하게 해결할 수 있는 알고리즘 문제로 시작하여

string과 stringbuilder의 특징을 알아보는 TIL을 작성했는데

stringbuilder가 더 좋다는 것을 어필하기 위해 그래프와 분산(표준편차)을 이용하여 작성했다.

이렇게 정리하기 전까지는 나도 좋다는 것만 알았지 구체적이지 않았는데

그래프와 표준편차를 보니 확실하게 stringbuilder의 이점을 이해할 수 있었다.