[TIL_Carrotww] 103 - 23/03/06

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 programmers 연속 펄스 부분 수열의 합 - level3

약 일주일만에 til을 쓰는거같은데 면접 준비와 코테 준비때문에 알고리즘을 풀기는 했지만 올리지는 못했다 ㅠㅠ

여러 코딩테스트를 보며 나의 약점을 찾은 결과 dp, simulation, dfs 에서 좀 약했다.
앞으로 위 3가지 유형을 위주로 풀려고 한다.

• 문제
  dp 문제임을 알았지만 dp 점화식을 찾는게 어려워 일단 brute force로 풀어보았다.
• 첫 번째 풀이

def solution(sequence):
    result = sum(sequence)
    total = result
    max_idx = 0
    max_val = 0
    for idx, val in enumerate(sequence):
        if abs(val) > max_val:
            max_idx, max_val = idx, abs(val)

    left, right = max_idx, max_idx

    if sequence[max_idx] < 0:
        # 제일 큰 값이 음수일때부터
        c_left, c_right = 1, 1
        while left != 0 or right != len(sequence) - 1:
            if left > 0:
                left -= 1
                if c_left == 1:
                    total = total - sequence[left] + (sequence[left] * c_left)
                    c_left *= -1
                else:
                    total = total - sequence[left] + (sequence[left] * c_left)
                    c_left *= -1
                result = max(result, total)

            if right < len(sequence) - 2:
                right += 1
                if c_right == 1:
                    total = total - sequence[right] + (sequence[right] * c_right)
                    c_right *= -1
                else:
                    total = total - sequence[right] + (sequence[right] * c_right)
                    c_right *= -1
                result = max(result, total)
    else:
        c_left, c_right = -1, -1
        while left != 0 or right != len(sequence) - 1:
            if left > 0:
                left -= 1
                if c_left == 1:
                    total = total - sequence[left] + (sequence[left] * c_left)
                    c_left *= -1
                else:
                    total = total - sequence[left] + (sequence[left] * c_left)
                    c_left *= -1
                result = max(result, total)

            if right < len(sequence) - 2:
                right += 1
                if c_right == 1:
                    total = total - sequence[right] + (sequence[right] * c_right)
                    c_right *= -1
                else:
                    total = total - sequence[right] + (sequence[right] * c_right)
                    c_right *= -1
                result = max(result, total)

    return result

맨 첫 번째 인덱스가 음수로 시작, 양수로 시작하는 경우로 나누어 주고 가장 큰 값의 인덱스에서 시작하며 큰 값을 갱신해 나가는 방식으로 진행했다.
풀면서 문제점은 알고있었지만 일단 해보았다.
큰 값 위주로 풀게되면 큰 값이 여러개 있을때의 경우는 체크하지 못해 안풀린다.

• dp 풀이
  이 문제를 근본적으로 이해하고 dp로 풀이한 풀이이다.

def solution(sequence):
    dp1 = [0] * len(sequence)
    dp2 = dp1[::]

    dp1[0] = sequence[0]
    dp2[0] = -sequence[0]

    for i in range(1, len(sequence)):
        dp1[i] = max(dp2[i-1]+sequence[i], sequence[i])
        dp2[i] = max(dp1[i-1]-sequence[i], -sequence[i])

    return max(max(dp1), max(dp2))

리스트를 두 개 만들어 준 후 첫 번째 방식과 같이 하나는 음수, 하나는 양수로 시작하며 지금 양수 리스트 자리를 갱신해야 한다면 음수 리스트의 전 인덱스의 값과 max를 봐 가며 갱신해 나가면 된다.

역시 이해를 하고 보면 쉽기는 하다.