[백준 / Java] 10799번: 쇠막대기 (실버2)

문제 풀이 날짜: 2023.07.27
포스트 작성일: 2023.07.27

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 10799번: 쇠막대기 (실버2)
SWEA 5432번: 쇠막대기 자르기 (D4)

 

키워드

스택, 구현

 

풀이 접근법

• 스택을 사용하지 않고 풀이하였다.
• 연달아서 붙어있는 괄호( “()” ) 가 레이저이므로 이를 replace()를 이용해 “*”로 교체한다.
  • 여는 괄호를 만나면 막대가 하나 추가되는 것이므로 막대의 수를 늘린다. (stick += 1)
  • 닫는 괄호를 만나면 막대 하나를 모두 잘라 없앤 것이므로 막대의 수를 줄인다. (stick -= 1) 동시에 잘라 떨어진 막대의 오른쪽 끝 토막을 더해주어야 한다. (result += 1)
  • 레이저(“*”)를 만나면 현재까지 세고 있던 막대가 모두 한꺼번에 잘리는 것이므로 막대의 수를 누적한다. (result += stick)

 

코드

import java.io.*;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String input = br.readLine();
			
		input = input.replace("()", "*");
			
		int stick = 0;
		int result = 0;
		for(int i = 0; i < input.length(); i++) {
			char c = input.charAt(i);
				
			if (c == '(') {
				stick += 1;
			} else if (c == ')') {
				result += 1; //막대의 오른쪽 끝 누적
				stick -= 1; //막대 하나가 모두 잘려 없어짐
			} else if (c == '*') {
				result += stick; //현재 겹쳐진 막대의 개수만큼 토막 누적
			}
		}
		
		System.out.println(result);
	}

}

---

스택의 응용 보다는 메커니즘을 이해하고 구현하는 것이 중요한 문제였다. 한편 replace()를 쓰는 것보다는 스택에 괄호를 넣고 빼면서 탐색하는 것이 더욱 소모시간을 줄일 수 있는 듯하다.

 

git 링크

(git 링크 첨부)