Coding Test Study - 4주차

Checking·2021년 5월 9일
0

Coding Test Study

목록 보기
4/22

스택/큐

프린터

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

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    priority_queue <int> priority_file(priorities.begin(), priorities.end());
    queue <pair<int, int>> order;

    for (int i=0; i<priorities.size(); i++) {
        order.push({i, priorities[i]});
    }

    while (true) {
        if (priority_file.top() == order.front().second) {
            if (location == order.front().first) {
                answer++;
                break;
            } else {
                answer++;
                order.pop();
                priority_file.pop();
            }
        } else {
            order.push(order.front());
            order.pop();
        }
    }

    return answer;
}

/*
정확성  테스트
  테스트 1 〉	통과 (0.01ms, 3.96MB)
  테스트 2 〉	통과 (0.02ms, 3.79MB)
  테스트 3 〉	통과 (0.01ms, 3.96MB)
  테스트 4 〉	통과 (0.01ms, 3.96MB)
  테스트 5 〉	통과 (0.01ms, 3.93MB)
  테스트 6 〉	통과 (0.01ms, 3.88MB)
  테스트 7 〉	통과 (0.01ms, 3.95MB)
  테스트 8 〉	통과 (0.02ms, 3.95MB)
  테스트 9 〉	통과 (0.01ms, 3.97MB)
  테스트 10 〉	통과 (0.01ms, 3.96MB)
  테스트 11 〉	통과 (0.02ms, 3.96MB)
  테스트 12 〉	통과 (0.01ms, 3.78MB)
  테스트 13 〉	통과 (0.01ms, 3.95MB)
  테스트 14 〉	통과 (0.01ms, 3.92MB)
  테스트 15 〉	통과 (0.01ms, 3.78MB)
  테스트 16 〉	통과 (0.01ms, 3.87MB)
  테스트 17 〉	통과 (0.02ms, 3.94MB)
  테스트 18 〉	통과 (0.01ms, 3.93MB)
  테스트 19 〉	통과 (0.02ms, 3.83MB)
  테스트 20 〉	통과 (0.01ms, 3.96MB)
  
채점 결과
  정확성: 100.0
  합계: 100.0 / 100.0
*/

다리를 지나는 트럭

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

using namespace std;

void move_truck(queue <pair<int, int>> & bridge, int move_pos) {
    for (int i=0; i<bridge.size(); i++) {
        bridge.push({bridge.front().first + move_pos, bridge.front().second});
        bridge.pop();
    }
}

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int now_bridge_weight = 0;
    queue <pair<int, int>> truck_on_bridge;
    queue <int> wait_truck;
    
    for (auto w:truck_weights) {
        wait_truck.push(w);
    }
    
    while (wait_truck.size()) {
        if (now_bridge_weight + wait_truck.front() <= weight) {
            if (truck_on_bridge.front().first == bridge_length) {
                now_bridge_weight -= truck_on_bridge.front().second;
                truck_on_bridge.pop();
            }
            
            now_bridge_weight += wait_truck.front();
            truck_on_bridge.push({0, wait_truck.front()});
            wait_truck.pop();
            
            move_truck(truck_on_bridge, 1);
            
            answer++;
        } else if (now_bridge_weight + wait_truck.front() - truck_on_bridge.front().second <= weight) {
            int truck_move = bridge_length - truck_on_bridge.front().first + 1;

            now_bridge_weight -= truck_on_bridge.front().second;
            truck_on_bridge.pop();

            move_truck(truck_on_bridge, truck_move);

            answer += truck_move;

            now_bridge_weight += wait_truck.front();
            truck_on_bridge.push({1, wait_truck.front()});
            wait_truck.pop();

        } else{
            int truck_move = bridge_length - truck_on_bridge.front().first + 1;

            now_bridge_weight -= truck_on_bridge.front().second;
            truck_on_bridge.pop();

            move_truck(truck_on_bridge, truck_move);

            answer += truck_move;
        }
    }
    
    while (truck_on_bridge.size()) {
        int truck_move = bridge_length - truck_on_bridge.front().first + 1;
        truck_on_bridge.pop();

        move_truck(truck_on_bridge, truck_move);

        answer += truck_move;
    }
    
    return answer;
}

/*
정확성  테스트
  테스트 1 〉	통과 (0.01ms, 3.96MB)
  테스트 2 〉	통과 (0.01ms, 4MB)
  테스트 3 〉	통과 (0.01ms, 3.97MB)
  테스트 4 〉	통과 (0.06ms, 3.97MB)
  테스트 5 〉	통과 (0.07ms, 3.95MB)
  테스트 6 〉	통과 (0.09ms, 3.99MB)
  테스트 7 〉	통과 (0.01ms, 3.98MB)
  테스트 8 〉	통과 (0.01ms, 3.78MB)
  테스트 9 〉	통과 (0.02ms, 3.97MB)
  테스트 10 〉	통과 (0.01ms, 3.96MB)
  테스트 11 〉	통과 (0.01ms, 4MB)
  테스트 12 〉	통과 (0.01ms, 3.98MB)
  테스트 13 〉	통과 (0.01ms, 3.96MB)
  테스트 14 〉	통과 (0.01ms, 3.97MB)
  
채점 결과
  정확성: 100.0
  합계: 100.0 / 100.0
*/
profile
(ง ᐖ)ว

0개의 댓글