굳건하게

문제 : programmers.co.kr/learn/courses/30/lessons/17677

2018 KAKAO BLINE RECRUITMENT

구현 Simulation

[ 알고리즘풀이 ]

 1) 2글자씩 끊어서 둘다 알파벳인지 체크한다.

 2) 두 글자 다 알파벳이라면 소문자로 바꿔준 후, count 배열에 해당 케이스를 저장한다.

     count 배열은 [26][26] 으로 선언해 ['a' ~ 'z']['a' ~ 'z'] 모든 경우를 count 한다.

 3) count 배열을 순회하며 교집합은 count1, count2 배열의 min 값이 되고 합집합은 count1, count2 배열의 max 값이 된다.

[ 코드구현 C++ ]

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/Programmers/%5B1%EC%B0%A8%5D_%EB%89%B4%EC%8A%A4_%ED%81%B4%EB%9F%AC%EC%8A%A4%ED%84%B0%EB%A7%81.cpp

문제 : programmers.co.kr/learn/courses/30/lessons/4289

2019 KAKAO BLIND RECRUITMENT

bitmask bitmasking

[ 문제해석 ]

 속성의 모든 부분 집합 중, 유일성과 최소성을 만족하는 집합을 찾아야한다.

 이때, 유일성은 해당 집합의 속성 값들로 튜플을 구분할 수 있으면 되고, 최소성은 유일성을 만족하는 속성 집합 중에서 하나라도 속성이 빠지면 유일성이 깨지는 경우를 말한다.

[ 알고리즘풀이 ]

 우리가 다뤄야 될 속성은 최대 8개이므로 bitMask를 이용해서 가능한 모든 속성 조합을 다룰 수 있다.

 예를 들어, 1011(2) = 13 이라는 값은 0번, 1번, 3번 속성을 선택한 경우라고 생각하자.

 그러면, M개의 속성이 있다고 가정하면 (1 ~ 2^M - 1) 값들이 공집합을 제외한 모든 부분 집합을 의미한다.

 1) 가능한 모든 속성 집합을 순회하며 유일성을 체크하자.

 유일성을 만족한다는 것은 결국 모든 튜플 쌍들에 대해서 현재 속성으로 구분이 가능하다는 뜻이다. 따라서, getBit 함수를 통해 속성들의 index를 얻어내고, 모든 튜플 쌍들에 대해 현재 속성들로 값이 구분되는지 ( 다른 값이 있는지 ) 체크한다.

 2) 유일성이 검증된 애들 중 최소성을 체크하자.

 최소성은 결국 1번, 2번, 5번 속성으로 유일성을 만족했다면 1번 / 2번 / 5번 / 1번, 2번 / 1번, 5번 / 2번, 5번 으로는 유일성을 만족하지 못해야된다.

 따라서, 유일성을 만족한 애들 중 속성의 갯수를 기준으로 sorting을 한 다음 현재 내가 선택한 속성보다 속성의 갯수가 작은 경우 중 나의 부분 집합이 있는지 체크하면 된다.

 부분집합은 & 연산을 통해서 간단하게 체크가 가능하다.

 예를 들어, 1011과 0011 은 부분집합 관계이므로 1011 & 0011 = 0011 이 성립한다.

[ C++ 코드구현 ]

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/Programmers/%ED%9B%84%EB%B3%B4%ED%82%A4.cpp

문제 : https://programmers.co.kr/learn/courses/30/lessons/42888

카카오 2019 BLINE RECRUITMENT '오픈 채팅방'

맵 Map

 자료구조 Map을 이용해서 문제를 해결할 수 있습니다. 실제 UserID 와 NickName을 자료구조 Map에 담아두고, NickName이 바뀌면 Map을 갱신하고, Enter 혹은 Leave 명령어가 들어오면 NickName을 신경쓰지말고, UserID를 기준으로 Enter / Leave 명령 상태를 차례대로 저장해줍니다. 그 후, 저장해놓은 명령 상태를 Map에서 UserID에 해당하는 NickName을 이용해 제대로 원하는 답을 출력해주면 됩니다.

#include <string>
#include <vector>
#include<map>
using namespace std;

