코딩 초보 삐리리뽀옹이 나가신다

def solution(str1, str2):
    mul_val = 65536
    
    # 소문자 변환
    str1 = str1.lower()
    str2 = str2.lower()
    
    # 두글자씩 떼어서 배열로 변환
    str1_arr = [ str1[i : i + 2] for i in range(len(str1) - 1) if str1[i : i + 2].isalpha() ]
    str2_arr = [ str2[i : i + 2] for i in range(len(str2) - 1) if str2[i : i + 2].isalpha() ]
    
    union_count = len(str1_arr) + len(str2_arr) # (A U B) = (A) + (B) - (A ^ B) 공식 사용 : 교집합 개수 구한 후 빼줘야 함
    # 교집합 개수 구하기
    intersection_count = 0
    for x in str1_arr:
        if x in str2_arr:
            intersection_count += 1
            str2_arr.remove(x)
    
    # 합집합 개수 구하기
    union_count -= intersection_count # 교집합 개수 빼주기
    
    if union_count == 0:
        return mul_val
    else:
        return int(intersection_count / union_count * mul_val)

#include <math.h>

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
using namespace std;

int dfs(int n, int plusCnt){
    if(n < 1 || log(n)/log(3) < (plusCnt + 1)/2){
        // log(n)/log(3)	: 앞으로 나올 수 있는 최대한의 * 횟수(n이 되기 위해 3을 거듭제곱해야 하는 횟수)
        // (plusCnt + 1)/2	: *가 나와야 하는 최소한의 횟수
  		// 앞으로 *가 최대로 나오는 경우(log(n)/log(3)) 가 반드시 나와야 하는 *의 횟수((plusCnt + 1)/2) 보다 작다면 더 재귀를 진행해봤자 무의미함으로 return
        return 0;
    }
    if(n == 3 && plusCnt == 2){
        // * : 하나, + : 둘 이므로 1 return
        return 1;
    }
    
    int ret = 0;
    if(n%3 == 0 && plusCnt >= 2){
    	//3으로 나눠지고 남은 +가 두 개 이상이어야 *가 나올 수 있음
        ret += dfs(n/3, plusCnt - 2);
	}
    ret += dfs(n - 1, plusCnt + 1); //+ 하나를 늘리는 경우
    
    return ret;
}

int solution(int n) {
    return dfs(n - 2, 2); // 시작 시 맨 마지막 두 개는 무조건 ++이어야 하므로 plusCnt를 2로 시작
}

// 풀이

#include <string>
#include <vector>
#include <set>

using namespace std;

vector<string> my_user_id, my_banned_id;
int my_answer = 0;
set<int> id_set;

bool is_matched(string id, string form){
    //불량사용자 form에 id가 맞는지 확인하는 함수
    if(id.length() != form.length())
        return false;
    for(int i=0;i<id.length();i++){
        if(id[i] == '*' || form[i] == '*')
            continue;
        if(id[i] != form[i])
            return false;
    }
    return true;
}

