-
[백준 4889] 안정적인 문자열 (Python)Algorithm & Problem Solving/그리디 알고리즘(Greedy) 2021. 2. 5. 02:11
문제풀이
stack을 이용해 안정적이지 않은 경우 ans를 증가하는 방식으로 해결할 수 있다.
1. 현재 문자가 '{' 이면 stack에 append하기
2. 현재 문자가 '}' 이면 stack 에서 pop하기
- stack 이 비어있을 경우 안정적이지 않은 경우이므로 ans 증가
- 이 경우 안정적이지 않은 '}' 를 바꿔줘야 하므로 '{'를 stack에 append
3. stack 이 남아있을 경우, stack에 남아있는 개수가 2의 배수일 경우 ans 증가하기 => 2의 배수일 경우 '{' 를 '}'로 바꿔서 안정적인 문자로 만들어야 하기 때문
코드
import sys if __name__ == '__main__': idx = 1 while True: S = list(map(str, sys.stdin.readline().rstrip())) if '-' in S: break stack = [] ans = 0 for y in S: if y == '{': stack.append(y) else: if stack: stack.pop() else: ans += 1 stack.append('{') while stack: if len(stack) % 2 == 0: ans += 1 stack.pop() print(f'{idx}. {ans}') idx += 1
결과
문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!
'Algorithm & Problem Solving > 그리디 알고리즘(Greedy)' 카테고리의 다른 글
[백준 1461] 도서관 (Python) (0) 2021.02.10 [백준 19639] 배틀로얄 (Python) (0) 2021.02.05 [백준 2258] 정육점 (Python) (0) 2021.02.04 [백준 1041] 주사위 (Python) (0) 2021.01.30 [백준 1263] 시간 관리 (Python) (0) 2021.01.30