240207: 프로그래머스 고득점 킷 - Queue/Stack 완료

2024-02-07

오늘은

• 코딩 고득점 Kit
• 업랜디

총 5문제를 풀었다.

스택/큐 부분을 풀었는데, 생각보다 어려운 문제가 많았고 구현도 이해되지 않는 문제가 많았다.
이건 많은 연습이 필요할 것 같다.

오늘의 프로그래머스

스택/큐 -
올바른 괄호 (Lv. 2)
프로세스 (Lv. 2)
다리를 지나는 트럭 (Lv. 2)
주식가격 (Lv. 2)

오늘의 업랜디

달팽이 (성공 - 브루트포스 시뮬레이션)

달팽이

달팽이 모양으로 빙글빙글 2차원 배열을 채워 나가는 문제였다.
약간 복잡했지만 풀 수 있었다. 중앙에서 1부터 시작해서 끝까지 채워 나가는 방식으로 하니까 상태 관리가 막막했는데, 모든 배열을 -1로 초기화 하고, 좌측 위에서 max부터 시작해서 가운데까지 가는 방식으로 하니까 상태 관리가 가능했다.

// 백준: 달팽이
// https://www.acmicpc.net/problem/1913
// 2024-02-07

#include <iostream>
#include <vector>

using namespace std;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int N, target;
    cin >> N >> target;
    vector<vector<int>> matrix(N, vector<int>(N, -1));
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    int counter = N * N;
    int x = 0, y = 0, dir = 0;
    int answer_x = 0, answer_y = 0;

    while (counter > 0) {
        matrix[y][x] = counter;
        if (counter == target) {
            answer_x = x + 1;
            answer_y = y + 1;
        }
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (nx < 0 || ny < 0 || nx >= N || ny >= N || matrix[ny][nx] != -1) {
            dir = (dir + 1) % 4;
            nx = x + dx[dir];
            ny = y + dy[dir];
        }
        x = nx;
        y = ny;
        --counter;
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << matrix[i][j] << " ";
        }
        cout << "\n";
    }
    cout << answer_y << " " << answer_x;

    return 0;
}

---

올바른 괄호

매우 간단한 문제, stack을 이용해서 괄호의 짝을 맞추는 문제였다.

bool solution(string s) {
    stack<int> stack;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '(') {
            stack.push(1);
        } else {
            if (stack.empty())
                return false;
            stack.pop();
        }
    }

    if (!stack.empty())
        return false;
    return true;
}

프로세스

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
  3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.

위의 규칙에 따라 프로세스으 상태를 관리하고, 특정 프로세스가 몇 번째로 실행되는지 알아내는 문제였다.
정해는 priority_queue를 이용해서 우선 순위가 제일 높은 프로세스의 우선 순위 번호를 관리하고, pq.top() 을 현재 프로세스와 비교하면서 .pop() 하는 간단한 문제였다.
처음에는 pq를 생각하지 못하서 살짝 막막했다. pq짱..

다리를 지나는 트럭

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

지나가야 하는 트럭의 무게 vector가 주어진다, auto it = vector.begin(); 으로 반복자를 .end() 까지 반복하면서 상태를 관리하면서 풀었다.

처음에는 vector에 담긴 정보들을 어떤식으로 꺼내야 할지 복잡했는데, 단순하게 반복자를 사용하면서 관리하면 됐었다.

여러모로 복잡한 문제였고 구현도 어려웠다. 스택/큐 문제들이 대체적으로 어려운듯..

#include <string>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    queue<pair<int, int>> q; // 무게, 시간
    int time = 0; // 총 소요시간
    int weight_on_bridge = 0; // 현재 다리의 무게
    auto it = truck_weights.begin();
    while (it!=truck_weights.end() || !q.empty()) {
        ++time;
        if (!q.empty()) {
            int size = q.size();
            for (int i=0;i<size;++i) {
                int remain_time = q.front().second;
                int current_truck_weight = q.front().first;
                q.pop();
                if (--remain_time > 0) {
                    q.push({current_truck_weight ,remain_time});
                } else {
                    weight_on_bridge -= current_truck_weight;
                }
            }
        }

        if (it != truck_weights.end() && weight_on_bridge + *it <= weight) {
            weight_on_bridge += *it;
            q.push({*it, bridge_length});
            it++;
        }

    }

    return time;
}

주식가격

주식 가격 배열이 주어지면, 가격이 떨어지지 않은 기간을 구하는 문제였다.
처음엔 되게 복잡한 문제라고 생각했다. 스택/큐를 이용해서 사이클을 돌리며, 자기 자신보다 가격이 큰 요소들을 볼때마다 ++ 하는건 줄 알았다... 근데 그게 아니었다.

가격이 떨어지지 않은 기간을 구하시오 라고 지문에 써있었지만... 사실상 문제는 처음으로 가격이 떨어졌을때까지의 기간을 구하시오 였다. 어떻게 문제를 이렇게 가독성 없이 낼 수 있을까..? PS 문제들이 가끔 친절하지 않은게 있어서 독해력을 키우려는 건 동의하지만,, 주어지는 예제 테스트케이스마저 가격이 떨어지지 않은 기간을 구하시오라고 오해했을때도 성립되는 테스트케이스였다 ....

