백준[6443] - 애너그램 (Kotlin)

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() {

    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    var strs = charArrayOf()
    var visited = arrayOf<Int>()
    var selected = arrayOf<Char>()

    fun dfs(k: Int) {
        if (k == strs.size) {
            for (i in strs.indices) {
                bw.write("${selected[i]}")
            }
            bw.write("\n")
        } else {
            // k번째 자리에 대해 중복되는 단어 제거 위한 변수
            var beforeChar = ' '
            for (i in strs.indices) {
                // 같은 자리에 대해 이전에 같은 문자가 들어갔다면 continue
                if (beforeChar == strs[i]) continue
                // 이미 사용한 단어라면 continue
                if (visited[i] == 1) continue
                visited[i] = 1
                selected[k] = strs[i]
                dfs(k + 1)
                visited[i] = 0
                selected[k] = ' '
                // 다음 loop 돌기 전에 이전에 k번째 자리에 넣은 단어 저장
                beforeChar = strs[i]
            }
        }
    }

    repeat(br.readLine().toInt()) {
        strs = br.readLine().toCharArray()
        strs.sort()
        visited = Array(strs.size) { 0 }
        selected = Array(strs.size) { ' ' }
        dfs(0)
    }

    bw.flush()
    bw.close()
    br.close()
}

 

repeat(br.readLine().toInt())를 통해 입력 받은 숫자 만큼 반복하여 애너그램을 출력한다.

입력받은 문자열에 대해 CharArray로 변환하여 문자별로 비교하는데, 이 때 알파벳 순서로 출력해야하는 조건을 위해 sorting을 수행하였다.

중복되지 않게 출력해야 하는 조건을 위해 beforeChar라는 변수를 추가하여 각 자리마다 이전에 넣은 문자를 저장한 후 비교한다.

같은 위치에 대해 이전에 넣은 문자와 같은 문자라면 continue를 통해 넘어가고, visited 배열을 통해 이미 이전 자리에서 사용한 문자여도 continue를 통해 넘어간다.

 

 

 

고찰 : 정말정말 많이 부족함을 느낀다.

몇 문제 풀어봤던 백트래킹과 그리 다른 유형의 문제가 아니었음에도 불구하고 조금만 조건이 추가된 응용문제에 대해서는 1시간이나 걸릴 정도로 응용능력과 문제해결능력이 부족하다. 넘 슬프다. 가장 시간이 오래 걸렸던 부분은 부끄럽지만 N개의 영단어에 대한 처리였다.

괜히 깔끔하게 해보겠다고 repeat을 통해 n번 str, visited와 같은 배열을 재사용하는 방식에 대해 오래 고민하였다.

저게 정말 깔끔한 코드인지는 전혀 모르겠다. 더 열심히 해야겠다.

 

 

걸린 시간 : 1시간

난이도 : 골드 5

문제 : https://www.acmicpc.net/problem/6443

6443번: 애너그램