23.07.14 파이썬 코딩 퀴즈#265 사칙연산(프로그래머스 스쿨)

이번 문제는 사칙연산 문제이다.

드디어 level 3 문제를 졸업하고, level 4로 넘어왔다.

일단 넘어오긴 했는데, level 3 에서도 삽질을 많이 했던터라... 문제를 보자마자 걱정이 앞선다.

 

해당 문제는 굉장히 심플한 문제이다. 주어지 수식에서 연산 순서를 설정하여 최대값을 도출해내면 된다.

즉, 괄호를 이용하여 연산 순서를 정하고, 해당 연산 순서에 따라 연산을 마친 뒤, 최대값을 찾아 반환하면 된다.

제한사항에 의해 배열의 길이는 항상 3 이상이다. 즉 숫자 2개, 연산부호 하나가 존재하며, 언제나 연산이 가능한 수식이 문자열로 분리되어 주어지게 된다. 그리고 다행스럽게도 연산자는 오직 '+', '-' 만 주어진다.

level 2의 수식 최대화 문제가 생각나는 문제이다.

 

입출력 예 1번은 위 문제 설명에 나와있으므로 입출력 예 2번을 살펴보자

주어진 arr를 나열하면 5 - 3 + 1 + 2 - 4 가 된다. 그리고 이를 순서대로 계산하면 1 을 얻을 수 있다.

5 - ((3 + 1 + 2) - 4)) 처럼 계산하면 3 값을 얻을 수 있으며 이는 해당 수식에서 얻을 수 있는 최대값이 된다.

(5 - 3) + 1 + 2 - 4 반대로 이처럼 계산하게 되면 처음과 같은 1을 얻을 수 있으며,

(5 - (3 + 1 + 2)) - 4 로 계산하면 -5 값을 얻을 수도 있다.

 

문제 해설에서도 설명되어 있지만, 덧셈은 연산 순서에 상관없이 결합법칙이 성립하지만, 뺄셈의 경우 연산 순서에 따라 그 결과값이 바뀌게 된다. 

 

즉 뺄셈을 만나기 전까지 그 값을 최대로 만들어 주면, 문제를 풀이가 가능해 보인다.

입출력 예제 2번을 살펴보자.

뺄셈은 이전값 보다는 그 이후 값들에 영향을 많이 받기 때문에, 수식을 거꾸로 뒤집어볼 필요가 있다.

먼저 4 와 '-' 부호가 등장한다. 앞의 수식의 결과는 현재 알 수 없기 때문에 최대값은 0, 최소값은 -4가 된다.

그 다음 '+','2'를 만나게 된다. 여기에서 최대값은 2, 최소값은 -2가 된다. 그 이유는 2 앞에 어떤 값이 존재할 지 알 수 없기 때문이다.

그리고 다시 '+', '1' 을 만난다. 따라서 최대값은 3, 최소값은 -1이 된다.

그리고 이제 다시 -를 만나게 된다. 즉 앞의 수식들의 최소값을 선택해야 한다.

'-','3'을 만날 경우의 최소, 최대값은 2와 6이 된다.

따라서 수식이 마무리된 '5'를 기점으로 '5-2'를 선택한 3이 최대값이 된다.

위 아이디어를 바탕으로 코드를 작성해 보았다.

먼저 '-'부호가 한개인 경우 순서대로 연산을 하면 되기 때문에 예외처리를 해주었다.

이제 배열을 뒤집고 minmax 를 설정한 다음 반복문을 돌기 시작한다.

그리고 나타나는 정수는 다 합산으로 처리하게 된다.

중요한건 '-' 부호가 등장한 시점이다.

 

입출력 예 2번을 위 코드로 확인해보면

처음 '-' 를 만나는 시점은 arr[2] 에서 만난다.

이미 sub_t 는 8 값을 가지고 있다.

따라서 이 경우 minmax[0] 은 -8을 가지게 되고, 다시 앞서 등장한 정수를 불러와 max 값을 계산하게 된다.

총 두개의 값을 비교하는데, 먼저 구해둔 최소값과 현재까지 누적된 합을 음수로 바꾸는 것( - (8+0))과, '-'부호 이전에 등장한 값을 음수로 바꾼 다음, 현재 누적합에서 이전에 등장한 수를 빼준 값을 더하고, 지금까지 계산된 tempmax 값을 더해준 값(-8 + (8 - 8) + 0) 을 비교하게 된다. 따라서 -8이 최대값을 가지게 된다.

 

그 다음 '-' 기호가 나올때까지 숫자들은 다 더해서 sub_t 에 저장하면 8 이된다.

그리고 minmax 가 [-8, -8]인 상태에서 다시 확인하게 되는데

먼저 최소값(minmax[0])을 살펴보면, 최대값과 현재 누적합을 더한걸 음수로 만드는 경우(-(8+(-8))와 현재 누적합을 음수로 만들고 최소값을 더하는 경우(-8 + (-8)) 중 최소값은 -16 이 된다.

그리고 이제 최대값을 구하기 위해 마지막에 등장한 정수 3을 불러온 다음 연산을 시작한다.

먼저 부분합과 최소값을 더하고 음수를 만드는 경우(-(8+(-8)), 그리고 (-3+(8-3)+(-8)) 경우 두가지 중 최대값 0 이 된다.