Cooper's devlog

쇠막대기 :10799번 - JAVA 본문

Algorithm/Baekjoon

쇠막대기 :10799번 - JAVA

cooper_dev 2020. 7. 9. 10:53

1. 문제 링크

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

 

10799번: 쇠막대기

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

www.acmicpc.net

 

 

2. 문제 설명

 

 

 

3. 문제 접근법

  • 핵심 포인트
    • ()는 레이저!
    • ( )는 막대기 끝!
  • 차이는?(※중요!)
    • '(' 바로 옆에 있는 ')'은 레이저!
    • '('아 2칸 이상 떨어져 있는 ')'은 막대기 끝!

문제 풀이 순서

 

(1) 입력 괄호들을 순차적으로 탐색한다.

  • stack에 들어가는 값들은 괄호의 '인덱스'
  • 추가되는 괄호 인덱스는 오직 괄호 앞부분 '('만 해당한다.

(2) 조건문 처리

  1. ( → stack에 괄호 index 추가
  2. ) → if. stack의 값이 '인덱스 -1'(레이저 입니까?) -> 합계에 stack.size (레이저로 잘리는 갯수) 추가
  3.   → else                              (막대기 입니까?)    -> stack.pop & 합계에 1더하기

 

4. 문제 풀이

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
 
public class Fe_stick {
    public static void main(String[] args) throws IOException  {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        Stack<Integer> stack = new Stack<>();
        String input = br.readLine();
        int sum_of_seperated_sticks = 0;
        
        for (int i = 0; i < input.length(); i++) {
            if(input.charAt(i) == '(')    stack.push(i);
            if(input.charAt(i) == ')') {
                if(stack.peek() == i - 1){
                stack.pop();
                sum_of_seperated_sticks += stack.size();
                }else {
                    stack.pop();
                    sum_of_seperated_sticks++;
                }
            }
        }
        
        System.out.println(sum_of_seperated_sticks);
        
        br.close();
    }
}
  

 

<정답확인>

5. 느낀점 또는 특이사항

문제 풀고 나서 다름 사람의 문제풀이가더 간결하고 깔끔해보여서 참고했다.

기존 풀이법 : Stack<Character>로 첨가해서 stack.size() 카운팅하려고 하니, 레이저와 막대기 끝 구분하는 것을 어떻게 해야하지라는 부분에서 시간이 오래걸렸는데 아예 인덱스로 처리하는 방법이 훨씬 효율적인 것을 확인했다.

 

'Algorithm > Baekjoon' 카테고리의 다른 글

덱 :10866번 - JAVA  (0) 2020.07.10
오큰수 :17298번 - JAVA  (0) 2020.07.10
단어 뒤집기 :17413번 - JAVA  (0) 2020.07.09
조세퍼스 문제 : 1158번 - JAVA  (0) 2020.07.08
에디터:1406번 - JAVA  (0) 2020.07.08
'Algorithm/Baekjoon' Related Articles more
Comments