99클럽 코테 스터디
오늘의 문제는 굉장히 어렵다. 그래서 필살기를 두개나 쓰기로 했다. 하나는 비기너, 미들러 거르고 챌린저 한 문제만 풀기이고, 다른 하나는 풀이 대충 쓰기이다. 여기에 처음부터 끝까지 모든 발상과 접근과 풀이를 적으려면 두 시간은 걸릴 것 같다. 끝까지 다 쓰고 나서 적는건데, 대충 적는다고 적었는데도 거의 한 시간은 걸렸다...
만약 이해가 안 되는 부분이 있고 궁금한 분이 있으시다면, 댓글이나 99클럽 오픈카톡방에서 물어보시면 따로 설명드리겠다.
챌린저 문제 사칙연산 : https://school.programmers.co.kr/learn/courses/30/lessons/1843#
출처 : 프로그래머스
챌린저 문제 : 사칙연산
풀이 접근
O(n^2) 풀이와 O(n) 풀이 두 가지로 풀었다.
O(n^2) 풀이는 앞에서부터, O(n)풀이는 뒤에서부터 접근한다. 뒤에서부터 접근한다는 발상을 못해서 O(n^2) 풀이로 먼저 풀었는데, 이 쪽이 특히 아주아주 빡셌다.
설명을 대충 적겠다고 했지만, 그래도 코드 설명에 각각 최대한 성의있게라도 써보려 한다...
코드1(Python3, 통과, 최대 2.46ms, 10.5MB)
앞에서부터 순회하는 코드이다. 시간복잡도는 O(n^2)이다.
minus는 지금까지 나온 "-" 부호의 개수이다. 그리고, 마이너스 부호의 개수만큼 괄호를 열 수 있는데, dp[k]는 괄호 k개를 연 상태에서 식의 최댓값이다. 괄호가 홀수 개 열려있으면 그 안에 들어있는 수식은 음수 값을 갖게 되고, 짝수 개(0개 포함) 열려 있으면 양수 값을 갖게 된다.
맨 앞에는 반드시 숫자가 오므로, dp[0]에 arr[0]이 들어있는 상태로 시작한다.
그리고 한번 순회에 부호 + 숫자 한 묶음씩을 살핀다.
1) 음수일 경우 ("-" + 숫자)
minus 카운트를 올리고, 가능한 모든 괄호를 열고 하나도 닫지 않은 경우에 해당하는 값을 dp에 append해준다.
그리고, 0개 초과 minus개 미만의 괄호가 열린 경우는 dp 점화식으로 해결한다. 점화식이 왜 저렇게 생겼는지는... 설명을 생략하겠다. 아무튼 된다.
열린 괄호가 0개인 경우만 따로 해 준다. (열린 괄호가 -1개인 경우는 없으니까)
2) 양수일 경우
괄호가 0개 열린 경우와 모두 열린 경우만 따로 처리하고, 그 사이는 또 점화식으로 처리한다.
TIL을 작성하면서 설명 쓰다가 발견했는데, if minus: 부분은 부호가 플러스일때나 마이너스일때나 불필요한 코드이다. 마이너스 부호가 들어왔을 때는 minus가 1 이상이므로 항상 통과되는 조건이고, 플러스 부호가 들어왔을 때는 for j문에 범위를 0이 아닌 -1까지로 바꿔주면 for문에 포함되는 조건이다.
근데 이상하게 불필요한 부분을 제거하고 제출하면 오히려 실행시간이 늘길래 일단 놔두었다.
answer는 담백하게 dp 리스트의 최댓값이다. 괄호가 몇개 열려있든 다 닫으면 되므로 그 값을 그대로 쓸 수 있다.
def solution(arr):
n = len(arr) // 2
minus = 0
dp = [int(arr[0])]
for i in range(n):
num = int(arr[2 * i + 2])
if arr[2 * i + 1] == '-':
minus += 1
if minus % 2:
dp.append(dp[-1] - num)
else:
dp.append(dp[-1] + num)
for j in range(minus - 1, 0, -1): # j는 열린 괄호의 수
if j % 2: # 열린 괄호가 홀수 개 -> 현재 값이 음수
dp[j] = max(dp[j-1] - num, dp[j] + num, dp[j+1])
else:
dp[j] = max(dp[j-1] + num, dp[j] - num, dp[j+1])
if minus:
dp[0] = max(dp[0] - num, dp[1])
else:
if minus % 2:
dp[-1] -= num
else:
dp[-1] += num
for j in range(minus - 1, 0, -1):
if j % 2:
dp[j] = max(dp[j] - num, dp[j+1])
else:
dp[j] = max(dp[j] + num, dp[j+1])
if minus:
dp[0] = max(dp[0] + num, dp[1])
answer = max(dp)
return answer코드2(Python3, 통과, 최대 0.18ms, 10.4MB)
뒤에서부터 순회하면 훨씬 쉽고 또한 효율적이다. 물론 훨씬 쉽다 한들 점화식이 왜 저렇게 나오는지 하나부터 열까지 설명할 자신은 없다... 그래도 적어두긴 했다.
뒤에서부터 순회하는데, mini는 가능한 최솟값, maxi는 가능한 최댓값, plus는 음수 부호가 나오기 전에 연달아 나온 양수들의 합이다.
양수가 나오면 maxi에 더해주고, plus에도 임시로 값을 더해준다.
마이너스 부호가 나올 때만 mini의 값을 갱신하고, plus는 0으로 초기화시킨다.
mini의 값은 방금 나온 음수를 포함해서 뒤에 붙어있던 양수들(다 합치면 plus의 값)을 음수로 만들 수 있으므로, 해당 경우와 방금 나온 음수 빼고 나머지 뒤의 값의 최댓값(maxi)의 부호를 뒤집는 경우 중 더 최소인 값으로 갱신한다.
maxi의 값도 단순히 maxi에서 해당 수를 빼는 게 아니라, mini의 값을 이용해 수식의 뒷 부분의 부호를 바꾸는 경우도 고려해서 갱신해준다.
맨 앞 숫자(arr[0])는 부호가 안 달린 양수이므로, 그거 빼고 순회한 뒤에 maxi에 맨 앞 숫자를 더해준 게 답이 된다.
def solution(arr):
n = len(arr) // 2
mini = 0
maxi = 0
plus = 0
for i in range(n, 0, -1):
num = int(arr[2 * i])
if arr[2 * i - 1] == '-':
mini, maxi = min(-maxi - num, mini - num - plus), max(maxi - num, -mini - num - plus, mini + plus - num)
plus = 0
else:
plus += num
maxi += num
answer = maxi + int(arr[0])
return answer