알고리즘

프로그래머스(programmers) 사칙연산 python 정답[동적계획법 풀이]

TheSapper 2023. 2. 7. 02:20
반응형

프로그래머스(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

 

이제 -가 식에 미치는 영향을 분석해보자

  1.  a-(b+c-d) : 식 전체에 영향을 미치는 경우
  2. a-(b+c)-d : 다음 -전까지의 식에 영향을 미치는 경우
  3. 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

 

반응형