프로그래머스(programmers) 사칙연산 python 정답[동적계획법 풀이]
프로그래머스(programmers) 사칙연산 python 정답[동적계획법 풀이]
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/1843
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 정답
def solution(arr):
arrs = ''.join(arr).split('-')
val0 = sum(list(map(int, arrs[0].split('+'))))
if len(arrs) == 1:
return val0
min_val = 0
max_val = 0
for arr in arrs[:0:-1]:
x = list(map(int, arr.split('+')))
min_val, max_val = min( -(sum(x)) + min_val, -(sum(x)) - max_val), \
max(-(sum(x)) - min_val, - x[0] + sum(x[1:]) + max_val)
return val0 + max_val
문제 해설
해당 문제는 상당히 어려운 편이다
arr의 예시 데이터는 다음과 같다.
["1", "-", "3", "+", "5", "-", "8"]
우리는 해당 문제를 이렇게 생각해 볼 수 있다.
- -로 묶인 + 만 포함한 표현식
따라서 일단 배열을 join하여 스트링으로 만들고 -를 기준으로 쪼갠다.
그러면 각 행은 -로 연결된 것과 마찬가지다.
즉, 이제 리스트의 각 항목은 +만을 포함한 표현식이 된다.
['1', '3+5', '8']
아래는 해당 부분을 처리하는 코드다.
arrs = ''.join(arr).split('-')
val0 = sum(list(map(int, arrs[0].split('+'))))
# 만약 -가 없으면 길이는 1
if len(arrs) == 1:
return val0
이제 -가 식에 미치는 영향을 분석해보자
- a-(b+c-d) : 식 전체에 영향을 미치는 경우
- a-(b+c)-d : 다음 -전까지의 식에 영향을 미치는 경우
- a-(b)+c-d : -바로 뒤의 숫자에만 영향을 미치는 경우
그리고 이전 결과의 최대, 최소값이 그 다음 -를 만났을 때 어떻게 영향을 미치는지 분석해보자
일단, -가 등장할 때마다, 영향을 미치는 식들의 부호가 반전된다
양의 최대값이 -를 만나면 최소값으로, 음의 최소값이 -를 만나면 최대값이 된다.
최솟값을 만드는 경우는 다음과 같다. (sum은 이전 처리에 의해 양수다)
- (1) -(sum(x)+최대)
- (2) -(sum(x))+최소
이를 식으로 옮기면 다음과 같다.
min_val = min( -(sum(x)) + min_val, -(sum(x)) - max_val)
최대값을 만드는 경우는 다음과 같다. (음수를 최대한 작게)
- (1) -(sum(x)+최소)
- (3) -x[0] + sum(x[1:]) + 최대
이를 식으로 옮기면 다음과 같다.
max_val = max(-(sum(x)) - min_val, - x[0] + sum(x[1:]) + max_val)
실제로 루프 내에서는 이전 이터레이션의 결과를 사용해야 하므로,
각행을 순서대로 처리하면 min_val이 먼저 갱신되어 오류가 발생한다.
따라서 튜플처리를 해주자.
참고
https://tiktaek.tistory.com/33
[프로그래머스] 코딩테스트 연습 - 사칙연산(Python)
코딩테스트 연습 - 사칙연산 [찾아라 프로그래밍 마에스터] 풀이 저는 개인적으로 정말 어려웠던 문제였습니다. 처음 시도했던 방법은 순열이었습니다. 풀다가 생각해보니 순열로 풀려면 모든
tiktaek.tistory.com