[문제풀이] 05-05. 쇠막대기

𝒄𝒉𝒂𝒏𝒎𝒊𝒏·2023년 11월 2일

코딩테스트

인프런 자바 알고리즘 문제풀이

목록 보기

40/95

인프런, 자바(Java) 알고리즘 문제풀이

Stack, Queue(자료구조) - 0505. 쇠막대기

🗒️ 문제

🎈 나의 풀이

	private static int solution(String[] strArr) {
        int answer = 0, cnt = 0, k=0;
        Stack<String> stack = new Stack<>();
        String beofre = "";

        while(true){
            cnt = 0;

            for(String s : strArr) {
                if (s.equals("(")) stack.push(s);
                else if(s.equals(")")) {
                    if(stack.size() > 1 && beofre.equals("(")) cnt++;
                    if(!stack.empty()) stack.pop();
                    if(stack.empty() && cnt != 0) {
                        answer += cnt + 1;
                        cnt = 0;
                    }
                }
                beofre = s;
            }

            stack.clear();
            cnt = 0;
            int a = 0, b = 0;

            for(String s : strArr) {
                if(s.equals("(")) stack.push(s);
                else if(s.equals(")") && !stack.empty()) {
                    stack.pop();
                    cnt++;
                    if(stack.empty()) {
                        if(cnt <= 2) for (int i=a; i<b+1; i++) strArr[i] = "_";
                        a = b+1;
                        cnt = 0;
                    }
                }
                b++;
            }

            stack.clear();

            for(int i=0; i<strArr.length; i++) {
                if(strArr[i].equals("(")) {
                    if (stack.empty()) {
                        stack.push(strArr[i]);
                        strArr[i] = "_";
                    } else stack.push(strArr[i]);
                }

                if(strArr[i].equals(")")) {
                    stack.pop();
                    if(stack.empty()) strArr[i] = "_";
                }
            }

            boolean isEnd = true;

            for(String s : strArr) if(!s.equals("_")) isEnd = false;

            if(isEnd) return answer;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] strArr = sc.nextLine().split("");
        System.out.println(solution(strArr));
    }

🖍️ 강의 풀이

    public int solution(String str){
		int cnt=0;
		Stack<Character> stack=new Stack<>();
		for(int i=0; i<str.length(); i++){
			if(str.charAt(i)=='(') stack.push('(');
			else{
				stack.pop();
				if(str.charAt(i-1)=='(') cnt+=stack.size();
				else cnt++;
			}
		}
		return cnt;
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		String str=kb.next();
		System.out.println(T.solution(str));
	}

💬 짚어가기

해당 문제는 stack을 이용하여 해결할 수 있다.

나의 풀이는 가장 하단 막대기부터 절단된 개수를 헤아리며 가장 상단의 막대기까지 확인하는
방식으로 접근하였다. 이 때 핵심은 괄호중 레이저를 분별하는 것이다.

✔️ 레이저 분별하기

(인 경우 : 스택에 push
)인 경우 : 직전의 기호가 (인 경우 레이저로 간주, pop()

나의 풀이에서는 직전의 기호를 보관할 수 있는 before라는 변수를 하나 두었고, ) 기호가
들어왔을 때 3가지 조건을 판별을 하도록 구성하였다.

✔️ 닫는 기호와 3개의 조건문

before이 ( 기호이면서 스택의 사이즈가 1보다 큰 경우 cnt++
() 쌍일지라도 감싸고있는 괄호가 없다면 자를 수 있는 쇠막대는 없다.
따라서 크기를 추가로 검사한다. 이 때 cnt는 연속된 레이저의 개수이다.
스택이 비어있지 않은 경우 pop()
닫는 기호에 대한 한쌍의 여는 기호를 제거한다.
스택이 비어있고, cnt가 0이 아닌 경우 절단된 쇠막대 개수 누계
스택이 비어있다는 의미는 모든 괄호가 닫혔다는 의미이다. 따라서 그 사이
레이저에 잘린 쇠막대의 개수(cnt + 1)을 누계한다.

이후 그 다음 상단의 막대기의 절단 개수를 헤아려야한다. 따라서 괄호를 적절히 가공해야한다.
가공은 다음 두 단계를 따른다. 괄호의 제거는 해당 괄호를 _ 기호로 대체하도록 하였다.

✔️ 다음 막대기를 위한 괄호 가공하기

(()) 제거 : 레이저를 감싸고 있는 괄호의 쌍이 1개인 경우, 더 이상 다음 층의 막대기를
자를 수 없다. 따라서 sliding window를 통해 해당 괄호를 제거하였다.
양 끝 괄호 제거 : 다음 층의 막대기는 아래 층의 막대기보다 길이가 짧아야한다. 따라서
레이저를 감싸고 있는 괄호 중 최외각 괄호를 제거한다. stack을 이용해 구현하였다.

이렇게 가공된 괄호를 통해 다음 층의 절단된 막대기 개수를 파악할 수 있다. 이 과정을 반복문을
돌며, 모든 괄호가 _ 기호로 대체될 때 절단된 막대기의 누계를 반환하며 문제를 해결할 수 있다.

강의에서는 마찬가지로 레이저를 식별하고, 레이저가 등장할 때 스택의 사이즈를 체크하여 자를 수 있는
막대기의 개수를 누계하도록 구성하였다. 다음으로 레이저가 아닌) 기호가 등장하면 잘려진 쇠막대의
조각으로 간주하고 개수를 누계하여 문제를 해결한다.