본문 바로가기

IT/Programming problems

[프로그래머스] 코딩테스트 예제 '사칙연산' Solution in Swift

문제 출처

 

코딩테스트 연습 - 사칙연산

[5, -, 3, +, 1, +, 2, -, 4] 3

programmers.co.kr

 


문제 

사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다.
예를 들어 식 1 - 5 - 3은 연산 순서에 따라 다음과 같이 다른 결과를 가집니다.

  • ((1 - 5) - 3) = -7

  • (1 - (5 - 3)) = -1

위 예시와 같이 뺄셈은 연산 순서에 따라 그 결과가 바뀔 수 있습니다.
또 다른 예로 식 1 - 3 + 5 - 8은 연산 순서에 따라 다음과 같이 5가지 결과가 나옵니다.

  • (((1 - 3) + 5) - 8) = -5

  • ((1 - (3 + 5)) - 8) = -15

  • (1 - ((3 + 5) - 8)) = 1

  • (1 - (3 + (5 - 8))) = 1

  • ((1 - 3) + (5 - 8)) = -5

위와 같이 서로 다른 연산 순서의 계산 결과는 [-15, -5, -5, 1, 1]이 되며, 이중 최댓값은 1입니다.
문자열 형태의 숫자와, 더하기 기호(+), 뺄셈 기호(-)가 들어있는 배열 arr가 매개변수로 주어질 때, 서로 다른 연산순서의 계산 결과 중 최댓값을 return 하도록 solution 함수를 완성해 주세요.

제한 사항

  • arr는 두 연산자 +, - 와 숫자가 들어있는 배열이며, 길이는 3 이상 201 이하 입니다.

    • arr의 길이는 항상 홀수입니다.

    • arr에 들어있는 숫자의 개수는 2개 이상 101개 이하이며, 연산자의 개수는 (숫자의 개수) -1 입니다.

    • 숫자는 1 이상 1,000 이하의 자연수가 문자열 형태로 들어있습니다.. (ex : 456)

  • 배열의 첫 번째 원소와 마지막 원소는 반드시 숫자이며, 숫자와 연산자가 항상 번갈아가며 들어있습니다.

입출력 예

array

reulst

[1, -, 3, +, 5, -, 8]

1

[5, -, 3, +, 1, +, 2, -, 4]

3

입출력 예시

입출력 예 #1
위의 예시와 같이 (1-(3+(5-8))) = 1 입니다.

입출력 예 #2
(5-(3+((1+2)-4))) = 3 입니다.

 


Point

1. 입력된 식에서 숫자 뒤 혹은 앞에 식이 유요한 범위 내에서 괄호를 개수와 상관없이 넣을 수 있을 때, 출력될 수 있는 결과의 최대 값을 구하는 문제이다.

 


Solution Tip

  - 순열과 같이 풀수 있다.

  - 연산은 A - or + B 형태로 나타낼 수 있고 A와 B는 괄호로 묶여있거나 안묶여있을 수 있다.

  - 예를 들어 X - Y - Z 라는 식이 있을 때 첫 값부터 시작하며 결과를 배열에 저장할 때 이런 진행이 될 수 있다.

 

1. X

    [(X, X)]

 

2. X - Y

    [(X, X)] , [(Y, Y)] 

    [(X, X), (max(X-Y), min(X-Y)) ] , [(Y, Y)]        

// [0][1] 값은 [0][0] - [1][0] 에서 구할 수 있다.

 

3. X - Y - Z

    [(X, X), (max(X-Y), min(X-Y))] , [(Y, Y)] , [(Z, Z)]

    [(X, X), (max(X-Y), min(X-Y))] , [(Y, Y),  (max(Y-Z), min(Y-Z))] , [(Z, Z)]

    [(X, X), (max(X-Y), min(X-Y)), (max(X-Y-Z), min(X-Y-Z))] , [(Y, Y),  (max(Y-Z), min(Y-Z))] , [(Z, Z)]

 

 // [0][2] 값은 [0][1] - [2][0] 과 [0][0] - [1][1] 의 최대값과 최소값. 즉, (X - Y) - Z 와 X - (Y - Z) 중 최대값과 최소값이다.

 

 - 저장된 값의 배열을 볼때 이렇다.  [(X), (X - Y), (X - Y - Z)] , [(Y), (Y - Z)], [(Z)]

 

 - 인덱스의 값이 2개인 이유는 최대값과 최소값 경우이며 마이너스 뒤에 괄호가 올 때는 최소값이 최대값이 되고, 최대값이 최소값이 될 수 있으므로 문제 답인 최대값을 구하기 위해서는 두 경우 다 저장, 계산해보아야 한다.

 


Solution