-
1541. [Python]잃어버린 괄호Python_알고리즘/Silver II 2023. 8. 6. 20:46
1. 문제
https://www.acmicpc.net/problem/1541
1541번: 잃어버린 괄호
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- 브루트 포
3. 파이썬 코드
# -가 들어있는 부분을 기준으로 인풋값을 짜른다. word = list(map(str,input().split("-"))) answer_list = [] # word의 길이만큼 반복문을 진행하는데 for i in range(len(word)): # 만약 word[i]에 + 연산자가 들어있는 경우 if "+" in word[i]: # 이 값들도 + 를 기준으로 정수로 변환하여 리스트로 잘라준다. hap_list = list(map(int,word[i].split("+"))) # 이후 이 값들을 합한 값을 word[i]에 넣어준다. word[i] = sum(hap_list) # 정답을 출력할 변수 answer = 0 # 만약 word 가 - 연산자가 있는 경우 리스트는 2개 이상으로 나뉜다. if len(word) > 1: # word의 길이만큼 반복을 하며 for j in range(len(word)): # 처음 인덱스 값은 무조건 더해준 후 if j == 0: answer += int(word[j]) # 이후 인덱스는 answer 변수에 값을 계속해서 뺴준다. else: answer -= int(word[j]) print(answer) # word에 - 연산자가 없는 경우 0 번 인덱스 출력 else: print(word[0])
4. 문제를 풀고난 후 생각
- 최소값이 나오기 위해서 생각해볼 조건은 어떤 경우가 있는지 수학적으로 생각해 봐야한다.
- +로 계산된 값들이 크지 않는 경우, - 연산자 이후 값들끼리 먼저 계산을 통해서 뺴주는 값이 커야하는 경우가 있다.
- 이를 바탕으로 처음 - 연산자를 기준으로 list 형태로 값을 나눠준다.
- 나눠준 값들을 탐색하여 + 연산자를 기준으로 값들을 또 나눠준 후 그 값들을 먼저 계산해서 i 번째 인덱스에 값을 바꿔준다. => x + y + z 이런 식을 sum을 통해서 합을 계산해서 넣어준다.
- 이러한 반복문을 거치면 word 라는 리스트에는 결국 A - B - C 이런 결과만 남게되며 만약 - 연산자가 없는 경우는 word 리스트 내부에는 1개의 값만 가지게 된다.
- 이를 조건식을 통해서 길이가 1인 경우 그대로 출력, 1보다 큰 경우 index 값이 0 인 처음 값은 더한 후 이후 값들은 계속해서 - 를 해주는 방식으로 결과값을 도출했다.
- 이 문제 또한 수학적 생각이 필요한 문제같다.
5. 문제를 푸는데 도움이 되는 지식
- 브루트 포스
'Python_알고리즘 > Silver II' 카테고리의 다른 글
1260. [Python]DFS와 BFS (0) 2023.08.08 1874. [Python]스택 수열 (0) 2023.08.07 1024. [Python]수열의 합 (0) 2023.08.04 1254. [Python]팰린드롬 만들기 (0) 2023.08.04 10799. [Python]쇠막대기 (0) 2023.02.13