23.03.03. 풀었던 문제들

프로그래머스 덧칠하기

 많이 본 greedy / simulation 문제. 앞 또는 뒤에서부터 채워가는 게 optimal이다.

// n : 구역, m : 롤러 길이
int solution(int n, int m, vector<int> section) {
    int answer = 0;
    
    int size = section.size();
    for(int i = 0; i<size; i++){
        int cur = i;
        // 더 이상 칠하지 못할 때까지 section index 증가
        while(cur + 1 < size && section[cur + 1] <= section[i] + m - 1){
            cur++;
        }
        i = cur;
        answer++;
    }
    
    return answer;
}

 

 

프로그래머스 바탕화면 정리

 좌표계에서 직사각형을 뽑으면 되는 쉬운 문제.

vector<int> solution(vector<string> wallpaper) {
    vector<int> answer = {INT_MAX, INT_MAX, INT_MIN, INT_MIN};
    // 시작x, 시작y, 도착x, 도착y
    
    for(int r = 0; r<wallpaper.size(); r++){
        for(int c = 0; c<wallpaper[r].size(); c++){
            if(wallpaper[r][c] == '#'){
                answer[0] = min(answer[0], r);
                answer[1] = min(answer[1], c);
                answer[2] = max(answer[2], r+1);
                answer[3] = max(answer[3], c+1);    
            }
            
        }
    }
    return answer;
}

// 직사각형 위치 찾으면 됨

 

 

프로그래머스 연속 펄스 부분 수열의 합

 연속 부분 수열의 합의 변형 문제이다. 펄스가 딱 2가지 종류만 주어진다는 것을 인지하면 된다. (1부터 시작하는 펄스와 -1부터 시작하는 펄스) 이 2종류에 대해 연속 부분 수열의 합이 최대가 되는 값을 찾아주면 되며, 이는 dp로 쉽게 해결할 수 있다.

• dp[i] = max(dp[i-1] + s[i], s[i])
  • dp[i] : index i까지 연속 부분 수열 합의 최댓값

typedef long long ll;

long long solution(vector<int> sequence) {
    int n = sequence.size();
    ll answer = INT_MIN;
    vector<ll> s1(sequence.begin(), sequence.end()), s2(sequence.begin(), sequence.end());
    for(int i = 0; i<n; i+= 2){
        s1[i] *= -1;
    }
    vector<ll> dp1(n, INT_MIN);
    dp1[0] = s1[0];
    answer = max(dp1[0], answer);
    for(int i = 1; i<n; i++){
        dp1[i] = max(dp1[i-1] + s1[i], s1[i]);
        answer = max(dp1[i], answer);
    }
    
    
    for(int i = 1; i<n; i+= 2){
        s2[i] *= -1;
    }
    vector<ll> dp2(n, INT_MIN);
    dp2[0] = s2[0];
    answer = max(dp2[0], answer);
    for(int i = 1; i<n; i++){
        dp2[i] = max(dp2[i-1] + s2[i], s2[i]);
        answer = max(dp2[i], answer);
    }
    
    return answer;
}

 

시간복잡도

  앞에서부터 순회하는 것 O(n)의 연산을 2번 하므로 O(n)이다.

 

 

프로그래머스 우박수열 정적분

 주어진 문장을 구현하면 되는 문제. 다만 indexing에 유의해야 한다.

 double로 구현할 시 floating point에 의해 수치가 잘못될 수 있기 때문에 int로 계산해둔 후 마지막에 double 계산을 해 주었다.

 또, areas[i]를 처음에는 i부터 i+1까지 정적분 결과로 두었으나 이렇게 두면 indexing이 애매해져서 처음에 0 값을 넣고 나서 계산해, i-1부터 i까지 정적분 결과로 두었다. 이렇게 하면 areas[end] - areas[start]가 start부터 end까지 정적분 결과가 되기 때문에 계산에 편하다.

typedef long long ll;

vector<double> solution(int k, vector<vector<int>> ranges) {
    // areas[i] : i-1부터 i까지 정적분 결과 * 2
    vector<ll> areas;
    areas.push_back(0);
    while(k != 1){
        int prevk = k;
        k = k & 1 ? 3*k + 1 : k/2;
        
        int sum = prevk + k;
        areas.push_back(sum);
    }
    
    // areas[i] : 0부터 i까지 정적분 결과 (prefix sum)
    for(int i = 1; i<areas.size(); i++){
        areas[i] += areas[i-1];
    }
    
    vector<double> answer;
    for(vector<int> range : ranges){
        int start = range[0], end = areas.size() - 1 + range[1];
        if(start > end) answer.push_back(-1);
        else answer.push_back((double)(areas[end] - areas[start]) / 2);
    }
    return answer;
}

 

시간복잡도

 앞에서부터 훑기 때문에 O(n). prefix sum을 사용하지 않을 경우 $O(n^{2})$일 것이다.

 

 

Leetcode 28. Find the Index of the First Occurrence in a String

 문제만 보면 KMP 알고리즘이다. 그러나 문제 제한이 10^4로 아주 작기 때문에 그냥 풀면 된다.

class Solution {
public:
    int strStr(string p, string c) {
        if(p.length() < c.length()) return -1;
        for(int i = 0; i<p.length() - c.length() + 1; i++){
            if(p.substr(i, c.length()) == c) return i;
        }
        return -1;
    }
};

 

시간복잡도

 string의 비교에 c.length()만큼, 전체 loop를 p.length() - c.length()만큼 돈다. 따라서 O(|p||c|)

 

공간복잡도

 c.length()만큼을 p.length()만큼 쓴다. 시간복잡도와 동일하게 O(|p||c|)