[Programmers 문제풀이 JAVA] Level 2 쇠막대기

 

📄 쇠막대기

🔗 문제 풀러가기

---

스택을 이용해서 문제를 해결 할 수 있습니다. 처음 문제를 접했을 때 쇠막대기가 끝나는 시점에서 해당 쇠막대기가 포함하고 있는 레이저만큼 조각을 생성하는 방법을 생각하였습니다. 하지만 이렇게 접근하다 보니 겹쳐 있는 쇠막대기에 대해 처리해야 할게 너무나 많아져 간단하게 처리 할 방법을 생각하였습니다. 문제의 풀이 방식은 아래와 같습니다.

먼저 레이저가 나오면 무조건 지금까지 쌓인 쇠막대기 만큼의 조각이 생깁니다. 따라서 레이저가 나오면 스택에 있는 쇠막대기의 개수 만큼 조각을 추가 해줍니다. 문제의 예시에서 첫 번째 레이저를 만났을 때를 가정해본다면 다음과 같습니다.

 

"(((()" 이렇게 첫 번째 레이저를 만나게 된다면 총 3개의 조각이 무조건 생기게 됩니다. 그 다음 레이저를 만났을 때의 경우는 "(((()()" 입니다. 이 경우 현재 3개의 쇠막대기가 겹쳐져 있으므로 역시 무조건 3개의 조각이 생기게 됩니다. 다음으로 고려해야 할 사항은 레이저가 아닌 ')'를 만나게 되었을 때 입니다. 이 경우 겹쳐 있던 쇠막대기 중 하나가 끝나는 시점 입니다.

 

"(((()())"의 상황에서 고려해야 할 점은 (()())입니다. 이때 레이저에 의해 만들어진 조각들(레이저의 왼쪽편에 있는 조각들)은 이미 구했기 때문에 마지막으로 잘려서 생긴 끝조각 1개를 추가 해줘야 합니다. 그림을 보면 더 쉽게 이해할 수 있습니다. 이때 주의해야 할 점은 쇠막대기의 끝부분이 나왔기 때문에 스택에 저장된 쇠막대기 중 1개를 제거해줘야 합니다.

 

Stack을 직접 구현하거나 Stack 클래스를 이용해서 문제를 해결해도 되지만 스택의 개념만을 이용해 코드를 작성하였습니다. 만약 스택을 사용하고 싶다면 int ironBarStack을 Stack으로 바꾸기만 하면 됩니다.

 

글보단 소스코드를 보면 쉽게 이해할 수 있습니다.

 

---

🌱 Solution 함수

final char LEFT_PARE = '(';

public int solution(String arrangement) {
    int pieceOfIronBar = 0;
    int ironBarStack = 0;

    for (int i = 0; i < arrangement.length(); i++) {
        if (isLeftPare(arrangement.charAt(i))) {
            ironBarStack++;
        } else {
            ironBarStack--;
            if (isLeftPare(arrangement.charAt(i - 1))) {
                // 레이저
                pieceOfIronBar += ironBarStack;
            } else {
                pieceOfIronBar++;
            }
        }
    }

    return pieceOfIronBar;
}

🌱 isLeftPare 함수

왼쪽 괄호인지 확인하는 함수입니다.

private boolean isLeftPare(char ch) {
    return ch == LEFT_PARE;
}

---

🔈 궁금한점이 있다면?

댓글 또는 Github Issues 남겨주세요. 모르는 부분이 있다면 함께 고민해서 문제를 해결해보아요

💡 Github에 더 많은 문제 풀이가 있습니다.

Programmers 문제 풀이

BaekJoon Online Judge 문제 풀이