자기개발/BOJ

[BOJ 16133] 공학용 계산기 (Calculator)

KGW2027 2023. 2. 5. 21:27
728x90
반응형

https://www.acmicpc.net/problem/16133

 

16133번: 공학용 계산기 (Calculator)

계산해야 할 식이 주어진다. 식의 길이는 100을 넘지 않으며, 문제에 주어진 문법을 만족한다. 또한 다음과 같은 조건을 만족하는 수식만 입력으로 주어짐이 보장된다. 계산 과정에서 등장하는

www.acmicpc.net

 

1. 접근

 문제 상단에서 보이듯 BNF 같은 표기법이 있어서 이대로 구현했다.

단, <expr>과 <term>의 경우( +, -, *, / ) 써져있는대로 하면 오른쪽을 먼저 계산하게 되는데,

문제 제시대로라면 왼쪽이 먼저 계산되어야 하므로

  • <expr> = <term> { [+ | -] <term> }
  • <term> = <factor> { [* | / ] <factor> }

로 바꿔서 풀었다.

 

2. 과정

 일단 InputStream을 Read하는 것만이 아니라, Peek하는 기능이 필요하다.

그래서 PushbackInputStream을 만들어서, Read->Unread 하는 방식으로 Peek을 구현했다.

    static int peek() throws Exception {
        int peek = pis.read();
        pis.unread(peek);
        return peek;
    }

 

 <num>, <digit>, <non-zero> 는 결국 모두 숫자 부분을 읽는 것을 분리해놨을 뿐이므로, 합쳐서 parseNum에 숫자를 읽는 것을 구현했다.

    static long parseNum() throws Exception {
        if (peek() == '0') return pis.read() - '0';
        long n = 0;
        int b;
        do {
            b = pis.read();
            if ('0' <= b && b <= '9') n = n * 10 + (b - '0');
        } while ('0' <= b && b <= '9');

        pis.unread(b);
        return n;
    }

 

 Java에서 가장 큰 문제는 math.sqrt의 정확도가 낮았다는 점이다. 그로 인하여, Math.sqrt(long)으로는 큰 수의 sqrt를 제대로 구현할 수 없었다.

Input
#9223372030926249001=

Output
3037000499
Answer
3037000499

Input
#9223372030926249000=

Output
3037000499
Answer
3037000498

 

 이를 해결하기 위해 BigDecimal.sqrt(MathContext.DECIMAL128)을 이용하여, 128자리 수 까지의 정확도를 확보하여 longValue를 얻어냈다. 그리고, BigDecimal.sqrt()는 Java 9 이상부터 사용가능하므로, Java 11로 제출했다.

long power = parsePower();
return new BigDecimal(power).sqrt(MathContext.DECIMAL128).longValue();

 

3. 코드

728x90
반응형