[JAVA] BOJ(백준) - 쇠 막대기 - 10799

문제 내용

여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
• 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다. 

아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.

이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.

1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.
2. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다. 

위 예의 괄호 표현은 그림 위에 주어져 있다.

쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다. 

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.

입력

한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다. 

출력

잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다.

 

---

문제 접근 방법

문제를 보면 알겠지만 쇠막대기에 레이저 n개를 쐈을때 해당 쇠막대기는 n+1개로 조각나게 된다.

이를 이용해 문제를 풀었다.

 

내풀이

1. 첫번째로 스택을 이용해서 레이저의 위치를 알아낸다. 문제에서 레이저는 ' ) ' 가 나왔을때 바로전 ' ( ' 이 괄호가 나왔을때 레이저라고 판단한다.
2. 두번째도 스택을 이용해서 쇠막대기의 위치를 알아낸다. 레이저를 제외하고는 열린괄호 ' ( ' 와 닫힌 괄호 ' ) ' 의 짝이 맞았을때 쇠막대기가 생성이 된다.
3. 세번째로 위에서 알아낸 위치들을 갖고 쇠막대기 각각 하나마다 몇개의 레이저가 닿는지 알아내고 n개의 레이저가 닿았을때 n+1개로 생성된 조각난 쇠막대기를 answer(정답)변수에 추가해준다.

내가푼 방식은 기본적으로 위의 과정을 거친다.

하지만 내가 풀었던 방식과 유사하지만 훨씬 더 효율적인 방법이 존재한다.

이는 다른분들의 풀이를 참고한 풀이이고 설명하자면 다음과 같다.

 

다른풀이

1. 내풀이와 마찬가지로 스택을 이용한다(안해도되긴함).
   ' ( ' 일때 스택에 추가, ' ) ' 일때 스택에서 반환(삭제) 한다.
2. ' ) ' 이게 나왔을때 스택에서 pop을 해주고 바로 전 요소가 ' ( ' 이거라면 answer에 스택의 사이즈만큼 더해준다.
3. 바로 전 요소가 ' ( ' 이게 아니라면 answer++ 을 해준다.

내풀이와 다른풀이 차이점

두개의 풀이에서 레이저와 쇠막대기가 만들어지는 과정은 문제에서 정의된것이기 때문에 무조건 같다.

다만, 내풀이는 쇠막대기를 하나씩 레이저를 쏴서 조각난 개수를 더하는 방법이고

다른풀이는 레이저를 쐈을때 그 레이저에 닿는 모든 쇠막대기는 조각나게 되는데 그때 조각난 쇠막대기의 한쪽부분의 개수만 세어준다. 이 과정을 레이저를 만날때마다 반복해주면서 레이저가 아닐땐 남은 쇠막대기조각을 추가하기 위해 answer++을 해주는 것이다.

즉, 정리하면

내풀이 -> 쇠막대기 하나마다의 경우를 봄.

다른풀이 -> 레이저하나에 닿는 쇠막대기 전부의 경우를 봄.

 

풀이를 보고 생각해보자.

 

---

풀이

내풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

public class Main {
	static ArrayList<Integer> razerIdx = new ArrayList<Integer>();//레이저 위치를 저장하는 리스트
	static Stack<StickPoint> stickIdx = new Stack<StickPoint>();//쇠막대기 위치를 저장하는 스택
	
	public static void main(String[] args) throws IOException{
		int answer = 0;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		
		location(s);//쇠막대기와 레이저 위치
		
		//쇠막대기 하나씩 잘라서 answer에 추가
		while(!stickIdx.isEmpty()) {
			StickPoint sp = stickIdx.pop();
			answer += stickDivide(sp,1);
		}
		
		System.out.println(answer);
	}
	
	//위치
	public static void location(String s) {
		Stack<StickPoint> st = new Stack<StickPoint>();
		
		for(int i=0; i<s.length(); i++) {
			char temp = s.charAt(i);
			
			//스택에 '('일때 추가하고, ')'일때 pop. 
			if(st.isEmpty() || temp==st.peek().c) {
				st.add(new StickPoint(i, 0, temp)); 
			} else {
				StickPoint sp = st.pop();
				//바로 전요소 체크후 레이저면 레이저 위치 추가.
				if(s.charAt(i-1)=='(') { razerIdx.add(i); }
				//레이저가 아니면 쇠막대기 위치 추가.
				else if(s.charAt(i-1)!='(') { stickIdx.add(new StickPoint(sp.x, i, temp));}
			}
		}
	}
	
	//쇠막대기 조각내서 개수 세기
	//cnt(개수)는 레이저 n개를 쐈을때 조각난 쇠막대기가 n+1개가 되야하므로
	//초기값을 1로하고 시작함.
	public static int stickDivide(StickPoint sp, int cnt) {
		int stickX = sp.x;//쇠막대기 시작 위치
		int stickY = sp.y;//쇠막대기 끝나는 위치
		
		for(int i=0; i<razerIdx.size(); i++) {
			int razer = razerIdx.get(i);
			//레이저가 쇠막대기 시작과 끝위치 안에 포함되면
			//레이저가 닿는다는 의미로 쇠막대기가 조각나게됨.
			//따라서 레이저 닿을때 마다 cnt 증가.
			if(stickX<razer && stickY>razer) { cnt++; }
		}
		return cnt;
	}
}

//스택에 저장해줄 클래객체
class StickPoint{
	int x;//start 위치
	int y;//end 위치
	char c;//괄호 모양
	public StickPoint(int x, int y, char c) {
		this.x = x;
		this.y = y;
		this.c = c;
	}
}

 

다른 풀이

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		
		int answer = 0;
		Stack<Integer> st = new Stack<Integer>();
		
		for(int i=0; i<s.length(); i++) {
			char temp = s.charAt(i);
			//스택에 '(' 일때 추가하고, ')'일때 pop
			if(temp=='(') {
				st.add(i);
			}else {
				st.pop();
				if(s.charAt(i-1)=='(') { //만약 레이저라면
					answer += st.size(); //남은 스택사이즈(잘릴 쇠막대기 갯수) 더함.
				} else { //레이저가 아닐땐 잘린 쇠막대기 끝에 남은거 하나를 더함.
					answer++; 
				}
			}
		}
		
		System.out.println(answer);
	}
}

 

---

마치며

스택을 사용하는 방법을 알아볼 수 있는 문제였다. 사실 두번째 풀이로 푼다면 스택이 필요없이 풀수 있긴하다.

여튼 스택은 문자 짝맞추는거, 괄호문제 등등에 자주 쓰이기 때문에 알아두는게 좋다.