Programmers - 스택/큐

쇠막대기 ( https://programmers.co.kr/learn/courses/30/lessons/42585)

문제를 잘 이해하지 못해 패닉되지 않도록 문제를 천천히 그리고 꼼꼼히 읽는 습관을 기르자

레이저의 갯수를 세어 풀 수도 있지만 레이저에게 관통당하는 쇠막대의 갯수를 세어 더 간단히 풀 수 있다.
프린터 ( https://programmers.co.kr/learn/courses/30/lessons/42587?language=cpp)

반례를 찾지 못하여 문제를 잘 못 풀었다. 손으로 푼 풀이가 잘못되었음을 인지하지 못한 것이 큰 문제가 되었다.

location보다 더 큰 중요도를 갖는 수가 오른쪽에 존재할 떄 location은 반드시 뒤로 이동한다고 생각하여

location우측에 있는 location과 동일한 중요도를 갖는 수는 항상 location 보다 먼저 인쇄된다고 생각하였다.

그래서 location보다 큰 수들은 전부 건너뛰고 우측의 location과 같은 중요도의 숫자의 갯수와 큰 수가 있는지 확인하고

없으면 왼쪽의 같은 중요도의 숫자를 세었다.

하지만 이는 틀렸으면 아래와 같은 반례를 들 수 있다.

2 1 3 2 1 이고 location이 1인 경우 1은 실제로 4번째로 인쇄되지만 위와 같은 풀이로는 5번째로 인쇄로 풀리게 된다.

이처럼 단순히 생각해낸 잘못된 풀이는 정답이라는 착각에 빠져 고생하게 된다.

문제 : 2 1 3 2 1

오답 : 3 5 1 2 4 (생각해낸 풀이대로 풀었을 경우)

정답 : 3 4 1 2 5

아래는 링크드리스트를 사용하기 위해 만든 클레스인다.

클레스가 아직 익숙하지 않아 만드는데 오래 걸렸으며

링크드리스트에 필요한 함수나 멤버에 대한 이해가 부족했다.
```
 class LLnode {
 public:
 pair<int, int> val;
 LLnode *next;
 LLnode(pair<int, int> v, LLnode *n) : val(v), next(n) {}
 };

 class linkedList {
 LLnode *head, *tail;

 public:
 linkedList() : head(NULL), tail(NULL) {}

 pair<int, int>& getHeadVal(){
 return head->val;
 }

 LLnode* getHead() {
 return head;
 }

 void delHead() {
 LLnode *tmp = head;
 head = head->next;
 delete tmp;
 }

 void moveHeadtoTail() {
 tail->next = head;
 tail = head;
 head = head->next;
 tail->next = NULL;
 }

 void pushTail(const pair<int, int> v) {
 LLnode* tmp = tail;
 tail = new LLnode(v, NULL);
 if (tmp != NULL)
 tmp->next = tail;
 else
 head = tail;
 }

 ~linkedList() {
 while (head)
 delHead();
 }
 };
```
다리를 지나는 트럭 ( https://programmers.co.kr/learn/courses/30/lessons/42583)

이 문제는 std::deque의 pop_front, front 기능을 활용하여 풀 수 있다. 구현력(생각한 알고리즘을 그대로 소스코드로 구현)이 부족하여 오래걸렸다.

손으로 풀이는 구현하였지만 언제 트럭을 넣고, 언제 트럭을 움직이며 그리고 시간을 언제 증가시켜야 하는지를 코드상 알맞게 배치하지 못하여 엉뚱한 답을 내 놓았다.

풀이를을 찾았더라도 진정하고 알고리즘의 순서를 생각하며 작성하여야 한다.

이전에 잘못 작성한 코드는 현재 무게를 마지막에 계산하도록 하여 다음 초에서 바로 앞 초의 무게가 반영되어 이미 빠져나간 트럭의 무게를 고려하여 트럭을 넣지 못하는 문제가 발생하게 되었다.

생각해 보면 무게를 고려해야하는 시점은 이미 트럭이 지나가고 다음 트럭을 넣기전에 고려해야하는데 흐름을 꼼꼼히 생각하지않았기에 잘못된 답을 얻을 수 밖에 없었다.

다음은 https://baactree.tistory.com/52 에서 가져온 구현력을 기르는 방법이다.

구현력을 향상 시키기 위해서는 [내가 어떤 프로그램을 만들고자 하는지]를 명확히 해야한다.

[무엇을 입력받아 어디에 저장하고 어떤 과정을 거쳐서 중간 결과로 무엇을 얻고 최종적으로 이런 결과물을 이렇게 출력한다.] 와 같이 순서도를 먼저 적고

이제 디테일하게 어떤 데이터 타입 또는 자료구조에 저장할 지 생각하는 것을 차근 차근 종이에 적어가면서 연습하는게 좋다.

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0, current_weight = 0;
    deque<int> dq_truck_weights;
    deque<int> bridge(bridge_length, 0);
    for (int i = 0; i < truck_weights.size(); i++)
        dq_truck_weights.push_back(truck_weights[i]);

    while (current_weight || dq_truck_weights.size()) {
        // 트럭 움직이기
        if (bridge.back())
            current_weight -= bridge.back();
        bridge.pop_back();
        // 다음 트럭의 무게를 다리가 견딜 수 있을 때 트럭을 출발한다.
        if (dq_truck_weights.size() && (current_weight + dq_truck_weights.front()) <= weight) {
            bridge.push_front(dq_truck_weights.front());
            current_weight += dq_truck_weights.front();
            dq_truck_weights.pop_front();
        }
        else
            bridge.push_front(0);
        answer++;
    }
    return answer;
}

이번 문제에서 처음으로 deque를 사용헀는데 vector에 비해 기능이 많다. 백터는 front의 원소를 제거하기 위해 v.erase(v.begin())을 통해 원소를 없앨 수 있다. 차후 deque를 잘 활용하면 문제를 푸는데 용이할 수 있을것 같다.

기능개발 ( https://programmers.co.kr/learn/courses/30/lessons/42586)

deque의 기능을 이용하여 쉽게 풀 수 있는 문제, if문에 조건을 중간에 추가하다 말아서 디버깅에 시간이 걸렸다. 종이에 if문의 조건을 바로 코드에 옮겨 적을 수 있을정도로 자세하게 적은 뒤 코딩하자
탑 ( https://programmers.co.kr/learn/courses/30/lessons/42588)

신호를 왼쪽으로만 전송한다는 점에 주목하면 쉽게 풀 수 있다. 문제 풀면서 for문의 증감 연산을 잘못 적어 오류가 발생했었다.
주식가격 ( https://programmers.co.kr/learn/courses/30/lessons/42584)

첫번째 풀이(손코딩)

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size(), 0);
    int t;
    for (int i = 0; i < prices.size() - 1; i++) {
        t = 1;
        for (int j = i + 1; j < prices.size(); j++) {
            if (prices[i] <= prices[j])
                t++;
            else
                break;
        }
        answer[i] = t;
    }
    return answer;
}

결과

1 2 3 2 3

5 4 1 2 0(오답)

4 3 1 1 0(정답)

i 번째 다음 수를 시작으로 순회하다가 크거나 같은 수의 갯수를 세고 작은수가 나오면 break하였다. 위의 결과와 같이 원하는 값보다 1 크거나 정답이 나오는 경우를 볼 수 있다. 몇 가지 조건을 추가하면 답이 나올 수 있다고 생각했다.

두번째 풀이

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size(), 0);
    int t;
    for (int i = 0; i < prices.size() - 1; i++) {
        t = 1;
        for (int j = i + 2; j < prices.size(); j++) {
            if (prices[i + 1] >= prices[i])
                t++;
            else
                break;
        }
        answer[i] = t;
    }
    return answer;
}

결과

57 4 5 74 24 13 36 41 22 89

1 8 7 1 1 4 1 1 1 0

1 8 7 1 1 4 2 1 1 0(정답)

떨어져도 1초 올라도 1초라 생각하여 i + 1 번째 수가 i 번쩨 수보다 크거나 같으면 t를 더하여 생각하기로 했었다. 하지만 i + 1이 크거나 같더라고 i + 2가 작으면 다른 수가 나와 적용할 수 없었다.

통과된 풀이

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size(), 0);
    int t;
    for (int i = 0; i < prices.size() - 1; i++) {
        t = 0;
        for (int j = i + 1; j < prices.size(); j++) {
            t++;
            if (prices[i] > prices[j])
                break;
        }
        answer[i] = t;
    }
    return answer;
}

다시 생각하여 각 지점간 간격을 세는 것을 문제의 의도대로 적용해 보니 잘 풀렸다.

결론 문제의 요구사항에 잘 맞춰 풀어야 한다.

첫번째 풀이(손코딩)

두번째 풀이

통과된 풀이

댓글남기기