BOJ_2661.좋은수열.swift

설명

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

좋은 수열을 구하여라

 

풀이 과정

아이디어를 떠올리는 것이 많이 힘들었다.

 

좋은 수열을 찾기 위해서는 수를 한개씩 추가할 때 마다 좋은 수열인지 반복해서 체크하는 과정이 필요했다. 또한 앞에서 아무리 좋은 수열 이었어도 뒤에 붙이는 숫자에 따라 나쁜 수열이 될 수도 있었기 때문에 dp와 같은 방법은 사용할 수 없었고 모든 경우를 대입하는 백트레킹 기법을 사용해야만 했다.

 

생각해낸 방법은 뒤에 숫자를 붙일 때 마다 좋은 수열을 체크하는 것이었다.

체크하는 방법을 떠올리는게 가장 어려웠는데 결국에 생각해낸 방법은 다음과 같다.

 

1. 똑같은 숫자가 반복해서 등장한 경우 무시한다.
2. 숫자의 간격을 2부터 n/2 까지 만들어서 숫자를 서로 비교해본다.
3. 만약 일치하는 숫자가 떨어진 간격 만큼 나왔다면 그 간격만큼의 중복된 수열이 등장했다는 것을 의미하므로 나쁜 수열이 된다.
   • 예시) 1231231
     • 간격이 2
       • {1, 3}, {2, 1}, {3, 2}, {1, 3}, {2, 1}
       • ⇒ 0개가 일치한다.
     • 간격이 3
       • {1, 1}, {2, 2}, {3, 3} + {1, 1}
       • ⇒ 3개가 일치한 순간 나쁜 수열이 확인 되었기에 다른 수열을 찾아본다.
4. 위의 과정에서 통과한 수열은 중복된 수열이 없기 때문에 좋은 수열이 된다.

 

리뷰

구현이 아직 부족하다는 것을 느꼈다.😂

 

백트래킹을 반복적으로 풀어봤기에 어느정도 푸는 법이 떠오르긴 했지만 정작 check를 구현하는데서 시간을 너무 많이 써버렸다. 😵

 

다른 사람들의 풀이를 보니 내 풀이와 차이점이 보였는데 check 에 해당하는 부분을 매번 모두 계산하는 것이 아니라 추가된 경우 추가된 부분만 비교하는 것이다. 내 풀이는 문자열이 길어졌을 때 비교했던 수열을 또 비교를 해야하지만 이 풀이법 같은 경우 제일 마지막에 추가된 숫자 근처의 1~n/2 개 수열만 비교를 하면 되기 때문에 더 효율적이었다.

 

구현에 대해 부족한 점이 많은 것을 느꼈고 많은 문제를 접해야 할 것 같다.👻

 

소스코드

import Foundation

let n = Int(readLine()!)!
var arr = [Int](repeating: 0, count: 82)
var done = false

func check(_ len: Int) -> Bool {
    for i in 2..<len {
        for j in 1...(len-i) {
            var temp = 0
            for k in j..<j+i {
                if k+i > len+1 {
                    break
                }
                if arr[k] == arr[k+i] {
                    temp += 1
                }
            }
            if temp == i {
                return false
            }
        }
    }
    return true
}

func solution(_ len: Int) {
    if len == n {
        if !done {
            done = true
            for i in 1...len {
                print(arr[i], terminator: "")
            }
            exit(0)
        }
    }

    for i in 1...3 {
        if arr[len] == i {
            continue
        }
        arr[len+1] = i
        if len < 2 || check(len) {
            solution(len+1)
        }

    }
}

solution(0)

 

알고리즘 스터디에서 공유했던 내용입니다.

https://bobmongus.notion.site/Week-02-a53803f409e64a8cab784ce5a15e500d