[인프런 알고리즘] Chapter 5, 5번 문제(쇠막대기)

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class sec05_05 {
    public static int solution(String str) {
        int count = 0;
        int metalStick = 0;
        for(int i = 0; i < str.length(); ++i)
        {
            if(str.charAt(i) == '(') ++metalStick;
            else if(str.charAt(i - 1) == '(') //레이저
            {
                --metalStick;
                if(metalStick > 0) count += metalStick;
            }
            else //막대 끝
            {
                --metalStick;
                ++count;
            }
        }
        return count;
    }

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

 

설명

• count: 잘린 쇠막대기의 총 개수를 저장하는 변수.
  metalStick: 현재 존재하는 쇠막대기의 수를 저장하는 변수.
  
  
• 주어진 문자열 str을 처음부터 끝까지 순회하며, 각 문자에 대해 조건을 판단한다.
  
  -'('가 나오면 새로운 쇠막대기가 시작된 것이므로 metalStick을 1 증가시킨다.
  
  -')'가 나왔을 때, 이전 문자가 '('라면 레이저로 간주한다. 이 경우 레이저가 위치한 쇠막대기의 수만큼 잘리므로 metalStick을 감소시키고, 남아 있는 metalStick 수만큼 count에 더해준다.
  
  -')'가 나오고 이전 문자가 '('이 아니라면 쇠막대기의 끝을 의미한다. 이 경우 metalStick을 감소시키고, 잘린 막대기의 끝부분을 하나 더해주어야 하므로 count를 1 증가시킨다.
  
  
• 최종적으로 잘린 쇠막대기 조각의 개수를 반환하여 출력한다.