[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 해주면 됩니당.

 

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

 

코드

 

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