[백준] 14888.연산자 끼워넣기 (Swift)

[백준] 14888.연산자 끼워넣기 (Swift)

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

14888번: 연산자 끼워넣기

풀이

백트래킹으로 해결할 수 있는 문제입니다.

 

각 연산자의 개수가 들어있는 배열을 입력받고 나서 백트래킹을 이용해 모든 경우의 수를 탐색합니다.

 

연산자를 이용해 계산한 값과 현재 몇 번째 연산을 진행하는지에 대한 정수를 메소드 인자로 하여 재귀함수를 작성합니다.

 

연산자 배열을 탐색하며 값이 존재한다면 해당 연산자로 연산을 수행합니다. 한번 연산을 수행한 연산자는 값을 1 만큼 감소시킵니다.

 

연산 횟수가 모두 채워진다면, 연산이 끝난 값과 기존에 있던 최대값, 최소값을 비교하여 알맞은 값을 대입합니다.

코드

	import Foundation
	let n = Int(readLine()!)!
	let array = readLine()!.split(separator: " ").map { Int(String($0))! }
	// + - * /
	var operators = readLine()!.split(separator: " ").map { Int(String($0))! }
	var maxVal = Int.min
	var minVal = Int.max
	calculate(array.first!, 1)
	print(maxVal)
	print(minVal)
	// 메소드 선언
	func calculate(_ value: Int, _ index: Int) {
	if index == n {
	maxVal = max(value, maxVal)
	minVal = min(value, minVal)
	return
	}
	for i in 0 ..< 4 {
	if operators[i] == 0 {
	continue
	}
	operators[i] -= 1
	var result = value
	switch i {
	case 0:
	result += array[index]
	case 1:
	result -= array[index]
	case 2:
	result *= array[index]
	case 3:
	result /= array[index]
	default:
	break
	}
	calculate(result, index + 1)
	operators[i] += 1
	}
	}

view raw BOJ_14888.swift hosted with ❤ by GitHub