C# 모음사전 - DFS 중복순열 / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/84512

 

중복 순열 문제.

1. A, E, I, O, U로 만들 수 있는 모든 문자열

2. 길이는 1~5

3. 문자 중복가능

 

의 조건이라서 중복 순열로 모든 문자열 만들고 정렬하면 된다.

 

내 코드

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

public class Solution {
    public int solution(string word) {
        
        var list = new List<string>();
        var arr = new char[5]{'A', 'E', 'I', 'O', 'U'};
        for(int i = 1; i < arr.Length + 1; i++)
            Traverse(arr, "", 0, i, list);
        
        list.Sort();
        return list.FindIndex(s => s == word) + 1;
    }
    
    private void Traverse(char[] arr, string str, int depth, int length, List<string> list)
    {
        if(depth == length)
        {
            list.Add(str);
            return;
        }
        
        for(int i = 0; i < arr.Length; i++)
            Traverse(arr, str + arr[i], depth + 1, length, list);
    }
    
    private void Swap(char[] arr, int x, int y)
    {
        var temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
}

 

중복 순열을 만드는 재귀함수는 여러 문제에서 쓰이니 거의 외워야되는 것 같다.