알고리즘 카카오 - 비밀지도, 캐시, 프렌즈4블록

비밀지도 

#include <string>
#include <vector>
#include<iostream>

using namespace std;

vector<string> solution(int n, vector<int> arr1, vector<int> arr2) {
	vector<string> answer;
	for (int i = 0; i < n; i++) {
		int num = (arr1[i] | arr2[i]);
		string a;
		int cnt = 0;
		while (cnt!=n) {
			cnt++;
			if (num % 2 == 0)a.push_back(' ');
			else a.push_back('#');
			num /= 2;
	}
		string b;
		for (int i = a.size()-1; i >=0; i--) {
			b.push_back(a[i]);
		}
		answer.push_back(b);
	}
	return answer;
}
int main(void) {

	vector<string> b = solution(6, { 46, 33, 33 ,22, 31, 50 }, { 27 ,56, 19, 14, 14, 10 });
	for (int i = 0; i < 6; i++) {
		cout << b[i] << endl;
	}
	return 0;
}

비밀지도의 핵심은 or 연산자를 아는지 그리고 이진법으로 바꿔서 ' '와 '#'로 나눌 수 있는지

인것 같습니다. 정말 쉬운 문제니 한번 풀어보세요.

 

프렌즈4블록

#include <string>
#include <vector>
#include <queue>
#include<iostream>
#include<string.h>
using namespace std;
#define NS 31
#define MS 31
int chk[MS][NS];
int cnt = 0;
void search(int i, int j, vector<string> board,int m,int n){// 찾기
	char chkBlock = board[i][j];
	if (chkBlock ==' ')return ;
	for (int y = 0; y < 2; y++) {
		for (int x = 0; x < 2; x++) {
			int ny = i + y; int nx = j + x;
			if (ny < 0 || ny >= m || nx < 0 || nx >= n)return ;
			if (chkBlock!= board[ny][nx]) {
				return ;
			}
		}
	}
	for (int y = 0; y < 2; y++) {
		for (int x = 0; x < 2; x++) {
			chk[y + i][x + j] = 1;
		}
	}
}
vector<string> downBlock(int m,int n,vector<string>board) {//블록 내리기
	for (int x = 0; x < n; x++) {
		queue<char>q;
		for (int y = m - 1; y >= 0; y--) {
			if (board[y][x] != ' ') {
				q.push(board[y][x]);
				board[y][x] = ' ';
			}
		}
		int y = m-1;
		while (!q.empty()) {
			board[y--][x] = q.front(); q.pop();
		}

	}
	return board;
}
vector<string> delBlock(int m,int n,vector<string> board) {//블록 지우기
	cnt = 0;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (chk[i][j] == 1) {
				cnt++;
				chk[i][j] = 0;
				board[i][j] = ' ';
			}
		}
	}

	return board = downBlock(m, n, board);//블록 내리기 시작
}
int solution(int m, int n, vector<string> board) {// 문제 솔루션
	int answer = 0;
	while (1) {
		memset(chk, 0, sizeof(chk));
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				search(i, j, board,m,n);
			}
		}
		board=delBlock(m, n, board);//블록 지우기 시작
		if (cnt!=0) {
			answer += cnt;
		}
		else {
			break;
		}
	}
	return answer;
}
int main(void) {
	int a = solution(4, 5, { "CCBDE", "AAADE", "AAABF", "CCBBF" });
		cout << a<<endl;
		
	//int	a = solution(6, 6, { "TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ" });
	//	cout << a<<endl;
}

이문제는 뭔가 시뮬같은 구현문제인데 결국은 4개가 같은게 있는지 확인을 잘해야하고

그걸 잘지워야하고 잘 내려야하는 문제입니다. 엄청 쉬운 문제라고 할 수 없지만 그이유는

구현 할게 많으니 그렇고 사실 문제를 이해하는데는 어려움이 없다 단지 구현을 잘하나

못하나 판별하는 수준은 되는 문제인것 같습니다.

 

캐시

#include <vector>
#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
using namespace std;
// (!stricmp(cache[i].c_str(), data.c_str())) { // 대소문자를 구분하지 않고 문자열 비교
struct Data {
	string C; int cnt;
};

int solution(int cacheSize, vector<string> cities) {
	int answer = 0;
	vector<Data>LRU;
	for (int i = 0; i < cities.size(); i++) {// 대문자로 전부 변환
		string a;
		for (int j = 0; j < cities[i].size(); j++) {
			a += toupper(cities[i][j]);
		}
		cities[i] = a;
	}

	for (int i = 0; i < cities.size(); i++) {
		if (cacheSize == 0) {
			return cities.size() * 5;
		}
		if (LRU.size() < cacheSize) {
			int flag = 0;
			for (int j = 0; j < LRU.size(); j++) {// 있는지 확인 
				if (!(strcmp(cities[i].c_str(), LRU[j].C.c_str()))) {//있으면 hit
					flag = 1;
					answer += 1;
					break;
				}
			}
			if (flag == 0) {
				LRU.push_back({ cities[i],0 });
				answer += 5;
			}
		}

		else {
			int maxCnt = 0x80000000;
			int idx = 0;
			for (int k = 0; k < cacheSize; k++) {
				int cnt = 0;
				for (int j = i; j >= 0; j--) {
					if (!strcmp(cities[j].c_str(), LRU[k].C.c_str())) {
						if (maxCnt < cnt) {
							maxCnt = cnt;
							idx = k;
						}
						break;
					}
					else {
						cnt++;
					}

				}
			}//가장 최근에 사용하지 않는 것 찾기;
			int flag = 0;
			for (int j = 0; j < LRU.size(); j++) {
				if (!strcmp(LRU[j].C.c_str(), cities[i].c_str())) {
					answer += 1;
					flag = 1;
					break;
				}
			}
			if (flag==0) {
				//int idx = searchIdx(i, cacheSize, LRU, cities);
				answer += 5;
				LRU[idx].C= cities[i];
			}

		}
	}
	return answer;
}
int main(void)
{
	cout << solution(0, { "Jeju", "Pangyo", "NewYork", "newyork" });
	return 0;
}

이문제는 우선 풀려면 LRU 에 대해서 알아야합니다. 운영체제를 공부하면 알게되는

알고리즘인데 여기서는 캐시라는 곳에 있는 지역이름중에서 현재 위치에서

가장 뒤에 있는 것을 교체해주는 알고리즘인데 위에 제주, 판교, 뉴욕, 파리가 입력이면

3의 공간이면 제주 판교 뉴욕이 들어있고 파리로 교체를 할때 파리를 기준으로

제주는 3번째, 판교는 2번째, 뉴욕,1번째로 진짜 최근에 안쓰인 제주를 파리로 교체해주면

되는 것입니다. 이렇게 배우고 나니 구현만 하면 되겠죠? 

그리고 이문제는 대소 문자를 구분하지 않는다고 되어있어서 처음부터 전부 대문자로 

만들고 비교를 진행해주면 좀 이해하기도 쉽고 구현도 복잡하지 않다고 생각합니다.

무튼 오늘은 여기까지 이고 여러분들도 도전해보세요.