[Swift][BruteForce] 백준 2529번 (부등호)

요구능력 : 백트래킹에 대한 이해

 

코드설명 : 

맨 아래에 수정된 코드있습니다.

 

 

이 문제는 0~9까지의 수 중에서 부등호의 갯수 +1 개만큼의 수를 뽑아서 부등호 조건에 맞출 수 있는지를 묻는 문제이다.

 

문제에서 요구하는 부분

1. 부등호의 개수 + 1개 만큼의 수

2. 뽑은 수를 가지고 부등호 조건을 만족하는지 확인

3. 부등호 조건을 만족하는 수들의 최소값과 최대값 출력

 

1. 1번부터 해결하면 n과m문제를 떠올리면 된다.

이 문제에서는 0부터 9까지의 수 중에서 선택하라고 했고 선택된 숫자는 모두 달라야한다고 했으므로 방문처리까지 해주면서

방문하는 수를 k + 1 (부등호의 개수 + 1)개 뽑았을 때 부등호조건에 비교하기위해서 result라는 배열에 저장해줬다.

for i in 0...9 {
        if !visited[i] {
            visited[i] = true
            result.append(i)
            dfs(depth + 1)
            result.removeLast()
            visited[i] = false
        }
    }

 

2. arr은 부등호가 들어있는 배열이다.

현재 arr[i]가 부등호 ">"를 가지고있고 현재 수와 다음에 오는 수가 arr[i] 부등호로 비교했을 때 참이면 배열을 계속돌고,

현재 arr[i]가 부등호 "<"를 가지고있고 현재 수와 다음에 오는 수가 arr[i] 부등호로 비교했을 때 참이면 배열을 계속돌고,

아니면 return을해서 현재 함수를 빠져나간다.

만약, 함수를 빠져나가지 않았으면 부등호조건을 모두 만족하는것이므로 resultArr에 수의 배열인 result를 매핑해서 넣어준다.

(참고 : String형식으로 넣어준 이유는 Int형식으로 넣었을 경우에 앞에 0이 생략되기 때문이다.)

for i in 0..<arr.count{
            if result[i] > result[i + 1] && arr[i] == ">"{
                continue
            }else if result[i] < result[i + 1] && arr[i] == "<"{
                continue
            }else{return}
        }

 

 

후기 : n과m을 이해하고 있다면 조건만 넣어주면 간단한 문제

let k = Int(String(readLine()!))!
let arr = readLine()!.split(separator: " ").map{String($0)}
var visited = Array(repeating: false, count: 10)
var result: [Int] = []
var resultArr: [String] = []
func dfs(_ depth: Int){
    if depth == arr.count + 1{
        for i in 0..<arr.count{
            if result[i] > result[i + 1] && arr[i] == ">"{
                continue
            }else if result[i] < result[i + 1] && arr[i] == "<"{
                continue
            }else{return}
        }
        resultArr.append(result.map{String($0)}.joined(separator: ""))
        return
    }
    for i in 0...9 {
        if !visited[i] {
            visited[i] = true
            result.append(i)
            dfs(depth + 1)
            result.removeLast()
            visited[i] = false
        }
    }
}
dfs(0)
print(resultArr.max()!)
print(resultArr.min()!)

---

수정사항 : 2022.09.28

위의 코드로 작성했을때 기존에 통과되었던게 현재는 시간초과가 나타나는 상황입니다.

아래코드로 재작성해서 통과하였습니다.

let k = Int(String(readLine()!))!
var arr = readLine()!.split(separator: " ").map{String($0)}
var answer = [String]()
var visited = Array(repeating: false, count: 10)
var resultArr = [Int]()
func dfs(_ depth: Int, _ now: Int){
    if depth == k + 1{
        answer.append(resultArr.map{String($0)}.joined())
        return
    }
    for i in 0...9{
        if !visited[i]{
            if depth > 0{
                if now <= i && arr[depth - 1] == ">"{continue}
                else if now >= i && arr[depth - 1] == "<" {continue}
            }
            visited[i] = true
            resultArr.append(i)
            dfs(depth + 1, i)
            visited[i] = false
            resultArr.removeLast()
        }
    }
}
dfs(0, 0)
print(answer.max()!)
print(answer.min()!)