[백준1541번] 잃어버린 괄호

문제 링크 >> https://www.acmicpc.net/problem/1541

 

 

📋 문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다.

그리고 나서 세준이는 괄호를 모두 지웠다.

세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

 

 

👉 입력

첫째 줄에 식이 주어진다.

식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다.

그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다.

수는 0으로 시작할 수 있다.

입력으로 주어지는 식의 길이는 50보다 작거나 같다.

 

 

👈출력

첫째 줄에 정답을 출력한다.

 

 

💡 사용된 개념

eval()

문자열로 이루어진 수식을 인자로 받아 계산된 결과를 숫자로 반환한다.

 

 

📝 풀이

❌ 첫 번째 풀이

inp = input()
arr = []

i = 0
while i < len(inp):
  if inp[i] == '-':
    arr.append(inp[i])
    string = ""
    num = 0
    copyinp = inp[i+1:]
    for j in range(len(copyinp)):
      if(copyinp[j] == "-"):
        num = j+1
        break;
      else:
        string += copyinp[j]
        if(j == len(copyinp)-1):
          num=j+1
    arr.append(str(eval(string)))
    i += num
  else:
    arr.append(inp[i])
  
  i += 1
print(eval(''.join(arr)))

 

문제를 풀 때 처음 생각했던 것은 입력을 숫자와 기호를 구분해 나누는 것이었다.

그리고 생각한 풀이의 내용은 다음과 같다.

1. 입력받은 문자열을 inp에 저장하고 각 문자를 순회한다.
2. + 기호이거나 숫자일 경우에는 arr에 추가한다.
3. - 기호를 만났을 때에는 - 기호 뒤에 있는 나머지 문자열을 copyinp에 저장한다.
   1. copyinp 안에서 - 기호를 만나거나 copyinp 문자열의 끝에 도달할 때까지 for문을 통해 각 문자를 살핀다.
      1. 해당 문자가 문자열의 끝이 아니고 - 기호도 아닐 경우 문자열 string에 더한다.
      2. 해당 문자가 - 기호일 경우 인덱스 번호 + 1을 num에 저장한다.
      3. 해당 문자가 문자열의 끝일 경우 string에 더한 뒤 인덱스 번호 + 1을 num에 저장한다.
   2. 반복이 끝났다면 sting에는 숫자 혹은 숫자+숫자의 문자열이 들어있으므로 계산한 후 다시 문자열로 바꿔 arr에 넣는다.
   3. 진행된 결과만큼 i에 num을 더해 살필 인덱스 번호를 조정한다.
4. inp의 순회가 끝났다면 arr을 join 연산을 통해 문자열로 바꾼 후 eval()로 계산한다.

 

해당 코드로는 예제 1, 예제 2는 답이 나오지만 예제 3은 풀 수 없었다.

또한 다시 생각해보니 - 기호가 다시 등장할 때에 대한 풀이도 두지 않아 예제 1에서 - 연산이 더 추가되면 엉뚱한 답이 나왔다.

 

✅ 두 번째 풀이

inp = input()
arr = inp.split('-')
result = 0

if len(arr) == 1:
  print(eval(inp))
  
else:
  for i in arr[0].split('+'):
    result += int(i)
  
  for i in arr[1:]:
    for j in i.split('+'):
      result -= int(j)
  print(result)

 

첫 번째 풀이의 코드를 다시 살펴봤을 때 -가 등장하는 경우와 그렇지 않은 경우로 나누고 있었다.

따라서 이 부분에 대해 아예 입력받은 것을 split으로 나누면 어떨까 생각했다.

 

위 코드의 풀이 과정은 다음과 같다.

1. 입력받은 문자열을 - 기호를 기준으로 나눈 것을 arr에 저장한다.
2. arr[0]에는 숫자 혹은 숫자+숫자가 들어간다. 따라서 이를 + 기호를 기준으로 나눈 뒤 모두 더한다.
3. arr[1: ]에는 숫자 혹은 숫자+숫자들이 들어있다. 따라서 이들을 순회하며 + 기호를 기준으로 나눈 뒤 모두 빼준다.

3 에서 모두 빼주는 이유는 A - ( B + C ) 는 A - B - C 와 같기 때문이다.

 

입력이 - 기호 없이 + 만 있을 경우에 대해 arr의 길이가 1이면 바로 계산해 버리는 분기점을 두었는데 다시 생각해보니 안 넣어도 제대로 동작한다.

 

 

 

 

🔍 참조

eval https://docs.python.org/3/library/functions.html?highlight=eval#eval