Baekjoon 1541번 잃어버린 괄호

Baekjoon 1541번 잃어버린 괄호

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

Contents

1. Problem

2. Error & Fail

3. Solution

4. My Code

5. Other's Code

6. Shortest Code

==============================================


1. Problem

1. 양수, +, -, (, ) 5가지로 구성된 최대 50 길이의 식을 만들었다. 그러나 괄호를 모두 지웠다. => 양수, +, - : 3가지로만 구성된 식이 입력으로 주어진다.
2. 적절한 괄호를 쳐서 입력값의 식이 최소가 되도록 만든다.
3. 처음과 마지막은 숫자이다.
4. 연속해서 연산자를 사용하지 않으며 숫자는 5자리를 넘지 않는다.
5. 수는 0으로 시작할 수 있다.

2. Error & Fail

2-1) Operator +, -
우선 type('+') 는 str이지만 operator +,- 는 그 어디에도 속하지 않는다.
즉 +를 무언가로 입력받고 싶지만 사실 operator는 앞과 뒤에 인자가 존재해야만 의미가 있기때문에  다음과 같이 형성될 수 밖에 없다. 

int1 + int2 = 계산된 int 
int1 - int2 = 계산된 int 
str1 + str2 = str1str2
str1 - str2 = 존재할 수 없음

참고로 -는 같은 operator이니 동일하다. 다만 str-str은 존재할 수 없다. 때문에 다음과 같은 에러가 뜬다.
TypeError: unsupported operand type(s) for -: 'str' and 'str'

2-2) Eval 
+는 '+'로 밖에 존재할 수 없다면 우리는 eval python 내장함수를 사용해야한다.
eval(equation) = equation 결과값이 나오기 때문에 사용이 가능하다.
그러나 여기서도 문제가 있다.
바로 eval('3+4')와 같은 수식적으로는 문제가 없는 것에서는 바로 계산 결과를 받지만
eval('03+04')와 같이 앞의 숫자에 0이 붙으면 그것은 계산이 불가능하다.
이것이 많은 사람들이 틀린 이유이기도 하다.


2-3) 정수가 아닌 문자를 골라내는 방법
'55-50+30'에서 +나 -를 하나의 문자를 구분하고자 할 때 필요했던 것은 str.isdigit()이었지만 나는 기억이 나지않아 일일이 if c[i] == '+' or c[i] == '-':와 같이 구분할려고 애를 썻지만 간단하게도 str.isdigit()으로 Bool 계산이 가능했다.

2-4) 괄호를 칠 수 있다는 궁극적인 의미
이 문제를 처음 접하고 괄호를 치면되는거지하고 바로 시작해서 list에 '정수', '+', '-' 형태의 string으로 분류할려고 할 것이고 그 다음으로 +나 - 앞에는')'를 뒤에는 '('를 넣을려고 시도했을 수도 있다.
참고로 이것은 내가 그랬다.
결과적으로 다음과 같은 순서의 코드를 짰다.

'55-50+30' => ['55', '-', '50', '+', '30']
다른 list에 append or insert
[['(', '55', '-', '50', ')', '+', '30'],
 ['(', '55', '-', '50', '+', '30', ')'],
 ['55', '-', '(', '50', '+', '30', ')']]
각각의 min(sum) 뭐 이런 식이었다.
그러나 결과는? 시간 초과! 혹은 런타임 에러!

그러나 본질은 그것이 아니다.

+, -, 정수의 형태에서 ()를 쳐서 최소값을 구하는 것은 -를 어떻게 바라볼 수 있느냐의 문제이다.

3. Solution

3-1) +,-, 정수의 조합에서 -라는 Operator 의 본질
다음 수식을 문제에서 요구하는 방식으로 풀어보자.

1+2-3+4-5+6-7-8+9+10 
=> 1+2-(3+4)-(5+6)-(7)-(8+9+10) 

33-70+50-90
=> 33-(70+50)-(90)

특징이 보이는가? 한 개만 더 풀어보자

80+90-110+100+90-80
=> 80+90-(110+100+90)-(80)

내가 왜 - 앞에다만 ()를 쳤는지 이해가 가는가

최소를 가진다는 의미는 맨 앞의 숫자를 더하는 뭉치를 제외하고는 결과적으로 뒤 모두를 -로 계산함으로써 최소가 되게할 수 있다. 

다시 쓰면 1+2-(3+4)-(5+6)-(7)-(8+9+10) = 3-7-11-7-27 = 3-(7+11+7+27)이 되므로
3을 제외하고 나머지는 다 뺀 상태가 된다.

두 번째 식을 보자.
33-(70+50)-(90) = 33-120-90 = 33-(120+90)
33을 제외하고 나머지는 다 뺀다.

세 번째 식은?
80+90-(110+100+90)-(80) = 80+90 - (110+100+90+80)

특징이 이제 보이는가?
그럼 우리는 -를 기준으로 괄호를 치면되는 것이고 -가 시작되는 지점을 기준으로 앞은 덧셈 뒤는 뺄셈으로 계산하면 된다.

