23.02.26. 풀었던 문제들

리트코드 daily challenge - 72. Edit Distance

 LCS 비스무리한 DP 문제. LCS로 접근했는데, 안 풀려서 solution을 봤다. (문제 본 지 30분 경과..) 

 dp[i][j]를 word1[0..i-1]을 word2[0...j-1]로 바꾸는 데 필요한 연산 횟수라고 하자. 그러면

• word1[i] == word2[j]인 경우에는 dp[i][j] = dp[i-1][j-1]이다. 연산을 할 필요가 없기 때문
• else, dp[i][j] = 
  • dp[i-1][j] + 1 : insert하는 경우
  • dp[i][j-1] + 1 : delete하는 경우
  • dp[i-1][j-1] + 1 : replace하는 경우
• 와 같은 경우의 수가 나온다. 사실상 dp 식만 세우면 바로 풀리는 문제.

// Runtime 7ms Beats 92.32%
// Memory 8.9MB Beats 63.20%

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.size(), len2 = word2.size();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1));

        // init
        for(int i = 0; i<=len1; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= len2; j++){
            dp[0][j] = j;
        }

        for(int i = 1; i<=len1; i++){
            for(int j = 1; j<=len2; j++){
                if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = min(min(dp[i-1][j] + 1, dp[i][j-1] + 1), dp[i-1][j-1] + 1);
            }
        }

        return dp[len1][len2];
    }
};

 

시간복잡도 & 공간복잡도

 O(len1 * len2)이다. 

 

 

프로그래머스 햄버거 만들기

 주어진 대로 구현하면 되는 문제인데, 한 번 없애고 전체 검사하고 ... 이러면 당연히 끝이 안난다. 한 번의 순회로 답을 도출해야 할 것.

int solution(vector<int> ingredient) {
    int answer = 0;
    for(int i = 0; i<ingredient.size(); i++){
        if(i >= 3 && ingredient[i] == 1 && ingredient[i-1] == 3 && ingredient[i-2] == 2 && ingredient[i-3] == 1){
            ingredient.erase(ingredient.begin() + i); i--;
            ingredient.erase(ingredient.begin() + i); i--;
            ingredient.erase(ingredient.begin() + i); i--;
            ingredient.erase(ingredient.begin() + i); i--;
            answer++;
        }
    }
    
    return answer;
}

 

시간복잡도

 O(n)이다. 처음부터 끝까지 순회하기 때문. vector의 erase 연산은 지워진 원소 뒤에 있는 원소의 개수인데, 여기서는 4를 지운다는 것이 고정이기 때문

 

공간복잡도

 O(1)이다. 추가적인 공간을 사용하지 않음.

 

 

프로그래머스 점 찍기

 단순히 for문으로 풀면 범위가 너무 커져서 TLE가 난다. 따라서 O(n)으로 풀 수 있는 방법을 찾아야 하는데, 우리는 원의 방정식을 알고 있다.

 $x^2a^2 + y^2b^2 = d^2$이라는 이 식에서, y = 0, k, 2k, ... d와 원의 접점을 알 수 있다. $sqrt(d^2 - b^2k^2) / k$이 그것이며, 계산식에서 long long으로 형변환만 잘 해준다면 문제없이 풀린다.

typedef long long ll;

long long solution(int k, int d) {
    long long answer = 0;
    ll dsquare = (ll) d * (ll)d;
    for(ll i = 0; i<=d; i += k){
        answer += ((ll)sqrt(dsquare - i * i) / k) + 1;
    }
    return answer;
}
/*
(a^2 + b^2) * k^2 <= d^2인 a, b의 개수

y가 0, k, 2k, 3k, ... d/k 일 때 x좌표
d/k, sqrt(d*d-k*k) / k, sqrt(d*d - 2k*2k) / k

sqrt(d*d/k*k - n*n)
*/

// 또는, 같은 풀이로 이렇게도 접근 가능.
long long solution(int k, int d) {
    long long answer = 0;
    ll dsquare = (ll) d * (ll)d;
    ll ksquare = (ll) k * (ll)k;
    ll dmk = dsquare / ksquare;
    for(ll i = 0; i<=d/k; i++){
        answer += ((ll)sqrt(dmk - i * i)) + 1;
    }
    return answer;
}

 

시간복잡도

 O(d/k)이다. 반복문을 그만큼 접근하기 때문.

 

 

프로그래머스 둘만의 암호

 string의 erase/find 함수와 string을 풀고 index로 접근하는 법을 안다면 쉽게 풀리는 문제

string solution(string s, string skip, int index) {
    string alphabet = "abcdefghijklmnopqrstuvwxyz";
    for(char c : skip){
        alphabet.erase(alphabet.find(c), 1);
    }
    for(char& c : s){
        c = alphabet[(alphabet.find(c) + index) % alphabet.length()];
    }
    return s;
}

 

 

프로그래머스 무인도 여행

 정석 BFS 문제. 항상 그렇듯 좌표가 있는 bfs 문제는 dr, dc array를 두고 for문으로 다음 탐색을 검사하자.

typedef pair<int, int> pii; // .first : r, .second : c

vector<int> answer;

int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};

void BFS(pii cur, vector<vector<bool>> &visited, vector<string> maps, int maxr, int maxc){
    queue<pii> q;
    q.push(cur);
    int food = 0;
    
    while(!q.empty()){
        pii top = q.front(); q.pop();
        visited[top.first][top.second] = true;
        food += maps[top.first][top.second] - '0';
        
        for(int i = 0; i<4; i++){
            int nr = dr[i] + top.first;
            int nc = dc[i] + top.second;
            if(0 <= nr && nr < maxr && 0 <= nc && nc < maxc && !visited[nr][nc] && '0' <= maps[nr][nc] && maps[nr][nc] <= '9'){
                visited[nr][nc] = true;
                q.push({nr, nc});
            }
        }
    }
    
    answer.push_back(food);
}

vector<int> solution(vector<string> maps) {
    int maxr = maps.size(), maxc = maps[0].length();
    vector<vector<bool>> visited(maxr, vector<bool>(maxc, false));
    
    
    for(int i = 0; i<maxr; i++){
        for(int j = 0; j<maxc; j++){
            if(!visited[i][j] && '0' <= maps[i][j] && maps[i][j] <= '9'){
                BFS({i, j}, visited, maps, maxr, maxc);
            }
        }
    }
    
    sort(answer.begin(), answer.end());
    if(answer.size() == 0) answer = {-1};
    return answer;
}