heheh
히히
heheh
전체 방문자
오늘
어제
  • 히히 (75)
    • AI (14)
      • Model (Study) (3)
      • Model (Paper) (7)
      • Tip! (4)
    • Backend (3)
      • ASP.NET (1)
      • Spring (2)
      • program (0)
      • JAVA (0)
    • Program (11)
      • Docker (3)
      • Github (5)
      • AWS (3)
    • OS (1)
      • Window (1)
      • Linux (0)
    • Python (14)
      • Python Lib (11)
      • Pytorch (1)
      • Tensorflow (1)
      • 크롤링 (1)
    • Spark (3)
      • Scala (2)
      • Pyspark (0)
      • SQL (1)
    • IOS (Swift) (0)
      • 기본 개념 (0)
    • 프로젝트 (3)
      • [AI] GAN (0)
      • [IOS] Swift (3)
      • [AI] 추천시스템 (0)
    • 분석 (1)
    • 알고리즘 풀이 (22)
      • 백준 (22)
    • 기타 (3)
      • 장비세팅 (3)
      • 소개 (0)

인기 글

최근 글

최근 댓글

hELLO · Designed By 정상우.
heheh

히히

알고리즘 풀이/백준

백준 1541번 : 잃어버린 괄호 (Python)

2021. 2. 4. 11:14

문제 : www.acmicpc.net/problem/1541

 

1541번: 잃어버린 괄호

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다

www.acmicpc.net

 

풀이

숫자와 부호를 나누어 리스트를 만든다. (nums, chars)

주어진 부호는 +와 -밖에 없으므로 모든 +를 먼저 한 뒤에 나온 모든 수에 대해 -를 하면 최소값이 나온다.

a-b+c가 있을 때 a-(b+c) = a-b-c가 되기 때문

chars에서 + 부호의 인덱스가 i라면 nums리스트에서 i와 i+1 인덱스의 값을 더해 nums[i]에 저장한다.

이때 이미 더해진 값임을 표시하기 위해 i+1의 값은 -1로 변경하고, 이후 덧셈을 할 때 -1의 숫자를 가지면 인덱스를 하나씩 앞으로 이동하여 전에 더해진 결과값을 찾아 더한다.

모든 덧셈이 끝난뒤 뺄셈을 진행한다.

 

n = input()
nums = list(map(int, re.split("[+-]", n)))
chars = list(re.findall("[+-]",n))

for i in range(len(chars)):
    if chars[i] == '+':
        k = i
        while nums[k] == -1:
            k -= 1
        nums[k] = nums[k]+nums[i+1]
        nums[i+1] = -1

result = 2*nums[0] 
for i in nums:
    if i != -1:
        result -= i

print(result)

'알고리즘 풀이 > 백준' 카테고리의 다른 글

백준 11726번 : 2xn 타일링 (Python)  (0) 2021.02.04
백준 1003번 : 피보나치 함수 (Python)  (0) 2021.02.04
백준 2667번 : 단지번호붙이기  (0) 2021.02.03
백준 11399번 : ATM  (0) 2021.02.01
백준 2579번 : 계단 오르기  (0) 2021.02.01
    heheh
    heheh

    티스토리툴바