[알고리즘 테스트, Kotlin] Stack을 이용하여 순열(Permutation)을 구해보자

알고리즘 테스트에 쓰이는 여러 기초적인 알고리즘을 내 방식대로 구현하여 완전히 내 것으로 만들 필요성을 느꼈다.

특히 순열과 조합 같은 경우 자주 쓰는 라이브러리가 기억이 잘 나지 않을 경우를 대비해, 나만의 알고리즘을 만들어보기로 했다.

스택(Stack)을 이용하여 순열을 구해보자

다음과 같은 상황을 상정해보겠다.

문자열이 ABCD가 주어졌고, 이를 조합하여 총 4! = 24개의 순열을 만들 수 있다.

이 때 이 순열을 모두 나열해야하는 상황이다.

보통은 재귀를 이용해서 풀지만, 개인적으로는 재귀보다는 스택을 이용하여 푸는 게 더 재미있고 직관적인 편이라 스택을 이용하여 풀어보겠다.

먼저 필요한 아이템부터 나열해보겠다.

• 1. 순열을 만들 문자열 ex) "ABCD"
• 2. 완성된 순열을 담을 리스트(List)
• 3. 순열을 만드는 도중 한번 지나왔던 순열들을 담을 세트(Set)
• 4. 현재 조합 중인 문자 순열을 담을 스택(Stack)
• 5. 아직 포함되지 않은 문자 인덱스를 담을 리스트(List)

이 아이템들을 이용한 스택 구현 방법에 대해 설명하겠다.

• 1. for문을 통해 문자열의 각 문자를 순회하며, 5번 아이템을 구성한다. 만약 이번 루프에서 첫번째 문자를 순회중이라면, 5번 아이템(List)은 "BCD"에 해당하는 2, 3, 4를 담을 것이다.
• 2. 순회중인 문자와 5번 아이템을 묶어서, 4번 아이템(Stack)에 넣는다. 본인은 Permutation이라는 데이터 클래스를 활용하여 Stack에 집어넣었다.
• 3. 4번 아이템(Stack)이 비어있지 않는 조건으로 While 루프를 구성한다. 만약 4번 아이템(Stack)의 마지막 오브젝트(Permutation)가 3번 아이템(Set)에 이미 있다면, 4번 아이템(Stack)을 pop하고 다음 while 루프를 돌린다. 만약 해당 오브젝트가 3번 아이템(Set)에 없다면 추가한다.
• 4. 마지막 오브젝트가 완성된 순열이라면, 2번 아이템(List)에 추가하고 4번 아이템(Stack)을 pop한다. 이후 다음 while 루프를 돌린다.
• 5. 만약 완성되지 않은 순열이라면, 5번 아이템을 순회하며, 추가로 더 넣을 수 있는 문자열 인덱스에 대해 순열을 조합하고 새로운 5번 아이템(List)을 구성하여 4번 아이템(Stack)에 추가한다.

  말로 하면 복잡한데, 결국 코드로 옮기면 아래와 같다.

    // @param currentPermutation: 현재 조합 중인 순열
     // @param notIncludedChar: 아직 포함되지 않은 문자의 인덱스
     data class Permutation(val currentString: String, val notIncludedChar: ArrayList<Int>)
  
     // 1번 아이템
     val mString = "ABC"
     // 2번 아이템
     val permutationList = mutableListOf<String>()
     // 3번 아이템
     val composedPermutation = mutableSetOf<String>()
     // 4번 아이템
     val stack = Stack<Permutation>()
     val r = mString.length
     for (charIdx in mString.indices) {
         // 1번 과정
         // 5번 아이템
         val notIncludedChar: ArrayList<Int> = mString.indices.filterNot { it == charIdx } as ArrayList<Int>
         
         // 2번 과정
         stack.push(Permutation(mString[charIdx].toString(), notIncludedChar))
         
         // 3번 과정
         while (stack.isNotEmpty()) {
             val currentPermutation = stack.peek()
             if (currentPermutation.currentString in composedPermutation) {
                 stack.pop()
                 continue
             }
             composedPermutation.add(currentPermutation.currentString)
  
             // 4번 과정
             if (currentPermutation.currentString.length == r) {
                 permutationList.add(currentPermutation.currentString)
                 stack.pop()
                 continue
             }
             
             // 5번 과정
             for (i in currentPermutation.notIncludedChar) {
                 // 새 문자열
                 val nextString = currentPermutation.currentString + mString[i].toString()
                 // 새 5번 아이템
                 val nextNotIncludedChar = currentPermutation.notIncludedChar.filterNot { it == i } as ArrayList<Int>
                 if (nextString !in composedPermutation) stack.push(Permutation(nextString, nextNotIncludedChar))
             }
         }
     }