23.09.14. 풀었던 문제들

프로그래머스 Lv. 2 최댓값과 최솟값, 4분 30초

 c++에서 delimiter를 사용해 string을 파싱할 줄 알면 바로 풀리는 문제. iss 쓰고 while getline으로 풀면 된다!

string solution(string s) {
    int min_v = INT_MAX;
    int max_v = INT_MIN;
    
    istringstream iss(s);
    string buffer;
    while(getline(iss, buffer, ' ')){
        int v;
        if(buffer[0] == '-'){
            v = stoi(buffer.substr(1));
            v *= -1;
        }
        else{
            v = stoi(buffer);
        }
        
        min_v = min(min_v, v);
        max_v = max(max_v, v);
    }
    
    return to_string(min_v) + " " + to_string(max_v);
}

 

시간복잡도

 s를 파싱하고 최대/최소값을 갱신하는 데 O(n)이 걸린다.

 

 

 

프로그래머스 Lv. 2 최솟값 만들기, 1분 40초

 수학 규칙을 알면 되는 문제. A는 오름차순, B는 내림차순으로 정렬한 후 곱한 것을 더한 것이 답이다.

int solution(vector<int> A, vector<int> B)
{
    sort(A.begin(), A.end(), less<int>());
    sort(B.begin(), B.end(), greater<int>());
    
    int answer = 0, len = A.size();
    for(int i = 0; i<len; i++){
        answer += A[i] * B[i];
    }

    return answer;
}

 

시간복잡도

 정렬에 O(nlogn), 순회에 O(n)

 

 

 

프로그래머스 Lv. 2 올바른 괄호, 2분

 stack 쓰면 매우 쉽게 풀리는 문제. 사실상 예제문제다. 이런 건 1레벨로 낮춰줬으면.

bool solution(string s)
{
    stack<char> stk;
    for(char c : s){
        if(c == ')'){
            if(stk.empty() || stk.top() != '(') return false;
            stk.pop();
        }
        else if(c == '('){
            stk.push('(');
        }
    }
    
    return stk.empty();
}

 

시간복잡도

 순회에 O(n)

 

 

 

프로그래머스 Lv. 2 이진 변환 반복하기, 6분 40초

 주어진 대로 변환하면 되는 문제. 뭐.. 10진수를 n진수로 변환할 때 % 이후 /를 한다는 것만 기억하면 된다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int num_removed_zeros = 0;
int num_binary_translation = 0;

string removeZero(string x){
    int total = (int) x.length();
    string result = "";
    for(char c : x){
        if(c == '1') result += "1";
    }
    int num_ones = result.length();
    num_removed_zeros += total - num_ones;
    return result;
}

string decimalToBinary(int x){
    num_binary_translation++;
    
    string result = "";
    while(x){
        result += to_string(x % 2);
        x /= 2;
    }
    reverse(result.begin(), result.end());
    return result;
}

vector<int> solution(string s) {
    while(s != "1"){
        int len = (int) removeZero(s).length();
        s = decimalToBinary(len);
    }
    return {num_binary_translation, num_removed_zeros};
}

 

 

 

프로그래머스 Lv. 3 숫자의 표현, 13분

첫 접근

 아래 느낌으로 nested loop로 돌렸다. n이 1만이니.. 그러나 당연히 TLE. 다른 방법이 필요했다.

vector<int> dp(10001, 0); // dp[i] : 연속된 자연수로 i를 표현하는 방법의 개수
int INF = 10001;

int solution(int n) {
    for(int i = 1; i<=n; i++){
        for(int len = 1;)
        for(int j = i; j<=5000; j++){
            int sum = (j - i + 1) * (i + j) / 2;
            if(sum >= INF) continue;
            dp[sum]++;
        }
    }
    
    return dp[n];
}

 

두 번째 접근

 sliding window가 딱 생각이 났다. sum을 계산하고, 작으면 e를 늘이고, 크면 s를 늘이는 방식으로.

int getSum(int s, int e){
    return (e - s + 1) * (s + e) / 2;
}

int solution(int n) {
    // dp 실패했으니 sliding window로 해 볼까? two pointer로.
    int s = 1, e = 1, answer = 0;
    while(s <= n){
        if(s > e){
            e = s;
            continue;
        }
        
        int sum = getSum(s, e);
        if(sum == n){
            answer++;
            s++;
            continue;
        }
        if(sum < n) e++;
        else if(sum > n) s++;
    }
    return answer;
}

 

시간복잡도

 s의 sliding에 O(n)이, e의 sliding에 O(n)이 걸린다.

 

 

 

