[Greedy,String] Sliver 2 1541 잃어버린 괄호

문제

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

---

설계  및 코드 ✨

1.  첫번째 시도

마이너스를 위주로 생각하자는 아이디어는 떠올랐는데, 예외가 있을 것 같아서

가장 기본적으로 하나씩 괄호를 다 넣어서 가장 최소값을 찾는 방식 선택  

 

● 문제 발생 

1. 문자열일 때 숫자 계산?

1- 해결 - eval() 함수 사용 

2. 문자열에 문자열을 삽입하고 싶을 때?

2- 해결 - 문자열[:4] + '(' + 문자열[5:8] + ')' 이런 식으로 

3. 예제 입력 3: 숫자 앞에 0이 있는 경우 처리?

3- 해결 - str(int()) 사용

 

최종적인 중요 문제발생 

반례: 0-100+50-100+50-100

괄호를 2개, 3개 ... 여러개 쓸 수 있는 경우 발생

하나씩 일일히 괄호를 삽입하는 것은 무리가 있음을 파악 

 

# 실버2 1541 잃어버린 괄호

# 예제 입력1 : 55-(50+40) = -35
# 숫자를 자를 수는 없음
# 마이너스를 위주로? 예외가 있을 수 있으므로 일단 다 해보기
# 파이썬으로 문자열 계산하기 -> eval()


num_str = input()
index_list = [-1]
number_str = ""
before_indx = 0

for i in range(len(num_str)):
  # 예제 입력3 숫자 앞에 0이 있는 경우 처리
  if num_str[i] == '+' or num_str[i] == '-':
    number_str += str(int(num_str[before_indx:i])) + num_str[i]
    before_indx = i+1

  elif i == len(num_str)-1:
    number_str += str(int(num_str[before_indx:i+1]))


print(number_str)  
minValue = eval(number_str)



for i in range(len(number_str)): 
  if number_str[i]=='-' or number_str[i] == '+':
    index_list.append(i)



index_list.append(len(number_str))


for num in range(len(index_list)):
  i = index_list[num]
  for j in index_list[num+1:]:
    # 문자열에 문자열을 삽입하고 싶을 때 이렇게 사용 
    new_str = number_str[:i+1] + '(' + number_str[i+1:j] + ')' + number_str[j:]
    print(new_str)

    if minValue >= eval(new_str):
      minValue = eval(new_str)

   

print(minValue)


# 반례 존재 -> 0-100+50-100+50-100 : 괄호를 2개,3개... 여러개 쓸 수 있는 경우 
# 하나씩 일일히 괄호를 찾는 것은 무리가 있음을 파악
# 다른 방법? 전에 생각했던 마이너스를 위주로 생각해보자 -> 마이너스 기준으로 split?

 

 

전에 생각했던 마이너스를 위주로 생각해보자 

마이너스 기준으로 split하자! 

 

2.  두번째 시도

마이너스로 split하기 -> -(100+80) 이렇게 계산하는게 가장 최소값이기 때문!

eval을 사용했을 때랑 안 사용했을 때 나눠서 함

eval: 보안, 디버깅, 안정성에 어려움이 있다

 

# 실버2 1541 반례 발생 -> 다른 방법으로 시도
# 마이너스로 split하기 -> -(100+80) 이렇게 있는 게 가장 최소값
# eval 안쓰고 하기

number_str = input().split('-')

for i in range(len(number_str)):
  if '+' in number_str[i]:
    # plus 로 연결된 것들 먼저 계산
    plus_list =  list(map(int,number_str[i].split('+'))) # list 원소 str -> int
    number_str[i] = str(sum(plus_list))

# print(number_str)

# eval 사용x
value = int(number_str[0])
for num in number_str[1:]: 
  value -= int(num)

print(value) 



# eval 사용
# number_str = "-".join(number_str)
# print(eval(number_str))