프로그래머스 42746 - 가장 큰 수

문제 링크

생각과 접근

• 이어 붙여서 가장 큰 수를 만드는 문제다.
• 어떤 기준으로 string을 sort해야 이어 붙여서 가장 큰 수를 만들 수 있을까?
  • 실제로 이어 붙여서 비교해보면 된다.

      bool compare(string a, string b){
          return a + b > b + a;
      }

  • 처음 보는 compare 함수 형태라 당황했지만, 꼭 기억해야 하는 compare함수라고 생각된다.

코드

#include <bits/stdc++.h>
using namespace std;

bool compare(string a, string b){
    return a + b > b + a;
}

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> v;

    for(int i = 0 ; i < numbers.size(); i++){
        v.push_back(to_string(numbers[i]));
    }
    sort(v.begin(), v.end(), compare);

    for(int i = 0; i < v.size(); i++){
        if(answer.empty() && v[i] == "0"){
            answer = "0";
            break;
        }
        answer.append(v[i]);
    }
    return answer;
}

채점 결과

프로그래머스 42748 - K번째수

문제 링크

생각 및 접근

• index와 실제 배열에 저장되는 index가 1씩 차이나서 귀찮았던 문제.
• vector temp를 선언해서 array를 새로 담고, commands에서 시키는 대로 원하는 구간을 sort 후, 원하는 답을 answer에 push_back하면 끝나는 문제

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> temp;
    vector<int> answer;

    for(int i = 0; i < commands.size(); i++){
        temp = array;
        sort(temp.begin() + commands[i][0] - 1, temp.begin() + commands[i][1]);
        answer.push_back(temp[(commands[i][0] - 1) + (commands[i][2] - 1)]);
    }

    return answer;
}

채점 결과

프로그래머스 42587 - 프린터

문제 링크

생각과 접근

사족

• 문제 이해를 잘 해야 삽질하지 않는다는 교훈을 얻은 문제.

    // 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
    // 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
    // 3. 그렇지 않으면 J를 인쇄합니다.

• 처음 잘못 이해했을 때 2번 조건에서 J보다 중요도가 높은 문서가 존재하면, 그 문서를 인쇄하는 것으로 이해해서 삽질을 했다.

본론

• queue< pair<int, int> > q;
  • 큐를 사용해서 문제를 풀었다.
  • 큐를 pair를 이용해서 왼쪽에는 index, 오른쪽에는 priorities[index]를 저장하였다.
• 무한루프
  • J에 해당하는 것 q.front() 을 pop한다. (편의상 J라고 부르겠음.)
  • J를 제외한 큐를 순회해서 J의 우선순위보다 높은 원소를 찾는다.
    • 우선순위가 높은 원소가 없다면, J를 인쇄해야 한다.
      • 문제의 답은 location에 해당하는 문서의 인쇄 순서를 찾는 것이므로, J의 인덱스와 location이 일치하는지 확인한다.
        • 일치한다면, 답을 찾은 것이므로 return answer;
        • 일치하지 않는다면, 아무것도 하지 않는다. (이미 J는 pop 되었기 때문에 추가적인 작업이 필요하지 않는다.)
    • 우선순위가 높은 원소가 있다면, J를 큐의 가장 마지막에 넣어야 한다.
      • 우선순위가 높은 원소가 있다는 것을 flag에 저장하였음
      • 큐 순회가 끝나고 나면 J를 push한다.

코드

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;

    queue< pair<int, int> > q;
    for(int i = 0; i < priorities.size(); i++){
        q.push(make_pair(i, priorities[i]));
    }

    while(-1){
        bool flag = true;
        int idx = q.front().first;
        int pri = q.front().second;
        q.pop();

        int size = q.size();
        for(int i = 0; i < size; i++){
            int _idx = q.front().first;
            int _pri = q.front().second;
            q.pop();

            if(pri < _pri){
                flag = false;
            }
            q.push(make_pair(_idx, _pri));
        }

        if(flag == false){
            q.push(make_pair(idx, pri));
        }
        else{
            answer++;
            if(idx == location){
                return answer;
            }
        }
    }
}

채점 결과

프로그래머스 42583 - 다리를 지나는 트럭

문제 링크

생각 및 접근

• 문제의 접근은 이렇게 했습니다.
  • 시간을 1초씩 늘려가는 while문을 돌려야겠다.
  • while문을 돌면서 다리 위를 건너는 트럭의 남은 다리 길이를 1씩 줄여야겠다.
  • 다리 위를 건너는 트럭을 큐에 저장해야겠다.
