시험기간이어도 코테 연습은 꾸준히 하자

시험공부하다가 너무 지루해서 풀어보았다.
시험 기간에는 코테 연습도 이렇게 재밌을 수가 없다.

5분 내에 후딱 풀 수 있는 Lv.1 짜리만 건드렸다.

1 K번째 수 (정렬, split)

---

(코딩테스트 연습> K번째수)

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    
    vector<int> answer;
    int col = commands.size();
    vector<int> A;
    for(int i = 0; i < col; i++) { // 3번 반복
        A.clear();
        int st = commands[i][0]-1;
        cout << "\nstarting index : " << st << "\n";
        int en = commands[i][1];
        cout << "ending index : " << en << "\n";

        for(int j = st; j < en; j++){
            A.push_back(array[j]); //split해줌
        }
        sort(A.begin(),A.end());
        for(int i = 0; i < A.size(); i++){
            cout << A[i] << " ";
        }
        int idx = commands[i][2]-1;
        answer.push_back(A[idx]);
    }
    return answer;
}

2 같은 숫자는 싫어(스택)

---

[코딩테스트 연습] 같은 숫자는 싫어

#include <vector>
#include <iostream>
#include <stack>
#include <algorithm>

using namespace std;
stack<int> stk;
vector<int> solution(vector<int> arr) 
{
    vector<int> answer;
    stk.push(arr[0]);
    for(int i = 1; i < arr.size(); i++) {
        int k = arr[i];
        if(stk.top() == k){
            continue;
        }
        else {
            stk.push(k);
        }
    }
    while(!stk.empty()){
        int ele = stk.top();
        stk.pop();
        answer.push_back(ele);
    }
    reverse(answer.begin(), answer.end());
    return answer;
}

3 최소 직사각형

---

뇌피셜로 문제 풀다가 시간 복잡도 계산에서 버벅거렸다.
넓이가 최소이려면 w,h 조합을 어떻게 가져가는 게 좋을까? 란 생각을 하다가...

가장 작은 지갑의 크기는
(명함의 긴 변 중 가장 긴 변) * (명함의 짧은 변 중 가장 긴 변)이 된다.

라는 규칙성을 구글링 해서 알아냈다! 왜 이 생각을 못했을까...
조금 더 설계하기 쉽게 설명해보자면,

처음 풀이

---

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> sizes) {
    int answer = 0;
    int w = 0; int h = 0;
    for(int i = 0; i < sizes.size(); i++){
        if(sizes[i][0] < sizes[i][1]) {
            // 더 큰 게 w가 되도록 swap해줌
            int tmp = sizes[i][1];
            sizes[i][1] = sizes[i][0];
            sizes[i][0] = tmp;
        }
        w = max(w, sizes[i][0]);
        h = max(h, sizes[i][1]);
    }
    answer = w * h;
    return answer;
}

더 간결한 버전

---

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> sizes) {
    int answer = 0;
    int w = 0; int h = 0; // w가 더 긴 변대로 정렬하도록, h는 짧은 변 중 긴 변 
    for(int i = 0; i < sizes.size(); i++){
        w = max(w, max(sizes[i][0], sizes[i][1]));
        h = max(h, min(sizes[i][0], sizes[i][1]));
    }
    answer = w * h;
    return answer;
}

4 더 맵게(힙)

---

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<>> pq; // min heap 생성
    for(int i = 0; i < scoville.size(); i++){
        pq.push(scoville[i]);
    }
    while(pq.size() >= 2 && pq.top() < K){
        int n1 = pq.top(); pq.pop();
        int n2 = pq.top(); pq.pop();
        int new_scov = n1 + (2*n2);
        answer++;
        pq.push(new_scov);
    }
    if(pq.top() >= K) {
            return answer;
    }
    return -1;
}

• 반성 = while문 작성할 때 !pq.empty()를 습관적으로 써서 core dump 에러가 발생하였다... 해당 문제에서는 top값을 2개 뽑아내야 하니까 조금 더 신중했어야 했는데.

6 올바른 괄호(스택)

---

#include <string>
#include <iostream>
#include <stack>
using namespace std;

bool solution(string s)
{
    bool answer = false;
    stack<char> stk;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == ')'){
            if(!stk.empty() && stk.top() == '(') stk.pop();
            else stk.push(s[i]);
        }
        else {
            stk.push(s[i]);
        }
    }
    
    if(stk.size() == 0){
        answer = true;
    }
    return answer;
}