99클럽 코테 스터디 7일차 TIL + 쇠막대기(백준 10799번)

✅ 오늘의 학습 키워드

- 스택(Stack)

- 벡터(Vector)

---

✅ 공부한 내용

오늘은 백준 10799번 '쇠막대기' 문제를 풀어보았다. 이 문제는 괄호로 표현된 쇠막대기와 레이저의 위치를 파악하여 최종적으로 쇠막대기가 몇 조각으로 나눠지는지 계산하는 문제이다.

문제 요약

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다.
• 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 '( )'으로 표현된다.
• 쇠막대기의 왼쪽 끝은 '(' , 오른쪽 끝은 ')'으로 표현된다.
• 레이저가 쇠막대기를 자르면 조각이 쇠막대기를 자른 후 남은 조각의 총 개수를 구하는 것이 목표이다.

풀이 로직

이 문제는 스택 또는 벡터를 스택처럼 사용하여 해결할 수 있다. 벡터를 연습하고 싶어 벡터를 사용했다.

풀이 로직은 크게 다음과 같다.

입력된 괄호 문자열을 한 문자씩 순회한다. (for 문 사용)
1. 여는 괄호 '('를 만나면:

- 현재 인덱스를 벡터에 저장한다. (opens.push_back(i))

2. 닫는 괄호 ')'를 만나면:

• 가장 최근에 저장한 여는 괄호의 인덱스를 가져와서 lastPosition 변수에 저장한다. (opens.back())
• 벡터에서 해당 여는 괄호를 제거한다. (opens.pop_back())
• 레이저인지 확인: 마지막 여는 괄호 위치 다음(lastPosition + 1)에 바로 닫는 괄호가 있는지 확인한다.
  • 레이저라면 -> 현재 벡터에 남아있는 여는 괄호의 개수(진행 중인 쇠막대기 수)만큼 조각을 추가한다(pieces += opens.size()).
  • 레이저가 아니라면 -> 쇠막대기의 끝으로 간주하고 조각을 1개 추가한다(pieces += 1).

3. 최종적으로 계산된 총 조각 수를 반환한다.

int countPiece(string &brackets) {
    // 여는 괄호를 벡터에 저장
    vector<int> opens;

    // 총 조각 수 저장
    int pieces = 0;

    // 괄호 길이만큼 문자열 순회 for문
    for (int i = 0; i < brackets.length(); i++) {

        // 현재 문자
        char c = brackets[i];

        // 여는 괄호일 경우
        if (c == '(') {
            opens.push_back(i);
        } 
        // 닫는 괄호일 경우
        else {
            int lastPosition = opens.back(); // 마지막 여는 괄호 위치 저장
            opens.pop_back(); // 제거

            // 레이저인지 확인 (여는 괄호 다음에 바로 닫는 괄호가 오는지 확인)
            bool laser = (brackets[lastPosition + 1] == ')');

            // 레이저일 경우
            if (laser) {
                int bars = opens.size(); // 현재 쇠막대기의 개수 확인
                pieces += bars; // 막대 수만큼 조각 추가
            }  
            // 레이저가 아닐 경우
            else { 
                pieces += 1; // 막대 끝이면 조각 1개 추가
            }
        }
    }

    return pieces;
}

---

✅ 나 혼자 디버깅...!! 

예제 입력 1을 넣어 출력이 17이 나오도록 (내가) 이해하기 쉽게 나 혼자 디버깅을 해보았다. ㅋㅋㅋㅋ

 

 

---

✅ 오늘의 회고

- 😳 어떤 문제가 있었고, 나는 어떤 시도를 했는지

처음에는 괄호 문자열을 어떻게 해석해야 할지 헷갈렸다. 레이저와 쇠막대기를 구분하는 방법이 명확하지 않았다. 먼저 문자열을 단순히 순회하면서 괄호 개수를 세는 방식을 시도했지만, 레이저와 쇠막대기의 구분이 제대로 되지 않았다.

