쇠막대기 문제풀이(C++, 스택/큐)[프로그래머스]

안녕하세요 멍청한 토끼입니다.

이번 문제는 프로그래머스의 스택/큐 Lv2에 해당하는

쇠막대기 문제 입니다.

포스팅을 시작하겠습니다.

 

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

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

불러오는 중입니다...

 

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

4. 결과

---

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

---

1. 문제 설명

여러 개의 쇠막대기를 레이저로 절단하려고 합니다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자릅니다. 쇠막대기와 레이저의 배치는 다음 조건을 만족합니다.

- 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있습니다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓습니다. - 각 쇠막대기를 자르는 레이저는 적어도 하나 존재합니다. - 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않습니다.

 

문제!!

쇠막대기와 레이저의 배치를 표현한 문자열 arrangement가 매개변수로 주어질 때, 잘린 쇠막대기 조각의 총 개수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

arrangement의 길이는 최대 100,000입니다. arrangement의 여는 괄호와 닫는 괄호는 항상 쌍을 이룹니다.

 

예시

쇠막대기 그림

수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향입니다. 이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있습니다.

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

 

위 예의 괄호 표현은 그림 위에 주어져 있습니다. 쇠막대기는 레이저에 의해 몇 개의 조각으로 잘리는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘리고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘립니다.

 

Arrangement	return
"()(((()())(())()))(())"	17

 

---

2. 문제풀이

이번 문제는 int 형, 벡터, 큐, 스택 어떤걸 써도 풀 수 있습니다. 그렇지만 큐/스택 문제이니 이번에는 스택을 이용하여 문제를 풀어보도록 하겠습니다. 필요한 것들을 생각해 보도록 하겠습니다. 1. 총 잘라진 쇠막대기 -> answer 2. 작업대 위의 쇠막대기 -> num(스택) --------------------------------------------------------------------------------------------------- 1. 괄호가 열고 바로 닫히는 문자열이 나왔다면 그것은 레이저이다. 따라서 쇠막대기의 개수를 증가 시켜야 한다. 2. 괄호가 열리는 부분은 작업대 위에 쇠막대기를 추가하는 작업이다. 3. 괄호가 닫히는 부분은 (전에 열리지 않았는데->레이저가 아님) 쇠막대기를 회수하는 부분이다. 따라서 레이저가 아니면 쇠막대기 개수를 증가시켜야 한다.  -------------------------------------------------------------------------------------------------- 간단한 예시 생각 입력값 : "(((())))" 이면 쇠막대기가 3개이고 레이저가 1개이다. 따라서 막대기는 6개가 나올것이다.(그림은 아래에 있습니다.) '('가 열릴때마다 쇠막대기를 추가를 하다보면 처음을 )를 만나게 됩니다. 그러면 전 괄호는 (이었으므로 레이저로 판단을 하면 됩니다.->(stack에 1개씩 푸시) 그러면 쇠막대기가 4개추가로 표시되어있으므로 1개를 줄여줍니다.( '('가 4개이므로)->(stack pop) answer에 쇠막대기 3개를 추가합니다.->(answer += stack.size()) 전 괄호가 '('가 아님에도 ')'가 나왔다면 쇠막대기 끝부분 입니다. 따라서 answer에 쇠막대기를 1개 추가합니다. ->(answer++) 그렇다면 닫히는 괄호는 3개가 더 나오므로 레이저부분에서 3개추가 닫히는 괄호에서 3개추가 총 6개가 됩니다.

쇠막대기

 

---

3. 소스코드

 

3.1 주석없는 코드

#include <vector>
#include <stack>
#include <string>
 
using namespace std;
 
int solution(string arrangement) {
    int answer = 0;
    stack<int> num;
    for (int i = 0; i < arrangement.length(); i++){
        if (arrangement[i] == '(')
            num.push(1);
        else{
            num.pop();
            if (arrangement[i - 1] == '(')
                answer += num.size();
            else
                answer++;
        }
    }
    return answer;
}

3.2 주석있는 코드

#include <vector>
#include <stack>
#include <string>
 
using namespace std;
 
int solution(string arrangement) {
    int answer = 0;
    stack<int> num;
    //글자의 처음부터 마지막까지 순회
    for (int i = 0; i < arrangement.length(); i++){
        //여는 괄호라면 스택에 추가
        if (arrangement[i] == '(')
            num.push(1);
        else{
            //닫는 괄호라면 스택에서 하나제거
            num.pop();
            //전 기호가 여는 기호였다면 레이저이므로 열린괄호만큼 개수추가
            if (arrangement[i - 1] == '(')
                answer += num.size();
            else//전 기호가 여는 기호가 아니었다면 쇠막대기의 마지막이므로 1개 추가
                answer++;
        }
    }
    return answer;
}

3.3 테스트 코드 추가

#include <iostream>
#include <vector>
#include <stack>
#include <string>
 
using namespace std;
 
int solution(string arrangement) {
    int answer = 0;
    stack<int> num;
    //글자의 처음부터 마지막까지 순회
    for (int i = 0; i < arrangement.length(); i++){
        //여는 괄호라면 스택에 추가
        if (arrangement[i] == '(')
            num.push(1);
        else{
            //닫는 괄호라면 스택에서 하나제거
            num.pop();
            //전 기호가 여는 기호였다면 레이저이므로 열린괄호만큼 개수추가
            if (arrangement[i - 1] == '(')
                answer += num.size();
            else//전 기호가 여는 기호가 아니었다면 쇠막대기의 마지막이므로 1개 추가
                answer++;
        }
    }
    return answer;
}
 
void print(string a, int answer) {
    int t = solution(a);
    cout << t << ", ";
    if (a == answer)
        cout << "정답" << endl;
    else
        cout << "틀림" << endl;
}
 
int main(){
    print("()(((()())(())()))(())", 17);
    return 0;
}

4. 결과

쇠막대기 테스트 결과