[백준] (Swift) 2529번 - 부등호 (feat. 백트래킹, DFS)

🟠 TIL - Character는 바로 Int로 변환이 안된다.

아오,, index에러가 자꾸 나면서 애매하게 오류가 나길래 이 오류를 찾는데 한참이 걸렸다 . 이게 뭐라고!!!!! 결론은,, 제목 그대로다. Char 문자는 바로 Int로 변환이 안된다. 즉, "2" 의 type이 char 라면, String으로 바꾸고 Int로 바꿔야 정상적으로 int로 변환이 가능하다. 여기서,,, 30분? 50분? 정도 오류찾는다고 코드 뜯어보고 코드 이리저리 바꿔보고 난리를 쳤다 ㅡㅡ 이제 알았으니 제대로 기억해두길.

var charNum: Character = "2"

Int(charNum)! // ❌ 에러
Int(String(charNum))! // ✅ 이렇게 바꿔줘야 한다.

 

🟠 문제

https://www.acmicpc.net/problem/2529

2529번: 부등호

 

🟠 나의 풀이

우선,, 문제를 처음보고 어떻게 풀어야하나,, 정말 어려웠다. 어떻게 접근해야할지 몰랐고, 약간의 힌트를 찾아보았다. 그냥,, 백트래킹을 이용하면 쉬운 문제였고, 0부터 9까지 돌면서 전에 숫자와 현재 부등호를 비교해보는게 끝이었다.

dfs를 끝내는 조건은 depth == n+1 로 두었다. 만약 2가 입력돼서 부등호가 2개이면, 3개의 숫자를 비교해야하기 때문이다. 근데,,, depth도 사실 필요없다. 그냥 구하려는 answer의 길이를 보면 된다!

answer에 조건에부합하는 숫자들을 하나씩 붙여나가는 방식으로 풀면된다. 현재 answer이 "0"이고, 비교하려고 하는 i 가 "2", 입력받은 부등호가 "<"라면 "0<2" 를 비교해서 true 면 visited 처리해주고, 다시 순회돌기위해서 dfs 재귀를 돌려주면 된다! 이 과정을 그림으로 그려봤다. (나만 이해할 수 있는 그림일수도...?)

(그림에는 depth가 존재하는데 코드를 짜다 보니까 depth가 곧 answer의 길이와 같아서 depth 매개변수를 삭제한채로 코드를 작성했다.)

정리해보자.

1. 0부터 9까지 전부 순회 (최댓값, 최솟값 순서대로 출력해야하기 때문에 9부터 0까지 돌릴거임)
2. visited[i] 확인, false이면 answer에 들어갈 수 있는 조건을 갖춘것!
3. i를 answer에 합쳐주기 전에 입력받은 부등호, answer 맨 마지막에 존재하는 숫자와 비교해서 적당한지 판별
4. 아니라면 아무일도 벌어지지 않고 다음 i로 넘겨주고, 만약 조건이 부합하다면 answer에 합쳐주기
5. 만약 answer의 길이가 n+1과 같다면 answer이 될 수 있는 후보니까, answerList에 넣어주고 return 해줘서 dfs를 끝내주기
6. 9부터 0가지 돌린 결과물이 answerList이기 때문에 어쩔수없이 가장 큰 수가 answerList의 맨앞에, 가장 작은수가 answerList의 맨뒤에 존재하게 되므로, 맨앞과 맨뒤에있는 것들을 순서대로 출력해주자.

 

🟠 정답코드

import Foundation

let n = Int(readLine()!)!
let inequality = readLine()!.split(separator: " ").map{ String($0) }
var answer = ""
var answerList = [String]()
var visited = Array(repeating: false, count: 10)

private func check(num1: Int, num2: Int, inequal: String) -> Bool {
    if inequal == "<" {
        if num1 < num2 {
            return true
        } else {
            return false
        }
    } else {
        if num1 > num2 {
            return true
        } else {
            return false
        }
    }
}

private func dfs(answer: String) {
    if answer.count == n+1 {
        answerList.append(answer)
        return
    }

    for i in stride(from: 9, through: 0, by: -1) {
        if !visited[i] {
            if answer == "" || check(num1: Int(String(Array(answer)[answer.count-1]))!,
                                     num2: i,
                                     inequal: inequality[answer.count-1]) {
                visited[i] = true
                dfs(answer: answer + String(i))
                visited[i] = false
            }
        }
    }

}

dfs(answer: answer)

for i in 0..<2 {
    if i == 0 {
        print(answerList[i])
    } else {
        print(answerList[answerList.count-1])
    }
}