백준 1541번 잃어버린 괄호

♣ 문제

 

 

 

♣ 문제 해결 아이디어

여러 가지 숫자와 더하기, 빼기가 섞인 식에서 최솟값을 구하려면 빼기를 최대한 많이 해야 한다. 

그러면 처음에 빼기가 나왔을 때 뒤에 더해지는 수들을 최대한 다 묶어서 빼야 한다. 

 

예를 들어 

55 - 50 + 40에서 빼기 뒤의 50과 40을 괄호로 묶으면 55 - (50+40)이 되어서 90이라는 큰 수를 뺄 수 있다. 

 

다만 이미 앞에 빼기가 한 번 나와서 뒤의 숫자를 묶기 시작했는데 그 중 빼기가 또 한 번 나오면 그 빼기의 앞에서 괄호를 닫아야 한다. 

 

예를 들어 

50 - 5 + 10 + 20 - 30 + 20 이라면 처음에 빼기를 만났을 때 괄호를 열어서 묶기 시작하다가 두 번째 빼기를 만나면 두 번째 빼기 기호 앞에 괄호를 닫아줘야 한다. 그리고 새롭게 괄호를 열어서 다시 뺄 수를 묶는다. 

 

50 - (5+10+20) - (30+20) 

 

그래야 뺄 수를 최대한 크게 만들어서 최솟값을 구할 수 있다. 

 

• 처음으로 빼기 기호를 만나면 괄호를 열어야 한다. ex)   50 - (5+10+20) - (30+20) 
• 열린 괄호가 있는 상태에서 빼기 기호를 또 만나면 빼기 기호 앞에서 괄호를 닫아야 한다.  ex)   50 - (5+10+20) - (30+20) 
• 그리고 빼기 기호 뒤에서는 다시 괄호를 열어서 새로운 큰 뺄셈을 만들기 시작한다.  ex)   50 - (5+10+20) - (30+20) 
• 열어놓은 괄호가 있는데 뒤의 식에서 더 이상 빼기가 나오지 않으면 괄호가 닫히지 않은 채 식이 끝나게 된다. 이런 경우, 끝에서 괄호를 닫아줘야 한다. ex)   50 - (5+10+20) - (30+20) 

 

♣ 코드 아이디어

• 첫 번째 아이디어

첫 번째 아이디어는 '-' 가 나올 때 그 앞 뒤에 특정한 문자를 집어넣는 것이었다. 그렇게 해서 '-'를 만날 때 해당 문자를 괄호로 바꿔치기 하려고 했다. 그냥 괄호를 넣으면 주어진 input의 길이가 달라지기 때문에 for 문에서 에러가 난다. 

 

formula가 55-50+40 이라고 생각하면

result는 -를 만날 때마다 &를 추가하기 때문에 ''55-&50+40" 이 된다. 

 

 

total은 괄호의 갯수를 체크하기 위해 설정했다. total이 홀수면 마지막에 닫는 괄호 ')' 를 추가해야 한다고 생각했다. 

for문을 돌기 시작해서 '-' 기호를 만나면 괄호를 추가할 것이기 때문에 total에 1을 더하고, 여는 괄호와 닫는 괄호 중 무엇을 넣어야 하는지 total을 이용하여 판단하였다. total에 이미 1을 더했기 때문에, 이는 새로운 괄호가 나와야 한다는 것을 의미한다. 따라서 total이 짝수가 아니면 &를 여는 괄호로 바꾸고, total이 홀수면 &를 닫는 괄호로 바꿨다. 

 

그러면 위의 result는 이렇게 나온다. 

 

즉 열린 괄호를 닫지 못하고 끝난다. 따라서 for문을 다 돈 후, total이 홀수이면 괄호가 닫히지 않았다고 판단하여 닫는 괄호를 추가하였다.

 

그리고 정규식과 eval을 사용하여 result를 계산하였다. eval을 사용하면 문자열인 수학식을 계산할 수 있다. 

 

<전체 코드>

 

<결과>

SyntaxError

 

<이유>

SyntaxError가 나오는 이유는 식의 중간에 괄호를 닫는 경우 때문이다. 예를 들어

formula가 '10-20+30-40+50'이면 result가 아래처럼 변한다. 

 

 