• queue< pair<int, int> > crossing
  • 다리 위를 지나가는 트럭을 저장하는 큐에는 트럭의 무게와 트럭의 남은 다리 길이를 저장해야 했습니다.
  • pair의 왼쪽은 트럭의 무게를, pair의 오른쪽은 트럭의 남은 다리 길이를 저장했습니다.
  • 큐를 순회하면서, 길이를 하나씩 줄여줍니다. 길이가 1이였다면, 그 트럭은 다리를 지난 트럭이 되므로 다리 위 전체 트럭의 무게를 저장하고 있던 onWeight에서 트럭의 무게를 빼줍니다.
• 트럭을 큐에 넣는 조건
  • 대기하고 있는 트럭이 있고,
  • 대기하고 있는 트럭의 무게 + onWeight가 다리 최대 무게를 넘지 않아야 합니다.
• 무한루프를 빠져나오는 조건
  • 더이상 대기하고 있는 트럭이 없고,
  • 다리를 지나고 있는 트럭 또한 없으면 됩니다.
• 시간을 저장하는 변수 answer
  • while문이 끝나기 전에 answer++; 해줍니다.

코드

#include <bits/stdc++.h>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0, onWeight = 0, waitingIndex = 0;
    queue< pair<int, int> > crossing;

    while(-1){
        int crossingNum = crossing.size();

        for(int i = 0; i < crossingNum; i++){
            int wei = crossing.front().first;
            int len = crossing.front().second;
            crossing.pop();

            if(len <= 1){
                onWeight -= wei;
                continue;
            }
            crossing.push(make_pair(wei, len - 1));
        }

        if(waitingIndex < truck_weights.size() && onWeight + truck_weights[waitingIndex] <= weight){
            crossing.push(make_pair(truck_weights[waitingIndex], bridge_length));
            onWeight += truck_weights[waitingIndex];
            waitingIndex++;
        }

        answer++;

        if(waitingIndex >= truck_weights.size() && crossing.empty())
            break;
    }    
    return answer;
}

채점 결과

프로그래머스 42586 - 기능개발

문제 링크

생각과 접근

• 먼저 각 작업의 끝나는데 걸리는 날 ( vector<int> endDay(progresses_size, 0) ) 을 구한 다음, 그 값을 토대로 answer를 찾으려 했습니다.
• endDay 를 순회하면서 endDay 의 최댓값을 기록하는 변수 temp 와 answer에 push_back할 변수 cnt를 선언했습니다. temp가 갱신되는 순간, answer에 cnt 를 push_back합니다. 최댓값으로 기록된 변수 temp 가 변경되는 시점은 그간 앞의 작업이 끝나길 기다리는 작업들이 temp 일 만큼 걸리는 작업이 끝났으므로 배포가 가능하게 되는 시점입니다.

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    int progresses_size = progresses.size();
    vector<int> answer;
    vector<int> endDay(progresses_size, 0);

    // 각 작업의 끝나는데 걸리는 날을 구하기
    int day = 0, endJob = 0;
    while(endJob < progresses_size){
        day++;
        for(int i = 0; i < progresses_size; i++){
            if(progresses[i] >= 100)    continue;
            progresses[i] += speeds[i];
            if(progresses[i] >= 100){
                endDay[i] = day;
                endJob++;
            }
        }
    }

    int temp = endDay[0], cnt = 1;
    for(int i = 1; i < progresses_size; i++){
        if(temp < endDay[i]){
            temp = endDay[i];
            answer.push_back(cnt);
            cnt = 0;
        }
        cnt++;
    }
    answer.push_back(cnt);
    return answer;
}

채점 결과

프로그래머스 42584 - 주식가격

문제 링크

생각과 접근

