[백준] Swift 2529 부등호 backtracking

문제 : 

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

2529번: 부등호

 

분석 :

혼자서 풀지 못했다 .. ㅜ

부등호의 조건을 만족하는 중복 없는 조합을 구하는 문제였다. 

그러한 조합들 중 최대 값, 최소 값을 구하는 게 답이였다 !

 

우선 부등호 개수 + 1개만큼의 숫자를 사용한다. 조건 만족시 answer 배열에 담는다.

그리고 for 문 0 ~ 9 10개의 숫자에 대해 첫번째 숫자일 경우는 부등호 조건을 체크하지 않고 바로 숫자를 넣는다.

그 다음 index가 1이상일때 부터는 첫번째 숫자, 첫번째 부등호, 두번째 숫자 3개를 파라미터로 해 signCheck 함수를 거친다. 

< 기호일땐 num2가 더 커야 하고, > 기호일땐 num1이 더 커야 한다. 

swift에선 character.asciiValue시 아스키 값을 얻을 수 있다 여기에 0 아스키 값인 48만큼 빼주어 int형으로 만들어 주었다.

 

예를 들어 

2

< >

와 같이 input이 들어왔을때

0 < 1 까지 입력 받은 상태라고 해보자

다음 backtracking 재귀 함수를 통해 index = 2, num1 = 1, num2 = 2일 것이다. 이때 num1 > num2(2 ~9)까지 조건이 성립하지 않으므로 for문이 끝날것이고 num1 = 1 인 경우로 돌아와 boolArr[1] 의 값을 false(선택 안한 값)으로 변경해준뒤,

다음 for문으로 num1 값은 2가 될 것이다. 

 

answer에는 부등호의 조건을 만족하는 string들만 들어 있게 될 것이고, 마지막에 sort함수를 통해 정렬 해준 뒤, max 값과 min값을 출력해준다.

 

swift 코드 :

//
//  main.swift
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/03/31.
//

import Foundation

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

func signCheck(_ num1: Character, _ num2: Int, _ sign: String) -> Bool {
    if(sign == "<") {
        if(num1.asciiValue! - 48 > num2) { return false }
    }else {
        if(num1.asciiValue! - 48 < num2) { return false }
    }
    return true
}

func backTracking_sign(_ index: Int, _ s: String){
    if(index == n+1) {
        answer.append(s)
        return
    }
    
    for i in 0...9 {
        if(boolArr[i]) { continue } // 이미 사용한 숫자
        if(index == 0){
            boolArr[i] = true
            backTracking_sign(index+1, "\(s)\(i)") // 다름 자리, 다음 숫자
            boolArr[i] = false
        }else {
            let num1 = s[s.index(s.startIndex, offsetBy: index - 1)]
            let num2 = i
            if(signCheck( num1, num2, signArr[index-1])) {
                boolArr[i] = true
                backTracking_sign(index+1, "\(s)\(i)") // 다름 자리, 다음 숫자
                boolArr[i] = false
            }
        }

    }
}

backTracking_sign(0, "")
answer.sort()

print(answer.last!) //  max 값
print(answer.first!) // min 값