[Programmers] 쇠막대기

[Level 2] 쇠막대기

https://programmers.co.kr/learn/courses/30/lessons/42585

• 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다.
• 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 '()'으로 표현한다. 또한 모든 '()'는 반드시 레이저를 표현한다.
• 쇠막대기의 왼쪽 끝은 여는 괄호 '('로, 오른쪽 끝은 닫힌 괄호 ')'로 표현된다.'
• 쇠막대기와 레이저의 배치를 표현한 문자열 arrangement가 매개변수로 주어질 때, 잘린 쇠막대기 조각의 총 개수를 return 하도록 solution 함수를 작성

 

 

Solution

• 먼저 문자열 arrangement에서 레이저를 의미하는 "()"를 "*"으로 변경했다.
• arrangement에 대해 for문 으로 레이저에 가장 인접한 쇠막대기를 자르는 방식
• 레이저로 쇠막대기를 자르면 (레이저 개수 + 1) 만큼의 조각이 생기는 것을 이용했고, 자른 쇠막대기 "()"는 arrangement에서 지워준다.
• while문의 종료 조건은 arrangement의 길이가 처음에 total 변수에 저장된 레이저 개수와 같을 때이다.
• 그리고 문제를 다 풀고 다른 사람의 풀이를 보니까 나만 이렇게 풀었더라 ,, 시간 오래걸리는 걸로 1등 했다 ^.^

 

 

소스코드

 

import java.util.*;
 
class Solution {
    static int answer;
 
    public int solution(String arr) {
        answer = 0;
        arr = arr.replace("()", "*");
        int total = 0;
        for (int i = 0; i < arr.length(); i++) {
            if (arr.charAt(i) == '*')
                total++;
        }
 
        StringBuilder sb;
        int open = 0, close = 0, rcount = 0;
        while (true) {
            for (int i = 0; i < arr.length(); i++) {
                if (arr.charAt(i) == '(') {
                    open = i;
                    rcount = 0;
                }
                if (arr.charAt(i) == '*') {
                    rcount++;
                }
                if (arr.charAt(i) == ')') {
                    close = i;
                    sb = new StringBuilder();
                    sb.append(arr.substring(0, open));
                    sb.append(arr.substring(open + 1, close));
                    sb.append(arr.substring(close + 1, arr.length()));
                    arr = sb.toString();
                    answer += (rcount + 1);
                    rcount = 0;
                    break;
                }
            }
            if (arr.length() == total) {
                break;
            }
 
        }
        return answer;
    }
}

 

 

+) Stack 풀이

 

import java.util.*;
 
class Solution {
    public static int solution(String arrangement) {
        int answer = 0;
        Stack<Integer> st = new Stack<>();
        for (int i = 0; i < arrangement.length(); i++) {
            if (arrangement.charAt(i) == '(') {
                st.push(i);
            } else if (arrangement.charAt(i) == ')') {
                if (st.peek() + 1 == i) {
                    st.pop();
                    answer += st.size();
                } else {
                    st.pop();
                    answer += 1;
                }
            }
        }
        return answer;
    }
}