• 문제가 스택/큐 분야에 있어서 스택과 큐를 활용해서 문제를 풀어보려다 실패해서 그냥 맨 처음에 생각했던 이중 for문 방식으로 풀었습니다.
• i for문에서 0부터 price_size - 2만큼 돕니다. prices의 마지막 원소를 탐색하지 않는 이유는 맨 마지막 주식 가격은 가격이 떨어질 수 없고, 이에 따라 answer 값이 0으로 고정되기 때문에 나중에 0 하나만 push_back하기로 했습니다.
• j for문에서 i + 1부터 price_size - 1만큼 돕니다. prices[i]보다 prices[j]이 작다면, answer에 j - i를 push_back하고 j for문을 종료합니다. 만약 j for문을 break없이 끝냈다면, answer에 j - i - 1를 push_back합니다.
  • 왜 j - i와 j - i - 1로 나눠서 구분을 하는가?
    • answer는 주식가격이 떨어지지 않는 시간 을 기록합니다. 아래 입출력 예로 설명하겠습니다.

      • 

      • 쉽게 말해서, 주식가격이 떨어지지 않는 시간을 세는 방식은 prices 배열의 ,수를 세는 것 입니다.
      • prices[2]는 prices[3]에서 j for문이 멈추게 됩니다. ,가 하나 있고, j - 1의 값은 3 - 2 = 1로 동일합니다.
      • prices[0]는 prices[4]와 비교를 끝내고 j = 5인채로 j for문이 끝나게 됩니다. ,는 4개 있고, j - i - 1의 값은 5 - 0 - 1로 동일합니다. - 1이 있는 이유는 j for문에서 빠져나올 때 j++되어 그것을 하나 빼주는 것입니다.

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> prices) {
    int i, j, price_size = prices.size();
    vector<int> answer;

    for(i = 0; i < price_size - 1; i++){
        for(j = i + 1; j < price_size; j++){
            if(prices[i] > prices[j]){
                answer.push_back(j - i);
                break;
            }
        }
        if(answer.size() != i + 1){
            answer.push_back(j - i - 1);
        }
    }
    answer.push_back(0);

    return answer;
}

채점 결과

프로그래머스 42585 - 쇠막대기

문제 링크

생각과 접근

• 쇠막대기 문제는 문제의 길이는 짧지만 고민을 정말 많이 해야하는 문제였습니다.
  
  

  

• 위와 같은 경우를 깊게 고민해보았습니다.
• 괄호를 열 경우는 딱히 나뉘는 케이스가 떠오르지 않았습니다.
• 괄호를 닫을 경우 두가지 케이스로 나뉩니다.
  • 첫 번째 : 레이저인 경우
    • 레이저일 경우, 열려있던 괄호만큼 answer를 더해주면 됩니다. (잘린 쇠 파이프 갯수!)
  • 두 번째 : 쇠막대기가 끝나는 경우
    • 쇠막대기가 끝나는 경우, 새로운 쇠막대기가 단 하나 생깁니다.
      
      

      

• 빨간 원이 레이저일 때 더해주는 경우, 파란 원이 쇠막대기가 끝나는 경우입니다.

코드

#include <bits/stdc++.h>
using namespace std;

int solution(string arrangement) {
    int answer = 0;
    stack<int> s;

    for(int i = 0; arrangement[i] != '\0'; i++){
        if(arrangement[i] == '(')   s.push(1);
        else if(arrangement[i] == ')'){
            s.pop();
            if(arrangement[i - 1] == '(')       answer += s.size();
            else if(arrangement[i - 1] == ')')  answer++;
        }
    }
    return answer;
}

채점 결과

프로그래머스 42588 - 탑

문제 링크

생각과 접근

• 문제의 분야는 스택/큐에 있었지만, 굳이 사용하지 않고 for문 두 개를 쓰면 간단히 풀 수 있는 문제였습니다.
• 신호는 오른쪽에서 왼쪽으로 흐르니 heights를 탐색할 때 거꾸로 탐색합니다. (i-for문)
• 두 번째 j-for문에서 i보다 제일 가깝고 heights[i]보다 큰 값을 찾습니다.
  • 큰 값이 있다면, 그 타워의 인덱스를 push_back
  • 큰 값이 없다면, 0을 push_back
• 탐색은 거꾸로 하여 값 또한 거꾸로 push_back되어 있으므로, vector answer에 다시 거꾸로 넣어줍니다.

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> heights) {
    vector<int> answer;
    vector<int> temp;

    for(int i = heights.size() - 1; i >= 0; i--) {
        for(int j = i - 1; j >= 0; j--) {
            if(heights[j] > heights[i]){
                temp.push_back(j + 1);
                break;
            }
            if(j == 0) temp.push_back(0);
        }
        if(i == 0) temp.push_back(0);
    }

    for(int i = temp.size() - 1; i >= 0; i--){
        answer.push_back(temp[i]);
    }
    return answer;
}

채점 결과