백준 1541번 : 잃어버린 괄호 문제풀이 [파이썬]
그리디 알고리즘
<문제>
1541번 문제의 내용은 아래와 같습니다.
잃어버린 괄호
문제
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
입력
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
출력
첫째 줄에 정답을 출력한다.
예제 입력 1 복사
55-50+40
예제 출력 1 복사
-35
예제 입력 2 복사
10+20+30+40
예제 출력 2 복사
100
예제 입력 3 복사
00009-00009
예제 출력 3 복사
0
<작성한 코드>
<코드 풀이>
생각보다 코드구현에 애를 많이 먹은 문제,,,
그리디 알고리즘을 적용해서 해결방법을 생각하는건 금방했지만
코드로 구현하려고하니 어려움을 많이 겪었다.
그리디 알고리즘 적용의 정당성 입증)
주어진 식의 최솟값을 구해야하는 문제이므로
'+' 기호가 붙어있는 값들을 먼저 계산해서 최대한 큰 값을 만들어줘야한다.
이렇게 큰 값을 만들어서 '-'기호가 나올때마다 빼주어야 최솟값을 구할 수 있다.
구현)
먼저 입력받은 값들을 split() 함수를 이용해
'-'기호를 기준으로 문자열을 잘라준다.
split() 함수는 괄호안의 값을 기준으로 문자열을 자르고 리스트로 만들어준다.
예를 들어,
55-50+40-30+20+10 라는 입력값이 주어지면
a라는 변수에는 [55, 50+40, 30+20+10]으로 나누어져
리스트 형식으로 문자열이 들어가게 된다.
이렇게 만들어진 a 리스트안에 있는 값들을
반복문을 사용해 또다시 하나하나 '+'기준으로 나눠준다.
이때 반복문을 한번 더 사용해 리스트에 들어있는 문자열들을
숫자형식으로 바꿔주고, + 계산을 해주어 num이라는 변수에 넣어준다.
이제 이렇게 생겨난 num이라는 리스트에 있는 숫자값들을
처음부터 시작해서 하나하나 다 빼주면 최솟값을 구할 수 있게된다.
만약 주어진 식에 -는 없고 +만 있다면
리스트에는 원소가 단 하나만 존재하기 때문에
ans = num[0] 줄에서 이미 최솟값을 구하게 되고,
여러 원소들이 존재한다면 0번째 값부터 시작해서
뒤에 이어질 모든 값들을 빼주면된다.
'백준 알고리즘 > Python' 카테고리의 다른 글
| [알고리즘] 정렬 알고리즘(1) - 선택 정렬, 삽입 정렬 (0) | 2023.02.22 |
|---|---|
| [알고리즘] DFS & BFS 알고리즘(3) - BFS 알고리즘 (0) | 2023.01.27 |
| [알고리즘] 그리디 알고리즘 - 백준 11399 파이썬 문제풀이: ATM (4) | 2022.12.25 |
| [알고리즘] DFS & BFS 알고리즘(2) - DFS 알고리즘 (0) | 2022.12.24 |
| [알고리즘] DFS & BFS 알고리즘(1) - 스택 자료구조와 큐 자료구조 (0) | 2022.12.24 |