ps:problems:boj:30855
Fraction
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 30855 |
문제명 | Fraction |
레벨 | 실버 1 |
분류 |
파싱 |
시간복잡도 | O(n) |
인풋사이즈 | n<=100 |
사용한 언어 | Python 3.11 |
제출기록 | 39512KB / 136ms |
최고기록 | 40ms |
해결날짜 | 2023/11/29 |
풀이
- 분수를 계산하는 것은, 분자 분모를 따로 저장해서 계산하고, 분자와 분모의 최소공약수로 나누어주면 기약분수 형태를 유지할수 있다. 귀찮으면 파이썬에서는 그냥 fractions 모듈을 쓰면 된다. 속도는 fractions 모듈을 쓰는것이 더 느리지만, 시간이 타이트한 문제가 아니라서 아무 상관 없다.
- 만약 올바른 입력이 들어온다면, 스택을 이용해서 이항연산을 처리하는 것의 간단한 확장이 된다. 여기까지는 전혀 어려울것이 없다.
- 어렵다..기 보다도 귀찮은 것은 올바르지 않은 입력이 들어올수도 있다는 것이다. 온갖 잘못된 입력들을 모두 떠올리는 것부터가 하기 싫어진다. 그러나 다행히도 케이스가 그리 많지는 않다. 들어오는 토큰 자체는 올바르게 정해져있으니, 구조만 체크하면 된다. 잘 생각해보면 잘못된 입력은 결국
'괄호끼리 매칭이 안되는 경우'와 '( 와 ) 사이에 항이 세 개가 아닌 경우', '시작이나 끝에 괄호 대신 숫자가 있는 경우' 뿐이라는 것을 알 수 있다. 스택에 '(' 를 같이 넣어주어서, ')'를 처리할때 괄호 매칭과 괄호사이의 항이 3개인지 체크해주고, 문자열을 모두 처리한 뒤에 스택에 숫자 한개만 남게 되는지만 확인해주면 된다. n>2 이상이기 때문에, 숫자 하나만 들어오는 입력을 따로 체크해줄 필요는 없다.
- 총 시간복잡도는 O(n).
코드
"""Solution code for "BOJ 30855. Fraction".
- Problem link: https://www.acmicpc.net/problem/30855
- Solution link: http://www.teferi.net/ps/problems/boj/30855
Tags: [parsing]
"""
import fractions
def main():
n = int(input()) # pylint: disable=unused-variable
symbols = input().split()
stack = []
for s in symbols:
if s == ')':
if len(stack) < 4 or stack[-4] != '(' or '(' in stack[-3:]:
print('-1')
return
a, b, c = stack[-3:]
stack[-4:] = [a + b / c]
elif s == '(':
stack.append(s)
else:
stack.append(fractions.Fraction(s))
if len(stack) != 1 or stack[0] == '(':
print('-1')
return
answer = stack[0]
print(answer.numerator, answer.denominator)
if __name__ == '__main__':
main()
ps/problems/boj/30855.txt · 마지막으로 수정됨: 2023/11/29 14:06 저자 teferi
토론