void calculate_comb_num(int banned_id_idx, int id_bit_check){
    /*
        @banned_id_idx        = 다음에 택할 불량사용자 index
        @id_bit_check = bit로 표현한 불량사용자로 선택된 user 집합
    */
    if(banned_id_idx == my_banned_id.size()){ 
        //불량사용자를 다 배정했으면 진입
        if(id_set.find(id_bit_check) != id_set.end()){
            //이미 셌던 집합이면 return
            return;
        } 
        my_answer++; //조합 개수 증가
        id_set.insert(id_bit_check); //id_set에 추가
        return;
    }
    for(int i=0;i<my_user_id.size();i++){
        if(!(id_bit_check & (1 << i)) && is_matched(my_user_id[i], my_banned_id[banned_id_idx])){
            //불량 사용자로 선택했던 user가 아니면 + 불량사용자 조건에 해당하면...
            calculate_comb_num(banned_id_idx + 1, id_bit_check | (1 << i));
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    my_user_id = user_id;
    my_banned_id = banned_id;
    
    calculate_comb_num(0, 0);
    
    return my_answer;
}

//SOLUTION 1 : SET 사용
#include <vector>
#include <set>

using namespace std;

set<int> room_set;

long long get_allocated_room(long long target_room){
    if(room_set.find(target_room) == room_set.end()){
        return target_room;
    } else {
        return get_allocated_room(target_room + 1);
    }
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    for(int i=0;i<room_number.size();i++){
        long long allocated_room = get_allocated_room(room_number[i]);
        answer.push_back(allocated_room);
        room_set.insert(allocated_room);
    }
    return answer;
}

//SOLUTION 2 : MAP, FIND 사용

#include <vector>
#include <map>

using namespace std;

map<long long, long long> room_map;

long long get_allocated_room(long long target_room){
    if(room_map[target_room] == 0) {
        return target_room;
    } else {
        room_map[target_room] = get_allocated_room(room_map[target_room]);
        return room_map[target_room];
    }
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    for(int i=0;i<room_number.size();i++){
		long long allocated_room = get_allocated_room(room_number[i]);
 		answer.push_back(allocated_room);
		room_map[allocated_room] = allocated_room + 1;
    }
    return answer;
}

첫 번째 방법

//BFS 탐색을 2 depth까지 하는 비효율적인 방식의 첫 시도
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

bool isFar(const int boardSize, vector<string> place, vector<vector<int>> &visited){
    const vector<int> dx = {-1, 1, 0, 0};
    const vector<int> dy = {0, 0, -1, 1};
    
    queue<tuple<int, int, int, int>> q;
        
    for(int i=0;i<boardSize;i++){
        for(int j=0;j<boardSize;j++){
            if(place[i][j] == 'P')
				q.push({i, j, 0, q.size()});
        }
    }
	while(!q.empty()){
      	int x = get<0>(q.front());
        int y = get<1>(q.front());
        int c = get<2>(q.front()); // 거리
        int v = get<3>(q.front()); // 탐색 중인 면접자의 index
        q.pop();
        
        visited[x][y] = v;
        
        for(int d=0;d<4;d++){
            int nx = x + dx[d];
            int ny = y + dy[d];
            int nc = c + 1;
                
            if(nx<0 || nx>=boardSize || ny<0 || ny>=boardSize
            	|| visited[nx][ny]==visited[x][y] // 탐색 중인 면접자가 방문한 적이 있다면 continue
               	|| place[nx][ny]=='X' // 파티션이면 continue
              	|| nc>2) // 다음에 갈 자리가 맨해튼 거리 2 초과면 continue
            	continue;
            
            if(place[nx][ny] == 'P')
                return false;
            q.push({nx, ny, nc, v});
        }
    }
    
    return true;
}

vector<int> solution(vector<vector<string>> places) {
	vector<int> answer;
    const int boardSize = 5;
	vector<vector<int>> visited(boardSize, vector<int>(boardSize, -1));
	
    for(auto place : places)
		answer.push_back(isFar(boardSize, place, visited));
    
	return answer;
}

두 번째 방법

//1 depth BFS 탐색을 통한 효율적인 방법
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

bool isFar(const int boardSize, vector<string> place){
    const vector<int> di = {-1, 1, 0, 0};
    const vector<int> dj = {0, 0, -1, 1};
    
    vector<vector<bool>> visited(boardSize, vector<bool>(boardSize, false));
        
    for(int i=0;i<boardSize;i++){
        for(int j=0;j<boardSize;j++){
            if(place[i][j] == 'P'){
                visited[i][j] = true;
            	for(int d=0;d<4;d++){
                    int ni = i + di[d];
            		int nj = j + dj[d];
                    if(ni<0 || ni>=boardSize || nj<0 || nj>=boardSize || place[ni][nj]=='X')
                        continue;
                    if(visited[ni][nj])
                        return false;
                    visited[ni][nj] = true;
                }    
            }
        }
    }
    
    return true;
}

vector<int> solution(vector<vector<string>> places) {
	vector<int> answer;
    const int boardSize = 5;
	
    for(auto place : places)
		answer.push_back(isFar(boardSize, place));
    
	return answer;
}