프로그래머스 Lv. 3 숫자 게임, 17분 40초

 greedy 문제이다. 일단, 기본 전제: 이길 수 있으면 이기되 최대한 작은 수로 이기고, 지는 경우에는 최대한 작은 수로 져야 한다.

 

첫 접근

 최대한 작은 수로 이긴다 -> binary search, 특히 upper bound로 풀었다. 처음에 놓친 점은, multiset을 하지 않은 것.

int solution(vector<int> A, vector<int> B) {
    multiset<int> s(B.begin(), B.end());
    int answer = 0;
    set<int>::iterator iter;
    for(int point : A){
        
        iter = upper_bound(s.begin(), s.end(), point);
        if(iter == s.end()){ // point보다 큰 것이 없는 경우
            s.erase(s.begin());
        }
        else{ // 존재 : point보다 큰 것중 제일 작은 것
            s.erase(iter);
            answer++;
        }
    }
    
    return answer;
}

 

 그러나 TLE가 난다! input size가 10만이고, set의 연산은 O(logn)이므로 O(nlogn)으로 풀릴 줄 알았는데, set 연산이 생각보다 느린갑다.

 

두 번째 접근

 그래서 A는 내림차순으로, B는 오름차순으로 정렬한 후 B가 이기지 못하는 경우라면 B의 제일 작은 점수를 희생시키고, 이길 수 있으면 이기는 방식으로 선택했다.

int solution(vector<int> A, vector<int> B) {
    sort(A.begin(), A.end(), greater<int>());
    sort(B.begin(), B.end(), less<int>()); // 오름차
    int start = 0, end = B.size()-1;
    int answer = 0;
    for(int point : A){
        if(point >= B[end]){ // B가 못이기는 경우
            start++;
        }
        else{
            end--;
            answer++;
        }
    }
    
    return answer;
}

 

시간복잡도

 정렬에 O(nlogg), 순회에 O(n)이므로 O(nlogn)이다.

 

후기

 왜 set으로는 안풀릴까.

 

 

 

프로그래머스 Lv. 3 기지국 설치, 27분

 전파가 닿지 않는 부분을 알면, w의 /와 % 연산을 이용해서 쉽게 답을 낼 수 있다.

 그러면 전파가 닿지 않는 부분을 알아야 하는데, 

• 전파가 닿는 구간을 찾음
• 전체에서 위 구간을 뺌

 위 방식으로 구현했다.

 

 N이 작으면 bitmap 형식으로 풀어도 되는데, 2억이므로 시간 내에 풀 수 없다. 따라서 [시작 좌표, 끝 좌표]로 어떻게든 풀어야 한다.

 

1. 전파가 닿는 구간 찾기
   1. 겹치는 부분만 잘 처리해 주면 된다.
2. 전파가 닿지 않는 구간 찾기
   1. 전체에서 전파가 닿는 구간을 빼면 된다.

typedef pair<int, int> pii; // .first : 시작 지점, .second : 끝 지점. (included)

int solution(int n, vector<int> stations, int w)
{
    int s = stations[0] - w, e = stations[0] + w;
    s = max(s, 1); e = min(e, n);
    pii p = {s, e};
    vector<pii> overlaps(1, p);
    
    // 겹쳐 있는 구간을 찾을 것임.
    for(int station : stations){
        s = station - w, e = station + w;
        s = max(s, 1); e = min(e, n);
        int prev_e = overlaps.back().second;
        
        if(prev_e + 1 < s){ // 아예 새로운 구간이 시작되는 경우
            overlaps.push_back({s, e});
        }
        else{ // 이어지거나, 겹치는 경우
            overlaps.back().second = e;
        }
    }
    overlaps.push_back({n+1, n+1});
    
    
    // overlapping 결과 테스트
    // for(pii p : overlaps){
    //     cout<<p.first<<", "<<p.second<<endl;
    // }
    
    // sum of ceil(겹쳐 있지 않은 구간 / w)가 답.
    int answer = 0;
    s = 1;
    w = 2 * w + 1;
    for(pii overlap : overlaps){
        e = overlap.first - 1;
        
        answer += (e - s + 1) / w;
        answer += ((e - s + 1) % w != 0);
        
        s = overlap.second + 1;
    }
    
    return answer;
}

/*
비어있는 공간만 찾으면 됨. 구현 문제 같음.
stations들이 겹쳐 있는 구간을 찾는 문제로 바꾸면 쉬울 것 같은데?

*/

 

시간복잡도

 overlaps를 만드는 데 O(n), 이후 overlaps를 순회할 때 O(n)이므로 O(n)이다.

 

후기

 이 문제는 구현에서 조금 절었다. 실수한 점은, 첫 값을 넣을 때도 s와 e가 [1, n] 사이에 있게 filtering 했어야 했는데 그러지 않아서 문제가 생겼다.