vector<string> solution(vector<string> record) {
	int index = 0;
	map<string, string> id;
	vector<pair<string, bool>> tempAns;

	for (int i = 0; i < record.size(); i++) {
		int j;
		string tempID = "", tempNick = "";
		if (record[i][0] == 'E') { // Enter
			j = 6;
			while (record[i][j] != ' ')
				tempID += record[i][j++];
			j++;
			while (record[i][j] != '\0')
				tempNick += record[i][j++];
			if (id.count(tempID) == 0)
				id.insert({ tempID, tempNick });
			else
				id[tempID] = tempNick;

			tempAns.push_back({ tempID, 0 });
		}
		else if (record[i][0] == 'L') { // Leave
			j = 6;
			while (record[i][j] != '\0')
				tempID += record[i][j++];
			tempAns.push_back({ tempID, 1 });
		}
		else { // Change
			j = 7;
			while (record[i][j] != ' ')
				tempID += record[i][j++];
			j++;
			while (record[i][j] != '\0')
				tempNick += record[i][j++];
			id[tempID] = tempNick;
		}
	}
	vector<string> answer;
	for (int i = 0; i < tempAns.size(); i++) {
		string temp;
		if (tempAns[i].second == 0) 
			temp = id[tempAns[i].first] + "님이 들어왔습니다.";
		else
			temp = id[tempAns[i].first] + "님이 나갔습니다.";
		answer.push_back(temp);
	}
	return answer;
}

문제 : https://programmers.co.kr/learn/courses/30/lessons/60062

2020 카카오 BLINE RECRUITMENT

백트레킹 backtracking 완전탐색 complete search

● Input 크기가 크지 않으므로, 모든 경우에 대해서 완전탐색을 진행하면 됩니다.

● 우리는 어떤 친구를 어떤 지점에 배치할지, 그 후 시계 방향 혹은 반 시계 방향 중 어떤 방향으로 보내지를 고려해야 된다. 이때, 외벽이 원형 상태인 점을 이용하여 Weak 배열( 배치해야 되는 지점 ) 을 다음과 같이 하나씩 뒤로 보내본다면 ( 어떤 지점에 배치 + 어떤 방향 ) 이 한 번에 해결된다.

예를 들어, [ 6 ] 지점에서 10 방향으로 보내는 경우와 5 방향으로 보내는 경우는 [ 5 ] 지점에서 6으로 보내는 경우와 [ 6 ] 지점에서 10 방향으로 보내는 경우와 동일하므로 아래 그림과 같은 방법으로 모든 경우에 대해서 Weak 배열을 만들어 볼 수 있다.

● 그 후, 백트레킹을 이용해서 어떤 친구부터 배치할지 가능한 모든 경우에 대해서 현재 Weak 배열에서 탐색을 진행해보면 된다.

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int ans = 9999;

void playGame(deque<int> dq, vector<int> weak, vector<int> dist) {
	int p = 0, c = 0;
	bool check[15] = {};
	for (int j = 0; j < dist.size(); j++) {
		int l = p;
		while (l < weak.size() && dq[l] - dq[p] <= dist[j])
			check[l++] = 1;
		c++; // 친구 추가!
		p = l;
		if (p >= weak.size())
			break;
	}

	for (int j = 0; j < weak.size(); j++)
		if (check[j] == false) return;
	ans = min(ans, c);
	return;
}

void bt(deque<int> dq, vector<int> weak, vector<int> dist, vector<int> temp, bool visited[8], int size) {
	if (temp.size() == size) {
		playGame(dq, weak, temp);
		return;
	}
	for(int i = 0; i < size; i++)
		if (visited[i] == false) {
			visited[i] = true;
			temp.push_back(dist[i]);
			bt(dq, weak, dist, temp, visited, size);
			temp.pop_back();
			visited[i] = false;
		}
	return;
}

int solution(int n, vector<int> weak, vector<int> dist) {
	ans = 9999;
	deque<int> dq;
	for (int i = 0; i < weak.size();  i++)
		dq.push_back(weak[i]);

	for (int i = 0; i < weak.size(); i++) {
		// 백트레킹으로 가능한 모든 dist 순서마다 진행을 해보자.
		bool visit[8] = {};
		vector<int> temp;
		bt(dq, weak, dist, temp, visit, dist.size());

		// dq 배열 하나씩 shift
		dq.push_back(dq.front() + n);
		dq.pop_front();
	}
    
	if (ans == 9999) return -1;
	return ans;
}