[알고리즘] 프로그래머스 쇠막대기 -스택(Stack)-

https://programmers.co.kr/learn/courses/30/lessons/42585?language=kotlin

코딩테스트 연습 - 쇠막대기

 

(a) 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 '()'으로 표현합니다. 또한 모든 '()'는 반드시 레이저를 표현합니다.
(b) 쇠막대기의 왼쪽 끝은 여는 괄호 '('로, 오른쪽 끝은 닫힌 괄호 ')'로 표현됩니다.

 

프로그래머스 LEVEL2 문제 쇠막대기를 풀어봤습니다.

간단히 설명하면 ( ) 는 레이저 나머지 ( ( (  ,   ) ) )  이런 연속된 것들은 쇠막대기를 뜻합니다.

예를들어 ( ( ( ) ) ) 이렇다면   밑과 같은 형식이 됩니다.

그림실력 ㅈㅅ.

 

 

처음에 다음과 풀고 테스트케이스만 통과하고 제출시 통과를 못했었습니다.

import java.util.Stack;

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution("()(((()())(())()))(())");
    }

    public int solution(String arrangement) {
        int answer = 0;
        Stack<Character> stack = new Stack<>();
        for (char c : arrangement.toCharArray()) {
            if (c == '(') {
                stack.add(c);
            } else {
                char bar = stack.pop();
                if (bar == '(') { // 왼쪽 막대기 잘려야할 개수
                    answer += stack.size();
                } else { // 오른쪽 막대기 잘리는 부분 하나 증가
                    answer++;
                }
            }
        }
        System.out.println(answer);
        return answer;
    }
}

원인은 스택에 쌓인 값이 아닌 바로 왼쪽에 있는 값을 확인했어야했습니다. )

스택에는 항상 ( 만 쌓이기 때문입니다. 이전 값이 ( 인 경우 현재 값인 ) 와 만나므로 레이저를 형성하고 레이저를 포함한 ( 값을 pop 한 개수의 스택사이즈만큼 막대기가 잘릴겁니다.

 

수정하여 통과한 풀이는 다음과 같습니다.

[Java]

import java.util.Stack;

class Solution {

    public int solution(String arrangement) {
        int answer = 0;
        Stack<Character> stack = new Stack<>();
        int i = 0;
        for (char c : arrangement.toCharArray()) {
            if (c == '(') {
                stack.add(c);
            } else {
                stack.pop();
                if (arrangement.charAt(i-1) == '(') { // 왼쪽 막대기 잘려야할 개수, 이전께 '(' 일 경우 레이저의 왼쪽부분 잘리는 개수를 더함
                    answer += stack.size();
                } else { // 오른쪽 막대기 잘리는 부분 하나 증가 ,이전께 ')' 일 경우에 한개 더잘림
                    answer++;
                }
            }
            i++;
        }
        return answer;
    }
}

 

 

[Kotlin]

코틀린에서 withIndex()는 처음 사용해보는데 정말 유용한 거 같습니다.!!

import java.util.Stack

internal class Solution {

    fun solution(arrangement: String): Int {
        var answer = 0
        val stack = Stack<Char>()
        for ((i, c) in arrangement.toCharArray().withIndex()) {
            if (c == '(') {
                stack.add(c)
            } else {
                stack.pop()
                if (arrangement[i - 1] == '(') { // 왼쪽 막대기 잘려야할 개수, 이전께 '(' 일 경우 레이저의 왼쪽부분 잘리는 개수를 더함
                    answer += stack.size
                } else { // 오른쪽 막대기 잘리는 부분 하나 증가 ,이전께 ')' 일 경우에 한개 더잘림
                    answer++
                }
            }
        }
        return answer
    }
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다@!