[코딩테스트]백준 - 행운의 문자열

행운의 문자열

문제

민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작했다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다.

입력

첫째 줄에 문자열 S가 주어진다. 길이는 최대 10이다.

출력

첫째 줄에 위치를 재배치해서 얻은 서로 다른 행운의 문자열의 개수를 출력한다.

예제 입력 1

aabbbaa

예제 출력 1

1

출처

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 백트래킹
• 탐색

해결한 코드

function b1342() {
    var fs = require('fs');
    var str = fs.readFileSync('/dev/stdin').toString().trim();
    //var str = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "");
    var len = str.length
    var visited = new Array(len).fill(false)
    var arr = []
    var result = [0]
    var a = new Array(26).fill(0)

    for(var i=0; i<len; i++){
        a[str.charCodeAt(i)-'a'.charCodeAt(0)]++;
      // 각 문자가 얼마나 중복되었는지 세어주기 위함 
    }
    isLucky(arr, str, len, result, 0, visited)

    for(var i=0; i<a.length; i++){
        if(a[i] > 1){
            result[0] /= fac(a[i])
          // 중복된만큼 팩토리얼하여 나눠줌 
        }
    }
    console.log(result[0])

}

b1342()

function isLucky(arr, str, len, result, count, visited) {
    if (count === len) {
        if (isCheck(arr)) {
          // 행운의 문자열 조건에 부합하면 
            result[0]++;
            return
        }
    }
    for (var i = 0; i < len; i++) {
        if (!visited[i]) {
            visited[i] = true
            arr.push(str.charAt(i))
            isLucky(arr, str, len, result, count + 1, visited)
            arr.pop()
            visited[i] = false
        }
    }
}

function isCheck(arr) {
    for (var i = 0; i < arr.length - 1; i++) {
        if (arr[i] == arr[i + 1]) return false
    }
    return true
}

function fac(n) {
    if (n == 1) return n
    else return n * fac(n - 1)
}

알고리즘

※ 백트래킹으로 푼다.

1. 만들 수 있는 모든 행운의 문자열의 갯수를 센다.

1-1. 입력으로 받은 문자들로 행운의 문자열을 만들려면?
👉🏻 문자열 순서대로 백트래킹으로 돌며 문자열을 만든다.
👉🏻 행운의 문자열은 각 문자가 직전 문자와 같지 않아야 한다.
👉🏻 각 문자열별로 방문여부를 확인하여 방문하지 않은 문자들로만 문자열을 만든다.
이를 위해 visited 배열이 필요

1-2. 그렇다면 백트래킹 함수를 어떻게 구성해야 할까?

• 입력으로 들어온 문자열을 순서대로 넣으며 행운의 문자열을 만들어줄 배열이 필요하다.
  ex. 입력으로 "aabbbaa"이 들어왔다면,

1-2-1. 우선 맨 처음 문자인 'a'를 배열 arr에 넣는다.

arr = ['a']

해당 문자는 방문했으므로 visited[0] = true 해준다.
이렇게 바뀐 arr, visited를 데리고 백트래킹 함수를 재귀로 부른다. 문자열 하나 넣었으니 count+1를 해준다.

1-2-2. 재귀로 불러진 함수에서 i가 0일때 visited[0] = true이므로, i = 1, visited[1]로 넘어간다.

arr = ['a', 'a']

해당 문자는 방문했으므로 visited[1] = true 해준다.
그럼 다시 아까처럼 바뀐 arr, visited를 데리고 백트래킹 함수를 재귀로 부른다. count+1 해준다.

1-2-3. 이렇게 시간이 흘러 흘러... 과정이 흘러 흘러.. count = 입력받은 문자열 길이가 되면
arr 배열의 구성이 행운의 문자열 조건에 부합하는지 확인한다.

• 행운의 문자열 조건에 부합하면 -> 갯수 세어주기
  📍 나는 result = [0]를 만들어서 원소 0의 숫자를 증가시켰다.
• 부합하지 않으면 -> 그냥 return됨

1-2-4. return 되면, arr에 담았던 방금 그 문자열을 뺀다.
해당 문자열의 방문 여부도 false로 돌려놓는다.

2. 중복 순열 처리를 해준다.

이를 위해 입력받은 문자열에서 중복되는 문자의 갯수를 센다.
그 갯수만큼 팩토리얼하여 (위에서 구한 result 값에 해당하는) 행운의 문자열 갯수에다 나눠주어야 하기 때문이다.

ex. "aabbbaa"의 경우, a는 4번, b는 3번 중복된다.
따라서 result[0]의 값 / 4!*3! 을 해주어야 한다. 중복된 행운의 문자열을 제거하기 위해서다.

3. (알고리즘은 아니지만..) 자바스크립트로 푼다면 입력받을 때 반드시 trim()을 붙여야 한다.

그래야 한다.. 그러지 않아서 틀렸다.. 계속..

처음에는

if (!visited[i]) {
      visited[i] = true
      arr.push(str.charAt(i))
      isLucky(arr, str, len, result, count + 1, visited)
      arr.pop()
      visited[i] = false
}

이 부분에 isCheck 함수를 사용했다. arr안에 문자를 넣을 때마다 직전 문자랑 같은지 확인해주고, 같지 않을 때만 진행시키려고 했다.
근데 이렇게 쓰면 시간이 더 걸린다네..? 그래서 시간초과가 떴나 봅니다 ㅠㅠ
중복 순열로 푸는 방법이 시간이 더 적게 걸리는 듯 하다. 다른 분들 풀이를 봤는데도 그러한 것 같다..