[백준][BOJ 2257] - 화학식량

문제

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

2257번: 화학식량

 

 

문제 접근

• 문제를 보면 다음과 같은 특징을 가진다.
  • 먼저 숫자가 들어갈 경우, 직전의 화학식량 * 숫자 로 값을 계산해야 한다.
  • 괄호가 들어간 경우, 괄호 내부의 화학식량을 우선해서 계산해야 한다.
• 예를 들면 다음과 같다.
• $CH(CO2H)3$ 을 보자
  • C, H는 각각 12, 1로 저장된다.
  • 괄호가 열려 있으므로 괄호가 닫힐 때 까지의 화학식량을 계산해야 한다.
    • $CO2H$는 O 뒤에 2가 존재하므로 C = 12, O2 = 32, H = 1로 괄호 내부의 화학식량은 총 45가 된다.
  • 괄호 뒤에 3이 존재하므로 괄호 내부의 화학식량 45에 3을 곱한 135가 결과가 된다.
  • 따라서 전체 화학식량은 12 + 1 + 135 = 148이 된다.
• 문제는 위의 과정을 어떻게 코드로 나타낼 것인지이다. 우리가 필요한 연산들은 다음과 같다.
  • 숫자가 들어오면 직전의 값을 뺀 뒤 숫자를 곱해 다시 넣어주는 연산이 필요하다.
  • 괄호가 존재할 경우 내부의 화학식량을 먼저 구해야 하는 연산이 필요하다. 이때 내부 화학식량을 구하는 방식은 기존과 동일하다.
• 연산들의 특성을 고려해보면 스택이 꽤나 적절해 보인다. 내부의 화학식량을 먼저 구해야 하는 연산의 경우, 적절한 재귀함수를 사용하여 계산이 가능해 보인다.

 

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class Main {
  static Map<Character, Integer> map;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String data = br.readLine();

    Deque<Integer> stack = new ArrayDeque<>();
    map = new HashMap<>();
    map.put('H', 1);
    map.put('C', 12);
    map.put('O', 16);

    int idx = 0;
    while(idx < data.length()){
      char element = data.charAt(idx);

      if (element == '('){
        idx = solve(idx + 1, data, stack);
        continue;
      }

      if (element >= 'A' && element <= 'Z'){
        stack.addLast(map.get(element));
      } else if (element >= '2' && element <= '9'){
        stack.addLast(stack.pollLast() * (element - '0'));
      }

      idx++;
    }

    int ans = 0;
    while (!stack.isEmpty()){
      ans += stack.pollLast();
    }

    System.out.println(ans);
  }

  static int solve(int idx, String data, Deque<Integer> stack){
    Deque<Integer> tempStack = new ArrayDeque<>();

    while(data.charAt(idx) != ')'){
      if (data.charAt(idx) == '('){
        idx = solve(idx + 1, data, tempStack);
        continue;
      }

      if (data.charAt(idx) >= 'A' && data.charAt(idx) <= 'Z'){
        tempStack.addLast(map.get(data.charAt(idx)));
      } else if (data.charAt(idx) >= '2' && data.charAt(idx) <= '9'){
        tempStack.addLast(tempStack.pollLast() * (data.charAt(idx) - '0'));
      }

      idx++;
    }

    int result = 0;
    while(!tempStack.isEmpty()){
      result += tempStack.pollLast();
    }

    stack.addLast(result);

    return idx + 1;
  }
}