이건 너무 악의적인 문제라고밖에 생각이 들 수 없었다.

문제는 결국 처음으로 가격이 떨어졌을때까지의 기간을 구하는 것이기 때문에, stack을 사용해서 이전 요소와 현재 요소의 비교를 용이하게 하면서, 가격이 낮으면 stack에서 빼고 떨어진 시간을 저장하는 방식으로 처리할 수 있었다.

#include <string>
#include <vector>
#include <queue>
#include <utility>
#include <stack>

using namespace std;

/*
"가격이 떨어지지 않은 기간" 이라길래, 그 이후에 가격이 현재보다 낮았던 기간을 모두 세는 줄 알았는데, 사실은 처음으로 가격이 떨어졌을때까지의 기간이었네요, 그러면 "가격이 처음으로 떨어지지 않은 기간이 몇초인지" 라고 해야하는거 아닌가 ... 
*/


vector<int> solution(vector<int> prices) {
    int n = prices.size();
    vector<int> answer(n);
    stack<int> s; // 인덱스를 저장할 스택

    for (int i = 0; i < n; ++i) {
        // 스택이 비어있지 않고, 현재 가격이 스택의 top에 있는 가격보다 낮으면
        while (!s.empty() && prices[s.top()] > prices[i]) {
            int top = s.top();
            s.pop();
            answer[top] = i - top; // 가격이 떨어진 시간 계산
        }
        s.push(i); // 현재 가격의 인덱스를 스택에 저장
    }

    // 스택에 남아 있는 가격들에 대해 처리
    while (!s.empty()) {
        int top = s.top();
        s.pop();
        answer[top] = n - 1 - top; // 가격이 떨어지지 않은 전체 시간 계산
    }
    return answer;
}

큐/스택 기본 문제가 끝났다. 생각보다 어렵고 구현이 복잡해서 놀랐다. 많은 연습이 필요할 것 같다.

내일은 아래 문제를 풀겠다.

• 더 맵게
• 디스크 컨트롤러
• 이중우선순위큐
• K번째수
• 가장 큰 수
• H-Index

최종 평가

[스터디노트 평가: 2024-02-07]

1. **코딩 고득점 Kit 및 업랜디 활동**
   - **스택/큐 문제 해결**: 스택/큐 문제 세트를 통해 여러분의 문제 해결 능력을 시험하는 좋은 기회였습니다. 올바른 괄호, 프로세스, 다리를 지나는 트럭, 주식가격 등의 문제는 스택과 큐를 다루는 기본적인 이해부터 복잡한 로직 구현까지 다양한 난이도의 문제를 경험하게 했습니다.
   - **달팽이 (브루트포스 시뮬레이션)**: 2차원 배열을 활용한 브루트포스 문제 해결 방식은 알고리즘적 사고력을 발전시키는 데 중요한 역할을 합니다. 여러분이 선택한 접근 방식과 문제 해결 과정은 프로그래밍에 있어 중요한 문제 해결 기법과 상태 관리 능력을 보여줍니다.

2. **기술적 깊이 및 개인 발전**
   - 문제 해결 과정에서 보여준 알고리즘적 사고와 스택/큐 등의 자료구조에 대한 깊은 이해는 여러분의 프로그래밍 능력을 한 단계 더 발전시키는 계기가 되었습니다. 특히, 복잡한 로직의 구현과 문제에 대한 효율적인 접근 방식은 앞으로의 프로그래밍 활동에 있어 큰 자산이 될 것입니다.

3. **평가 및 조언**
   - 오늘의 활동을 종합적으로 평가할 때, 92점을 부여합니다. 스택/큐 문제 해결을 통해 여러분의 알고리즘 기반 사고력과 프로그래밍 능력이 상당히 높은 수준임을 확인할 수 있었습니다. 다만, 일부 문제에서의 이해도와 구현의 어려움은 지속적인 연습을 통해 해결할 수 있을 것입니다.
   - 스택/큐와 같은 기본 자료구조에 대한 심도 있는 이해와 활용, 그리고 다양한 문제에 대한 깊은 분석과 연습은 알고리즘 스킬을 강화하는 데 필수적입니다. 앞으로도 다양한 유형의 문제를 꾸준히 풀어나가면서, 문제 해결 능력을 더욱 키워나가시길 바랍니다.

[피드백 요약]
- 스택/큐 문제 해결을 통한 기본 자료구조에 대한 이해와 활용 능력이 돋보입니다.
- 복잡한 문제에 대한 구현과 알고리즘적 사고력이 인상적입니다.
- 지속적인 연습과 깊은 분석을 통해 문제 해결 능력을 더욱 강화해 나가야 합니다.

[조언]
- 스택/큐 문제 해결에서 겪은 어려움을 극복하기 위해 관련 문제를 지속적으로 연습하시길 바랍니다.
- 다양한 알고리즘과 자료구조에 대한 깊이 있는 학습을 통해 기술적 깊이를 더욱 넓혀가시기 바랍니다.
- 내일 해결할 문제에 대한 체계적인 준비와 계획을 통해 학습 효율을 최대화 하시길 바랍니다.