[알고리즘] BOJ 1541 - 잃어버린 괄호(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy 50문제 풀기

1 / 50(NEW!)

 

탐색 50문제 풀기

0 / 50

 

기초 동적 프로그래밍 50문제 풀기

0 / 50

 

투포인터 10문제 풀기

0 / 10

---

1. 문제

1541번: 잃어버린 괄호 (acmicpc.net)

1541번: 잃어버린 괄호

---

2. 문제 해결 아이디어: Greedy

값을 최소로 만들기 => 빼기 사이에 있는 괄호가 많도록

55 - 50 - 40 => 그냥 두기

55 - (50 + 40) => 묶기

 

-를 모으는 변수 선언 = minus_numbers

• 현재 연산자가 -
  • 만약 이전에 -가 모아져 있었다면 => answer - minus_numbers를 빼주고, minus_numbers에 다음값 넣어주기
  • 아니라면 => minus_numbers에 +
• 현재 연산자가 +
  • 만약 이전에 -가 모아져 있었다면 => minus_numbers에 +
  • 아니라면 => answer - 다음값

---

3. 구현

3.1. 내 풀이

      

      

      

    
    

      <python />
    

import re
import sys
input = sys.stdin.readline

PLUS = '+'
MINUS = '-'

input_data = input().strip('\n')
numbers = list(map(int, re.split('[+|-]', input_data))) # 숫자만 분리
operators = list(re.findall('[+|-]', input_data)) # 연산자만 분리

minus_number = 0 # 현재 쌓여 있는 - 값
answer = numbers[0]

for i, oper in enumerate(operators) :
  if oper == MINUS :
    if minus_number != 0 :
      answer -= minus_number
      minus_number = numbers[i+1]
    else :
      minus_number += numbers[i+1]
  else :
    if minus_number != 0 :
      minus_number += numbers[i+1]
    else:
      answer += numbers[i+1]
else :
  if minus_number != 0 :
    answer -= minus_number
  
print(answer)

 

3.2. 다른 사람 풀이

      

      

      

    
    

      <python />
    

exps = input().split('-') # - 기준으로 split해서 리스트에 저장

answer = 0

for i, exp in enumerate(exps) :
    cnt = sum(list(map(int, exp.split('+')))) # + 기준으로 분리후, 모든 값 더하기
    if i == 0: # 첫 번째이면
      answer = cnt
    else :
      answer -= cnt
  
print(answer)

예를 들어 50 - 80 + 70 - 60 + 90 이라고 할 때

50 - (80 + 70) - (60 + 90) 이 최대가 된다.

-를 기준으로 분리, 그 다음 + 끼리 저장한다. 라는 느낌.

---

4. 메모

걸린 시간

• 총 53분

Python 문법

• enumerate
  
  • for문에서 list의 index와 값 동시에 접근하고 싶을때 사용
• re
  • 정규 표현식으로 list를 분리할 때 사용
  • split에 정규 표현식을 넣어서 두 가지 이상의 구분자로 list를 분리할 수 있음
  • findall을 사용해서 문자열에서 해당 정규 표현식에 해당되는 것만 찾을 수 있음

---

5. 마치며

그동안 너무 코딩테스트를 안했구나 + 내가 너무 어렵게 구현했다..

곧 다시 페이스 찾을 수 있겠지 아자자ㅏ자아