22.04.04 풀었던 문제들

1. 쿼드 압축 후 개수 세기

backtrack을 이용해, 압축 가능하다면 탐색하지 않고, 압축 불가능하면 탐색하는 방식으로 진행하면 된다. 2중포문 안쓸려다가 시간 엄청나게 잡아먹은 문제. 생각해 보면, 모든 arr을 log(input size)만큼 탐색하는 것이므로 시간복잡도는 n^2logn이다. 입력이 1024까지니 이런 풀이가 가능함.

// 쿼드압축 후 개수 세기
 
#include <string>
#include <vector>
 
using namespace std;
 
void div(vector<vector<int>>& arr, vector<int>& answer, int r, int c, int size){
    if(size == 1){
        answer[arr[r][c]]++;
        return;
    }
    
    int base = arr[r][c];
    bool compressable = true;
    for(int i = r; i<r + size; i++){
        for(int j = c; j < c + size; j++){
            if(base != arr[i][j]){
                compressable = false;
            }
        }
    }
    
    if(compressable){
        answer[base]++;
    } else{
        int halfsize = size/2;
        div(arr, answer, r, c, halfsize);
        div(arr, answer, r + halfsize, c, halfsize);
        div(arr, answer, r, c + halfsize, halfsize);
        div(arr, answer, r + halfsize, c + halfsize, halfsize);
    }
    return;
}
 
vector<int> solution(vector<vector<int>> arr) {    
    vector<int> answer(2, 0);
    div(arr, answer, 0, 0, arr.size());
    return answer;
}

 

​

2. 교점에 별 만들기

구현이 귀찮았다.

​

​

3. 124 나라의 숫자

1 : 3 * 0 + 1 : 1 2 : 3 * 0 + 2 : 2 3 : 3 * 0 + 3 : 4	4 : 3 * 1 + 1 : 11 5 : 3 * 1 + 2 : 12 6 : 3 * 1 + 3 : 14
7 : 3 * 2 + 1 : 21 8 : 3 * 2 + 2 : 22 9 : 3 * 2 + 3 : 24	10 : 3 * 3 + 1 : 41 11 : 3 * 3 + 2 : 42 12 : 3 * 3 + 3 : 44
13 : 3*3*1 + 3*1 + 1 : 111

조금 복잡하다. 그러나, 결국 진법변환 tool은 아래와 같이 동일하다.

while(n){
    n%3; // 해당 자리수
    n/=3; // 나눠줌
}

이게 기본이로 두고 생각해 보자. 124 나라의 진법의 경우에는 1의 자리수에 1, 2, 4가 온다. 그러나 사실 4를 3으로 바꿔 생각하면 좀 쉬워진다.

0, 1, 2 대신 1, 2, 3이 오는 것이다. 따라서 n%3 대신 (n-1)%3 + 1을 해 준다. 그러면 나머지 부분은 해결이다. 몫 쪽을 보자. 만약 r(나머지)이 3이 되는 경우에는 3진법인데 +3이 되는 것이므로, 몫이 하나 작아져야 한다. 따라서 n/=3 이후 n--를 해 주는 것이다. 그리고 r이 3인 경우에는 4로 바꿔준다.

// 124 나라의 숫자
 
#include <string>
#include <vector>
 
using namespace std;
 
string solution(int n) {
    string answer = "";
    int r;
    while(n){
        r = ((n-1) % 3) + 1;
        n /= 3;
        if(r==3){
            r = 4;
            n--;
        }
        answer = to_string(r) + answer;
    }
    return answer;
}

 

4. 짝지어 제거하기

기본적인 stack 문제다.