코딩 테스트 일기 - 1일 차

소수 찾기

문제 링크 : 소수 찾기

문제 설명

• 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
• 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한 사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
"17"	3
"011"	2

• "17" -> (7, 17, 71) => 3
• "011" -> (11, 101) => 2

풀이 방법

• 각 종이 조각을 붙여서 소수를 만들어야 하는데, 종이를 모두 필수로 붙여야 되는 것이 아니고 하나씩도 검사를 해봐야되기 때문에 완전탐색을 통해 진행할 것이다.
  -> dfs를 통해서 구현한다고 하면 O(N!)만큼의 시간복잡도가 발생하는데, numbers의 길이가 최대 7이기 때문에 적당할 것으로 보인다.

• 11과 011은 같은 숫자로 취급되고, 같은 수가 여러번 나올 경우가 많으니, unordered_set<int>에 dfs를 통한 숫자를 저장하고 이를 소수 검사를 진행하면 될 것으로 보인다.

• 소수 찾는 함수의 구현은 배열로 저장(에라토스테네스의 체)보다는 값을 지속적으로 소수 검사하는 것이 나을 것으로 보인다.
  -> 소수 검사 시에 O(logN)의 시간복잡도가 발생하는데, dfs랑 같이 사용하니 최종적으로 O(N!)만큼의 시간복잡도가 발생할 것으로 유추할 수 있다.

구현

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

// 소수 검사 함수
bool isPrime(int n){
    if(n == 0 || n == 1) return false;
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

unordered_set<int> numberSet;	// dfs한 값들 저장
vector<bool> visited;			// dfs 방문 여부

void dfs(int idx, int n, string& numbers, string& str){
    if(idx > n){
        return;
    }
    
    for(int i = 0; i < n; i++){
        if(visited[i]) continue;
        
        visited[i] = true;
        str += numbers[i];
        numberSet.insert(stoi(str));
        dfs(idx + 1, n, numbers, str);
        visited[i] = false;
        str.pop_back();
    }
}

int solution(string numbers) {
    int answer = 0;
    
    // 만들 수 있는 모든 숫자 unordered_set에 저장
    string str = "";
    visited = vector<bool>(numbers.size(), false);
    dfs(0, numbers.size(), numbers, str);
    
    // 소수인지 확인
    for(auto it = numberSet.begin(); it != numberSet.end(); ++it){
        if(isPrime(*it)){
            answer++;
        }
    }
    
    return answer;
}

---

쿼드 압축 후 개수 세기

문제 링크 : 쿼드압축 후 개수 세기

문제 설명

• 0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

• arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

제한 사항

• arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
  -> arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
  -> arr의 각 행에 있는 모든 값은 0 또는 1 입니다.

입출력 예

arr	result
[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]	[4,9]

풀이 방법

• arr의 행의 개수가 2의 거듭 제곱수 형태를 하고 있기 때문에, Divide&Conquer 방법을 통해서 구현하면 좋을 것으로 보인다.
  -> arr의 행의 개수가 2^n이기 때문에 절반인 2^(n-1)을 기준으로 분리된 부분을 전부 확인한 후에 같은 값이라면 즉시 0 또는 1의 값을 넣으면 될 것 같다.
  -> 칸이 1x1까지 분리가 되면 위의 풀이법을 통해서 0 또는 1의 값이 들어갈 것으로 생각된다.
• 최악의 경우, 정확하게 이렇게는 될 수가 없지만 배열의 모든 값을 10번 볼 수 있기 때문에 시간복잡도는 O(N^2) 만큼 발생할 것으로 유추된다. (N = 1024)

구현

#include <string>
#include <vector>

using namespace std;

vector<int> answer{0,0};

void divide(int start_x, int end_x, int start_y, int end_y, vector<vector<int>>& arr){
    // (start_x ~ end_x)(start_y ~ end_y) 전부 같은 값인지 검사
    bool isFlag = true;
    int k = arr[start_y][start_x];
    for(int i = start_y; i < end_y; i++){
        for(int j = start_x; j < end_x; j++){
            if(k != arr[i][j]){
                isFlag = false;
                break;
            }
        }
        if(!isFlag) break;
    }
    
    // 같은 값이라면 
    if(isFlag){
        if(k == 0)
            answer[0]++;
        else
            answer[1]++;      
        return;
    }
    
    // 아니라면 분할
    int n = (end_x - start_x) / 2;
    divide(start_x, end_x - n, start_y, end_y - n, arr);
    divide(start_x + n, end_x, start_y, end_y - n, arr);
    divide(start_x, end_x - n, start_y + n, end_y, arr);
    divide(start_x + n, end_x, start_y + n, end_y, arr);
}

vector<int> solution(vector<vector<int>> arr) {
    divide(0, arr.size(), 0, arr.size(), arr);
    
    return answer;
}