C# 프로그래밍 기초 실습 전자책

C# / .NET 알고리즘과 퀴즈
본 알고리즘 퀴즈 문제는 C#/.NET 개발자를 위한 알고리즘 인터뷰 혹은 C# 프로그래밍을 통한
문제 해결 알고리즘을 연구해 보는데 도움이 되고자 작성되었습니다.


퀴즈 질문


예상답변/설명

문자열 순열을 구하기 위해서는 출력버퍼에 추가된 문자위치를 기억하기 위해 아래 예제에서처럼 FLAG 배열을 사용한다. 즉 사용/미사용을 FLAG에 저장해 두고 사용하지 않은 문자들만을 출력버퍼에 추가하는 것이다. 재귀 호출을 사용하여 문자열 크기 만큼 출력 버퍼가 채워질 때가지 계속 진행하며, 출력 버퍼가 모두 채워졌을 때는 이를 출력하고, 마지막 문자를 버퍼에서 제거하고 계속 다음 순열 문자열을 찾아낸다.

void PrintPermutation(string s)
{
    StringBuilder sb = new StringBuilder(s.Length);
    bool[] flag = new bool[s.Length];
    Permute(s, sb, flag);
}

void Permute(string s, StringBuilder sb, bool[] flag)
{
    if (sb.Length == s.Length)
    {
        Console.WriteLine(sb.ToString());
        return;
    }

    for (int i = 0; i < s.Length; i++)
    {
        if (flag[i]) continue;

        sb.Append(s[i]);
        flag[i] = true;

        Permute(s, sb, flag);

        sb.Remove(sb.Length - 1, 1);
        flag[i] = false;
    }
}