3-2) Eval('000int'))의 문제
Eval은 양날의 검이라는 말을 자주사용한다. 강력하지만 그만큼 보안상으로 위험하다.
https://ko.wikipedia.org/wiki/Eval
https://namu.wiki/w/eval
https://wikidocs.net/32#eval

그러나 우리는 이것을 사용하고 싶고 그것이 지금 뜻대로 되지않는다.
eval('004+3') 우리가 생각하기에 수식적으로 문제가 없으니 12 아닌가 하겠지만 실행되지 않는다.

그렇다면 우리는 어떻게 해야할까

우선 eval()을 하지 않고 int화 시켜서 각각 계산하는 방법이 있다.
가령 '56-003+044-33'이 있을 때 이것을 int 화 시켜서 
int(56)-int(003+044)-int(33)으로 계산이 가능하다. 
Operator를 치환할 방법이 없기에 힘들 수도 있지만 split을 통하면 가능하다.

str.split('-')처럼 split()에 우리가 경계로 삼고자하는 것을 토대로 나눠준다. 때문에 3-1의 내용을 기반으로 split('-')로 나눈다면 우리는 a라는 리스트에 -를 기준으로 나눠지고 그것들을 다시 +를 기준으로 b list에 split('+') 한다면 정수만 남게되어 따로 계산 결과를 도출할 수 있다.

표를 보면 이해가 빠르다.

Input='55-030+0040+80-90'	1	2	3
A	'55'	'030+0040+80'	'90'
B		int(030)+int(0040)+int(80)
A	55	30+40+80	90

만약 eval을 쓴다면 위의 방법으로 int한 것을 다시 str로 변형시켜 +로 만들고 다시 집어넣는 방식을 택해야하는데 굳이 그럴 필요가 없다.

물론 내가 모르는 것일 수도 있지만....

4. Code - 371B 56ms

N = input().split('-')
val = 0
for i,e in enumerate(N):
    if i == 0:
        if e.isdigit():
            N[i] = int(e)
        else:
            N[i] = sum(list(map(int, N[i].split('+'))))
        val += N[i]
    else:
        if e.isdigit():
            N[i] = int(e)
        else:
            N[i] = sum(list(map(int, N[i].split('+'))))
        val -= N[i]
print(val)

5. Other's Code - rapaeljin 92B 56ms

n = [sum(int(x) for x in y.split('+')) for y in input().split('-')]
print(n[0] - sum(n[1:]))

배울점 1. 입력 자체를 list 안의 for문에서 받아 또한 번의 for 문을 내부에서 수행, 합을 구하는 방식은 저와 내용은 유사하지만 코드길이면에서 압도적으로 짧습니다. 

배울점 2. list의 가장 큰 특징 slice를 잘 활용했습니다.
저는 이 방법을 기억하지 못해 i==0일 때는 더하고 그 이외의 것들은 뺀다라는 생각으로 나열했지만 보시는 것과 같이 위와 같이 n[0] 즉 앞에 -가 나오기 전까지의 합을 나타내고 sum(n[1:])은 나머지 뒤에 있는 것들은 싹다 더해 앞의 것에서 뺀다는 관점 놀랍습니다.

6. Shortest Code - sait2000 64ms - 2년전, minkj1992, youngminz 76B 60ms 8개월전

a,*b=[sum(map(int,s.split('+')))for s in input().split('-')];print(a-sum(b))

시간이 지남에 따라 빨라지기도 혹은 느려지기도 하는 코드인데 이 코드는 빨라졌네요.
저는 왜 느려졌는지 파악하지 못했으나 아신다면 댓글 남겨주시면 감사하겠습니다.
아마 map이거나 a, *b의 형태 slice가 시간을 잡아먹은 것은 아닌지 생각합니다만....

배울점 1. a, *b = list의 형태는 첫 번째 값은 a에 나머지는 b에 넣는다는 뜻이라네요.
a,b,*c=[5,6,7,8] # a=5, b=6, c=[7,8]
a,*b,c=[5,6,7,8] # a=5, b=[6,7], c=8 #이런 것도 되네요

Cf) a,*b,*c,d = [1,2,3,4,5,6,7] 이런 것도 되나했는데
SyntaxError: two starred expressions in assignment
역시나 에러가 뜨네요

Baekjoon 1541을 통해 배운 것

• +, - Operator는 str이나 int type 변환이 불가능하다.
• eval()함수는 주의해야하며 수식의 형태가 0이 포함하는 숫자가 되면 실행되지 않는다.
  eval('4+003') != 12 #실행되지 않음
• str.split(경계문자)를 통해 나누는 것이 편리하다.
• list에 for문을 돌릴 때 input을 넣어도 큰 복잡도를 가지지 않는다.
• a,*b = []와 같이 리스트에서 나머지를 표현할 때 *를 사용하기도 한다.
  단, 두 개의 *는 사용 불가