[백준] 알고리즘 분류(자료 구조,JAVA)10799번, 쇠막대기

문제 링크

10799번: 쇠막대기

---

 

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. '( )'쌍으로 표현될 때 반드시 레이저입니다.

2. 쇠막대기는 '('로, 오른쪽 끝에 닫힌 ')'로 표현합니다.

3. 레이저로 잘려진 쇠막대기의 개수를 결과로 출력합니다.

4. 막대기는 아래에서 위로 중첩됩니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 괄호 정보를 순차적으로 탐색하여 쇠막대기를 레이저로 자르는 시뮬레이션을 진행합니다.

 

3. 레이저로 자른 쇠막대기의 개수를 결과로 출력합니다.

 

 

시뮬레이션.

※1번째 괄호는 항상 ' ( ', 마지막 괄호는 항상' ) '입니다.

 

괄호 정보에 따라 시뮬레이션 진행과정이 달라집니다.

 

현재 괄호가 ' ( '일 때

 

다음 괄호가 ' ) '일 때

 

'( )' 쌍이 형성으로 레이저 발사

 

현재 존재하는 쇠막대기 개수만큼 쇠막대기 잘라집니다.

 

쌍으로 이루어졌으므로 다다음 괄호를 탐색하다록 진행!

 

자려진 막대기 개수 += 현재 막대기 개수

 

다음 괄호가 ' ( '일 때

쇠막대기 추가

 

현재 괄호가 ')'일 때

 

쇠막대기 1개 끝에 도달!

 

자려진 막대기 개수 += 1

 

※끝에 도달한 막대기가 잘려진 막대기 형태로 변경되기 때문에 +1이 진행됩니다.

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

괄호 정보

()(((()())(())()))(())

 

2. 괄호 정보를 순차적으로 탐색하여 쇠막대기를 레이저로 자르는 시뮬레이션을 진행합니다.

시뮬레이션 진행

 

현재 쇠막대기 : 0개

잘린 막대기 : 0개

 

()(((()())(())()))(())

현재 괄호 : ' ( '

다음 괄호 : ' ) '

레이저 발사!

잘린 막대기(0) += 현재 쇠막대기(0)

 

()(((()())(())()))(())

현재 괄호 : ' ( '

다음 괄호 : ' ( '

쇠막대기 추가

현재 쇠막대기 : 1개

 

()(((()())(())()))(())

현재 괄호 : ' ( '

다음 괄호 : ' ( '

쇠막대기 추가

현재 쇠막대기 : 2개

 

()(((()())(())()))(())

현재 괄호 : ' ( '

다음 괄호 : ' ( '

쇠막대기 추가

현재 쇠막대기 : 3개

 

()(((()())(())()))(())

현재 괄호 : ' ( '

다음 괄호 : ' ) '

레이저 발사!

잘린 막대기(0) += 현재 쇠막대기(3)

 

...

 

()(((()())(())()))(())

현재 괄호 : ' ) '

쇠막대기 1개 끝에 도달!

잘린 막대기(16) += 1

 

3. 레이저로 자른 쇠막대기의 개수를 결과로 출력합니다.

 

잘린 막대기 : 17을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 괄호 정보를 가지고 시뮬레이션을 진행합니다.
• 시뮬레이션 결과로 얻어진 잘려진 막대기를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String info = br.readLine();
        int n = 0;
        int answer = 0;
        //시뮬레이션 진행
        for(int i=0;i<info.length()-1;i++){
            if(info.charAt(i) == '('){		//현재 괄호가 '('일 때
                //다음 괄호가 ')' 일 때 레이저 발사!
                if(info.charAt(i+1) == ')') {
                    answer += n;	//현재 막대기 개수만큼 잘려집니다.
                    i++;	//다다음 괄호로 이동하도록 위치 +1
                }else	//다음 괄호가 '(' 일 때 쇠막대기 추가
                    n++;
            }else{	//현재 괄호가 ')'일 때
                n--;	//현재 막대기 개수 -1
                answer++;	//잘라진 막대기 개수 + 1
            }
        }
        answer++;		//마지막 괄호')'이기 때문에 + 1
        bw.write(answer + "");		//잘려진 막대기 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}