그 후 스택을 사용해야 한다는 힌트를 얻고, 스택을 활용한 접근 방식을 생각했다. 하지만 스택 대신 벡터를 사용하여 구현하는 방법으로 시도해 보았다.

- 🤔 어떻게 해결했는지

핵심 아이디어는 레이저와 쇠막대기의 끝을 구분하는 것이다.
닫는 괄호를 만났을 때, 마지막 여는 괄호 위치 다음(lastPosition + 1)에 바로 닫는 괄호가 있는지 확인한다. 그렇지 않으면 쇠막대기의 끝으로 해석하는 방법을 적용했다.

이를 위해 여는 괄호의 위치를 벡터에 저장하고, 닫는 괄호를 만날 때마다 가장 최근의 여는 괄호 위치를 꺼내 비교하는 방식을 사용했다. 레이저인 경우 현재 벡터에 남아있는 여는 괄호의 수(즉, 현재 활성화된 쇠막대기 수)만큼 조각이 추가되고, 쇠막대기 끝인 경우 1개의 조각만 추가되는 로직을 구현했다.

- 🤩 무엇을 새롭게 알았는지

1. 벡터를 스택처럼 활용하는 방법: C++에서 벡터의 push_back(), back(), pop_back() 메서드를 사용하여 스택과 동일한 기능을 구현할 수 있다는 것을 배웠다.
2. 타입 불일치 경고 해결 방법: C++에서 타입 불일치 경고를 해결하는 여러 방법(캐스팅, size_t 사용 등)에 대해 알았다.
   아래와 같은 타입 불일치 오류가 떴다.

Main.cc: In function ‘int countPiece(std::string&)’:
Main.cc:31:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   31 |     for (int i = 0; i < brackets.length(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~

이것을 해결하기 위해 캐스팅 또는 size_t를 사용하면 위와 같은 타입 불일치 경고는 해결된다.

for (int i = 0; i < (int)brackets.size(); i++) // 캐스팅 사용

for (size_t i = 0; i < brackets.size(); i++) // size_t 사용

위의 방법은 좀 어려울 수도 있다고 생각되어
아래처럼 다른 사람의 풀이법인 스택으로 문자 비교를 통해 해결한 방법을 보았는데 좀 더 이해하기 쉽게 해결한 것 같다. 나는 인덱스(위치)를 통해 하느라 좀 더 코드가 길어진 것 같네...

for (int i = 0; i < str.size(); i++) {
    // 레이저인 경우: '(' 다음에 바로 ')'가 온다면
    if (str[i] == '(' && str[i+1] == ')') {
        // 현재 스택에 있는 모든 쇠막대기(여는 괄호 수)만큼 조각 추가
        cnt += s.size();
        // 닫는 괄호를 건너뛰기 위해 인덱스 증가
        i++;
    }

    // 쇠막대기의 시작인 경우: 여는 괄호 '('
    else if (str[i] == '(') {
        // 스택 저장
        s.push(i);
    }

    // 쇠막대기의 끝인 경우: 닫는 괄호 ')'
    else if (str[i] == ')') {
        // 조각 추가
        cnt++;
        // 스택 제거
        s.pop();
    }
}

---

✅ 전체 코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int countPiece(string &brackets) {
    vector<int> opens;
    int pieces = 0;

    for (int i = 0; i < (int)brackets.size(); i++) {

        char c = brackets[i];

        if (c == '(') {
            opens.push_back(i);
        } 

        else {
            int lastPosition = opens.back();
            opens.pop_back();

            bool laser = (brackets[lastPosition + 1] == ')');

            if (laser) {
                int bars = opens.size();
                pieces += bars;
            } 
            else {
                pieces += 1;
            }
        }
    }

    return pieces;
}

int main() {
    string input;

    cin >> input;   
    int result = countPiece(input);
    cout << result << '\n';

    return 0;
}