haju__log

[python][백준/BOJ] 1541번 : 잃어버린 괄호 본문

BOJ_백준

[python][백준/BOJ] 1541번 : 잃어버린 괄호

haju 2023. 7. 27. 16:38
반응형

https://www.acmicpc.net/problem/1541

 

1541번: 잃어버린 괄호

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

www.acmicpc.net

 

✅ 문제 풀이

  • 최솟값을 만들기 위해서는 최대한 큰 수를 빼줘야 한다.
  • 덧셈으로 이루어진 부분을 먼저 계산한 후 빼주게 되면 최솟값을 만들 수 있음!
  1. 따라서 덧셈 부분을 먼저 계산하기 위해 뺄셈 기준으로 문자열을 분리한다.
  2. 분리된 문자열을 각각을 보며 덧셈이 있다면 계산한다.
  3. 덧셈 계산이 완료된 값들을 모두 뺄셈해준다.

틀린 코드

  • 예제는 다 맞았으나, '틀렸습니다'
  • 반례 : 6-3+5+6-8
  • 이유 : 덧셈계산을 해줄 때, hap=num 으로 그냥 대입을 해줬다.
  • a+b 처럼 피연산자가 2개인 경우는 계산에 문제가 없지만,
  • a+b+c 처럼 피연산자가 3개 이상일 경우부터 문제가 생김!
  • hap+=num으로 바꾸면 바로 해결됨~
import sys

#식 입력받기
l=sys.stdin.readline().strip()
# '-' 문자 기준으로 문자열을 자른다.
l=l.split('-')
#만약 l의 길이가 1이라면 -가 없다는 뜻이므로
# + 계산만 하면 된다.
if len(l)==1:
    l=''.join(l) #리스트에서 다시 문자열로 저장해주고
    l=l.split('+') # '+' 문자 기준으로 문자열을 자른다.
    result=int(l[0])
    for i in range(1,len(l)): #전체 숫자들을 더하는 과정
        result+=int(l[i])
else: #문자열에 '-'가 있을 경우의 계산과정
    fl=[] # + 연산이 계산된 값을 저장할 최종 리스트
    for i in l: #기존 값들이 저장된 l 리스트를 돌면서
        # '+' 연산자가 있을 경우
        if '+' in i:
            hap=0 # + 연산을 해서 저장해줄 변수
            num=0 # 숫자만 저장할 변수
            for j in i:
                if j =='+': #반복문을 돌면서 +를 만날경우에
                    hap=num #hap에 + 만나기전 숫자를 저장하고
                    num=0 #숫자 저장 변수는 초기화 해준다.
                else: # 문자가 + 가 아니라면
                    num *= 10 #num에다가 숫자를 저장한다.
                    num+=int(j)

            hap+=num #최종 더한 값을 저장하고
            fl.append(hap) #fl 리스트에 값을 추가한다.
        else: # '+' 연산자가 없을 경우 바로 fl에 값을 추가한다.
            fl.append(i)
    #최종 - 계산을 해주는 과정
    result=int(fl[0])
    for i in range(1,len(fl)):
        result-=int(fl[i])
print(result)

ans : -16 인데 output : -13 인 것을 볼 수 있다.

 

✅ 최종 코드

import sys

#식 입력받기
l=sys.stdin.readline().strip()
# '-' 문자 기준으로 문자열을 자른다.
l=l.split('-')
#만약 l의 길이가 1이라면 -가 없다는 뜻이므로
# + 계산만 하면 된다.
if len(l)==1:
    l=''.join(l) #리스트에서 다시 문자열로 저장해주고
    l=l.split('+') # '+' 문자 기준으로 문자열을 자른다.
    result=int(l[0])
    for i in range(1,len(l)): #전체 숫자들을 더하는 과정
        result+=int(l[i])
else: #문자열에 '-'가 있을 경우의 계산과정
    fl=[] # + 연산이 계산된 값을 저장할 최종 리스트
    for i in l: #기존 값들이 저장된 l 리스트를 돌면서
        # '+' 연산자가 있을 경우
        if '+' in i:
            hap=0 # + 연산을 해서 저장해줄 변수
            num=0 # 숫자만 저장할 변수
            for j in i:
                if j =='+': #반복문을 돌면서 +를 만날경우에
                    hap+=num #hap에 + 만나기전 숫자를 저장하고
                    num=0 #숫자 저장 변수는 초기화 해준다.
                else: # 문자가 + 가 아니라면
                    num *= 10 #num에다가 숫자를 저장한다.
                    num+=int(j)

            hap+=num #최종 더한 값을 저장하고
            fl.append(hap) #fl 리스트에 값을 추가한다.
        else: # '+' 연산자가 없을 경우 바로 fl에 값을 추가한다.
            fl.append(i)
    #최종 - 계산을 해주는 과정
    result=int(fl[0])
    for i in range(1,len(fl)):
        result-=int(fl[i])
print(result)

ans와 output 동일!

반응형