[Swift] 프로그래머스 - 수식 최대화

문제

https://programmers.co.kr/learn/courses/30/lessons/67257

계산식을 문자열로 입력받아 계산을 하는데,

연산자 우선순위(같은경우는 없고 다 달라야함)에 따라 계산값이 달라지는데,

이 중 최댓값을 출력하는 문제.

문제 규칙상 계산식의 결과가 상금임으로 음수가 나올 경우 절댓값으로 계산.

 

접근 방법

위 문제를 풀려면 우선 사칙연산을 할 줄 알아야 한다. 사칙연산 문제에서 연산자 우선순위가 추가된 문제.

 

사칙연산을 풀려면 연산자 우선순위에 따라 계산하기 편한 후위 표기법으로 변경하여 풀 수있다. 즉

 

1. 식을 Stack을 사용해서 후위 표기법으로 변경
2. 후위 표기법 계산 방법을 Stack을 사용해서 풀이

과정을 통해 풀 수 있다.

식을 후위 표기법으로 변경 방법

var stack = [] // 연산을 위한 스택

var result = [] // 출력값

// 가 있다는 가정하에,

for c in input {

  // ...

}

for문을 돌리면서 식을 하나하나 스캔해 나가면서 아래 과정을 진행.

1. 괄호가 있는 식일 경우

• ( 를 만나면 스택에 푸쉬
• ) 를 만나면 스택에서 (가 나올 때까지 pop 하여 출력(result)하고, (는 버린다.
• 피연산자는 그냥 출력(result)한다.
• 연산자를 만나면 (중요!!)
• stack이 비어있으면 stack에 넣어주고,
• 아니라면 c(for문을 돌면서 접근된 연산자값)의 우선순위가 스택의 맨 위의 연산자(stack.peek)보다 낮은 우선순위 연산자를 만날 때 까지 계속 pop 해준다. 위 과정 이후 자기자신(c값)을 stack에 push 한다.
• 모든 입력이 끝나면(for문을 다 돌았으면) 남은 stack 연산자를 모두 pop하여 result에 출력한다.(reverse를 해줘도 똑같다.)

 

2. 괄호가 없는 식일 경우

위 방법에서 괄호 부분만 무시하고 아래 방법 규칙 그대로 작성해주면 된다. 이 문제는 괄호가 없기 때문에..

 

이렇게 하면 후위 표기법으로 식이 바뀌게 된다.

예) A+B*C -> ABC*+

처음엔 이게 뭔식인가.. 싶겠지만 위 식을 stack으로 풀면 눈에 확 들어올 것이다.

 

그럼 다음은 후위 표기법으로 바꾼 식을 계산하는 방법에 대해 알아보겠습니다.

 

Stack을 사용한 후위 표기법 계산

func cal(_ 후위표기법계산식: [String]) -> Int {
  var stack = [] // 연산에 사용할 stack
  for b in 후위표기법계산식 {
    ...
  }
}

• 숫자를 만나면 stack에 push
• 연산자를 만나면 stack에서 pop을 2번 하여(v1, v2) 두 수를 연산(b에서 나온 연산자로)하여 다시 stack에 push

 

위 과정을 반복하다 보면 결국 stack은 계산값 하나만 남게 되고, 이 값은 return 해주면 됩니당.

 

이렇게 해서 괄호연산을 연산자 우선순위를 바꿔가면 계산한 값 중 최대값을 출력해주면 되는 문제입니다. 저는 연산자 우선순위는 딕셔너리를 사용해서 판단하였습니당.

 

코드

 

	import Foundation
	func solution(_ str: String) -> Int {
	let cmds: [[Character:Int]] = [
	["+":1, "-":2, "*":3],
	["+":1, "-":3, "*":2],
	["+":2, "-":1, "*":3],
	["+":2, "-":3, "*":1],
	["+":3, "-":2, "*":1],
	["+":3, "-":1, "*":2]
	]
	var max = 0
	for cmd in cmds {
	let convertedStack: [String] = convert(str, cmd)
	max = [max, abs(cal(convertedStack, cmd))].max()!
	}
	return max
	}
	func cal(_ convertedStack: [String], _ cmd: [Character: Int]) -> Int {
	var stack: [Int] = []
	for b in convertedStack {
	if let num = Int(b) {
	stack.append(num)
	} else {
	// 연산
	if let v2 = stack.popLast(), let v1 = stack.popLast() {
	var tmp = 0
	switch b {
	case "+":
	tmp = v1 + v2
	case "-":
	tmp = v1 - v2
	case "*":
	tmp = v1 * v2
	default:
	print("err")
	}
	stack.append(tmp)
	}
	}
	}
	return stack[0]
	}
	func convert(_ str: String, _ cmd: [Character: Int]) -> [String] {
	var stack: [Character] = []
	var result: [String] = []
	var tmp: [Character] = []
	for c in str {
	// 연산자인지 확인
	if c.isNumber {
	tmp.append(c)
	} else {
	result.append(String(tmp))
	tmp.removeAll()
	// 연산자 우선순위 확인
	if stack.isEmpty {
	stack.append(c) // 비어있을때만 넣어줌
	}
	else {
	let ipt = cmd[Character(extendedGraphemeClusterLiteral: c)]!
	while let last = stack.last, let inside = cmd[last], inside >= ipt {
	result.append(String(stack.removeLast()))
	}
	stack.append(c)
	}
	}
	}
	if !tmp.isEmpty {
	result.append(String(tmp))
	tmp.removeAll()
	}
	result += stack.reversed().map{String($0)}
	return result
	}
	let a = "100-200*300-500+20"
	let rs = solution(a)
	print(rs)

view raw 수식최대화.swift hosted with ❤ by GitHub

항상 사칙연산 문제 풀때마다 검색했었는데 이번에 재대로 정리해보네요 ㅠㅠ