&를 '-' 기호의 뒤에만 넣어줬기 때문에 식 중간에 닫는 괄호를 넣을 때 '-' 기호를 괄호로 바꿔치기 하고, 그 뒤에 & 기호가 와서 계산할 수 없는 식이 만들어진다. 

에러가 발생하게 만드는 부분

 

게다가 result[:i]가 아니라 result[i+1]로 했어야 앞의 30이 안 잘리는데 i까지만 가져오니 30이 3으로 바뀌어 버린다 .

 

 

• 두 번째 아이디어

두 번째는 '-' 기호의 뒤에만 & 기호를 추가하지 말고, 앞에도 추가하자는 아이디어였다. 그러면 식 중간에 닫는 괄호를 넣을 때 '-' 기호가 아닌 & 기호와 바꿔치기 하면 된다고 생각했다. 

 

즉, 처음으로 '-' 기호를 만났을 때는 여는 괄호를 넣고, 두 번째로 '-' 기호를 만났을 때는 닫는 괄호를 넣어야 한다. 이때 두 번째 '-' 기호 앞에 있는 & 기호를 닫는 괄호로 바꾸는 것이다. 

그런데 닫는 괄호로 바꾸는 것으로 끝나면 안된다. 왜냐하면 두 번째 '-' 기호를 만났다는 것은 뒤에 나오는 큰 뺄셈을 묶어줘야 한다는 의미이기 때문이다. 

 

문제풀이 아이디어에서 생각했던 이 부분이다. 

닫는 괄호를 넣음과 동시에 새로운 뺄셈을 만들기 위해 여는 괄호를 넣어야 한다 .

 

그래서 닫는 괄호를 넣음과 동시에 여는 괄호를 추가로 넣어서 큰 뺄셈을 만들도록 도와야 한다. 그래서 & 기호를 그냥 닫는 괄호로 바꾸는 게 아니라 여는 괄호를 추가하는 것까지 코드에 넣었다. 

 

 

그런데 이 코드를 실행하면 바뀌지 못한 & 기호들이 남게 된다. 

formula가  '10-20+30-40+50'일 때 result는 아래 과정을 거쳐 바뀐다. 

 

 

그래서 마지막에 &를 없애는 코드를 추가하여 계산했다. 

 

 

<전체 코드>

 

<결과>

틀림

 

<이유>

total 때문인 것으로 생각한다. 원래 괄호를 하나씩 추가하면서 total에 1씩 더했는데, 여기서는 괄호를 한 번에 두 개씩 추가하는 경우가 생겼기 때문이다. 

 

 

• 세 번째 아이디어

total에 괄호의 수를 더하는 게 헷갈린다는 생각이 들어서 totla을 빈 리스트로 정의하고, 괄호가 추가될 때마다 total 리스트에 괄호를 넣기로 했다. 리스트에 있는 마지막 괄호가 '('면 그 다음 괄호는 닫는 괄호를 넣으면 되고, 반대로 리스트에 있는 마지막 괄호가 ')'면 다음 괄호는 여는 괄호를 넣으면 된다. 

 

그리고 result는 빈 문자열로 정의하여 여기에 정답을 한 글자씩 넣기로 함

 

 

input을 formula로 정의한 후, formula를 for문으로 돌면서 문자를 하나씩 result에 넣는다. 그러다가 '-' 기호 차례가 되면 total_list에 들어있는 마지막 괄호가 무엇인지 파악하여 그 다음의 괄호를 result에 넣고, total_list에도 추가한다. 

 

formula를 다 돈 후, result에 아직 괄호가 열려 있는 부분이 있으면 맨 끝에 닫는 괄호를 추가한 뒤 계산한다. 

 

 

<전체 코드>

 

 

<결과>

IndexError

 

<이유>

total_list가 빈 리스트인데, for문에서 total_list의 길이 또는 마지막 인덱스를 다뤄서 인덱스 에러가 발생하는 것으로 예측

 

 

• 최종 아이디어

total_list에서 중요한 것은 마지막 요소가 어떤 괄호이냐는 것이니까 인덱스 에러가 나지 않게 미리 괄호가 아닌 다른 요소를 넣어서 길이 또는 마지막 인덱스를 다룰 수 있게 한다.