2020 KAKAO BLIND RECRUITMENT 1차예선 풀이

카카오 2021 문제를 푼 뒤 2020 문제로 넘어왔습니다. 이전 글과 마찬가지로 매일매일 공부기록용으로 글을 작성하는 것이기 때문에 문제를 풀면 글이 업데이트 하는 식으로 진행할 생각입니다. 2020은 문자열 문제가 많다는 느낌을 받았습니다. (문자열에 약한..)

또한 문제에 오해를 할 수 있도록 내놓은 구문이 많아 헷갈리기 쉬우므로 주의가 필요합니다.

---

https://programmers.co.kr/learn/courses/30/lessons/60057

코딩테스트 연습 - 문자열 압축

A번 문자열 압축

알고리즘 : 문자열 / 구현

최대 길이 N이 1000으로 작기 때문에 다른걸 사용하지 않고 모든 길이에 대해 다 해본다면 풀이할 수 있습니다.

예제 5 설명을 보면 특정 칸마다 자르는 것이므로 (자르는 칸이 3칸이면 0,3,6,9 ... 에서 자르는 것) 2-4, 5-7 이렇게 자르는 것으로

오해할 수 있습니다.

< CODE - 문자열 압축 >

#include <iostream> #include <string> #include <vector> using namespace std; int solution(string s) { int answer = 987654321; for (int i = 1; i <= s.size(); i++) { string recent = s.substr(0,i); int cnt = 1; int length = 0; for (int j = i; j < s.size(); j += i) { string sub = s.substr(j, i); if (recent == sub) cnt++; else { if (cnt == 1) length += recent.length(); else length += to_string(cnt).length() + recent.length(); cnt = 1; recent = sub; } } if (cnt > 0) { if (cnt == 1) length += recent.length(); else length += to_string(cnt).length() + recent.length(); } answer = min(answer, length); } return answer; }

---

https://programmers.co.kr/learn/courses/30/lessons/60058

코딩테스트 연습 - 괄호 변환

B번 괄호 변환

알고리즘 : 문자열 / 재귀 / 분할정복?

이런 방법으로 "균형잡힌 괄호 문자열"가 "올바른 괄호 문자열"이 된다는 것을 알게 된 문제였습니다.

구문 중 4-4에서 문자열u를 앞뒤를 제외하고 뒤집는다는 구문이 있어, reverse를 시도하였는데 52점이 나왔습니다.

이 방법으로 진행할 경우에도 올바른 괄호 문자열은 나오는 듯?? 해보이지만, 원하는 답과 달라서 오답으로 나오는 듯합니다.

reverse를 하는 것이 아닌 각 괄호를 현재 위치에서 뒤집는 것을 의미합니다.

< CODE - 괄호 변환 >

#include <iostream> #include <string> #include <vector> #include <stack> #include <algorithm> using namespace std; stack<char> s; string divide(string u, string v); string calculate(string u, string v); string divide(string u, string v) { // 1 if (u.empty()) return u; for (int i = 0; i < u.size(); i++) { if (s.empty() || u[i] == s.top()) s.push(u[i]); else s.pop(); if (s.empty()) { if (u.length() - 1 == i) { // 2 u = calculate(u, v); return u; } return divide(u.substr(0, i + 1), u.substr(i + 1, u.length() - (i + 1))); } } return u; } string calculate(string u, string v) { if (u.empty()) return u; bool isPerfect = true; string ret = "("; stack<char> stk; // 3 for (int i = 0; i < u.size(); i++) { if (u[i] == '(') stk.push(u[i]); else { if (stk.empty()) { isPerfect = false; break; } else stk.pop(); } } if (!stk.empty()) isPerfect = false; // 3-1 if (isPerfect) return u + divide(v, ""); // 4 ret += divide(v, ""); ret += ')'; for (int i = 1; i < u.size() - 1; i++) { if (u[i] == '(') ret += ')'; else ret += '('; } return ret; } string solution(string p) { p = divide(p, ""); return p; }

---

https://programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠

C번 자물쇠와 열쇠

알고리즘 : 구현

키 배열의 크기는 락 배열보다 작으므로 락 배열 크기로 만들어 준 뒤, 락 배열은 n*3크기로 만들어 예외처리할 경우를 줄여줍니다.

그리고 키 배열을 돌려 처리하면 됩니다. 키가 1인 부분과 락이 0인 부분만 체크할 것이 아니라 키가 1인 부분과 락이 1인 부분이 있으면 해당 키를 사용할 수 없으므로 넘어갑니다. 총 n,m <= 20이라 비트마스크로도 처리할 수 있지만, 배열로 처리하였습니다.

< CODE - 자물쇠와 열쇠 >

#include <iostream> #include <string> #include <exception> #include <vector> using namespace std; vector<vector<int>> k; vector<vector<int>> l; int n; int m; void rotateArray() { vector<vector<int>> tempK = k; for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) tempK[i][j] = k[m - 1 - j][i]; k = tempK; } void printArray() { for(int i = 0; i < k.size(); i++) { for(int j = 0; j < k[i].size(); j++) cout << k[i][j]; cout << endl; } } bool solution(vector<vector<int>> key, vector<vector<int>> lock) { n = lock.size(); m = key.size(); int cnt = 0; k.resize(n,vector<int>(n,0)); l.resize(n * 3,vector<int>(n*3,2)); for(int i = n; i < 2*n; i++) for(int j = n; j < 2*n; j++) { l[i][j] = lock[i - n][j-n]; if(lock[i-n][j-n] == 0) cnt++; } for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) k[i][j] = key[i][j]; for(int t = 0; t < 4; t++) { for(int i = 0; i < 2*n; i++) { for(int j = 0; j < 2*n; j++) { int check = 0; bool isPossible = true; for(int y = i; y < i + n; y++) { for(int x = j; x < j + n; x++) { if(k[y-i][x-j] == 1 && l[y][x] == 0) check++; if(k[y-i][x-j] == 1 && l[y][x] == 1) isPossible = false; } } if(check == cnt && isPossible) return true; } } rotateArray(); } return false; }

---

https://programmers.co.kr/learn/courses/30/lessons/60060

코딩테스트 연습 - 가사 검색

D번 가사검색

알고리즘 : 자료구조(트라이)

난이도 상 2020년 블라인드 테스트에서 가장 어려운 문제라고 나오는데 트라이를 공부한 적이 있어 쉽게 풀이하였습니다.

삼성 B형 연습할 때도 생각이 나서 정적 트라이로 풀이하였습니다. fr???도 있는 반면 ???st 같은 경우도 있기 때문에 각 문자마다

일반 문자열과 reverse문자열을 만들어 각각 다른 루트에 저장시켰고, 빠른 탐색을 위해 문자열의 길이별로 루트를

나눠주었습니다. 생각보다 쉽게 디버깅 없이 풀이되었습니다.

중복처리는 다른 방법이 떠올랐지만 쉽게 하기 위해 set을 사용하였습니다.

< CODE - 가사검색 >

#include <string> #include <vector> #include <algorithm> #include <set> #include <iostream> using namespace std; struct node { node * child[26] = {nullptr}; int childCount = 0; }; set<string> s; node * root[2][10005]; node nodes[2020005]; int nodeIdx = 0; node * alloc() { return &nodes[nodeIdx++]; } void init(const string & str, bool r) { node * cur = root[r][str.length()]; for(int i = 0; i < str.length(); i++) { int idx = str[i] - 'a'; if(cur->child[idx] == nullptr) { cur->child[idx] = alloc(); } cur->childCount++; cur = cur->child[idx]; } } int findInTrie(const string & str, bool r) { node * cur = root[r][str.length()]; if(cur == nullptr) return 0; for(int i = 0; i < str.length(); i++) { if(str[i] == '?') return cur->childCount; else { int idx = str[i] - 'a'; if(cur->child[idx] == nullptr) return 0; cur = cur->child[idx]; } } } vector<int> solution(vector<string> words, vector<string> queries) { vector<int> answer; for(int i = 1; i <= 10000; i++) { root[0][i] = alloc(); root[1][i] = alloc(); } for(int i = 0; i < words.size(); i++) { if(!s.count(words[i])) { s.insert(words[i]); init(words[i], false); reverse(words[i].begin(),words[i].end()); init(words[i], true); } } for(int i = 0; i < queries.size(); i++) { bool r = queries[i][0] == '?'; if(r) reverse(queries[i].begin(), queries[i].end()); answer.push_back(findInTrie(queries[i],r)); } return answer; }

---

https://programmers.co.kr/learn/courses/30/lessons/60061

코딩테스트 연습 - 기둥과 보 설치

E번 기둥과 보 설치

알고리즘 : 구현 / 시뮬레이션

단순 시뮬레이션입니다. 처음에 기둥과 보를 삭제하면 그로 인해 발생하는 균열로 우르르 무너지는 것까지 구현해야하는 줄 알고

큐로 구현하였는데 아니였습니다;; 그냥 더 이상 유지가 불가능한 경우가 나오면 무시하면 됩니다.

< CODE - 기둥과 보 설치 >

#include <iostream> #include <string> #include <vector> using namespace std; #define MAX 105 bool exGidung[MAX][MAX]; bool exBo[MAX][MAX]; bool isSafe(int y, int x, bool isBo, bool second = true) { if (second && (!isBo && !exGidung[y][x] || isBo && !exBo[y][x])) return true; if (!isBo) { if (y == 0 || exGidung[y - 1][x] || exBo[y][x] || (x > 0 && exBo[y][x - 1])) return true; } else { if (exGidung[y - 1][x] || exGidung[y - 1][x + 1] || (x > 0 && exBo[y][x - 1] && exBo[y][x + 1])) return true; } return false; } vector<vector<int>> solution(int n, vector<vector<int>> build_frame) { vector<vector<int>> answer; for (auto a : build_frame) { int x = a[0]; int y = a[1]; bool isBo = a[2]; bool isLaunch = a[3]; if (!isBo) { if (isLaunch) { if (isSafe(y,x,isBo,false)) exGidung[y][x] = true; } else { exGidung[y][x] = false; if (isSafe(y + 1, x, 0) && isSafe(y + 1, x, 1) && isSafe(y + 1, x - 1, 1)) continue; else exGidung[y][x] = true; } } else { if (isLaunch) { if (isSafe(y,x,isBo,false)) exBo[y][x] = true; } else { exBo[y][x] = false; if (isSafe(y, x, 0) && isSafe(y,x+1,0) && isSafe(y, x + 1, 1) && isSafe(y, x - 1, 1)) continue; else exBo[y][x] = true; } } } for (int j = 0; j <= n; j++) { for (int i = 0; i <= n; i++) { if (exGidung[i][j]) answer.push_back({ j,i,0 }); if (j < n && exBo[i][j]) answer.push_back({ j,i,1 }); } } return answer; }

---

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

코딩테스트 연습 - 외벽 점검

F번 외벽 점검

알고리즘 : 비트마스크 / 순열

각 친구가 닦는 순열을 모두 만들어 비트마스크를 통해 해결합니다. 구현만 떠오르면 쉽게 해결할 수 있는 문제입니다.

< CODE - 외벽 점검 >

#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; #define MAX 205 vector<int> chance; int wSize; void makeChance(int now, int bit, int size) { if(bit == (1 << size) - 1) chance.push_back(now); for(int i = 0; i < size; i++) { if(bit & (1 << i)) continue; makeChance(now * 10 + i, bit | (1 << i), size); } } int solve(int chc, int start, int n, const vector<int> & weak, const vector<int> & dist) { int tChc = chc; int ret = 0; int check[MAX] = {0}; int chk = 0; while(chc != 1) { int cur = chc % 10; chc /= 10; check[weak[start] % n] = true; chk++; ret++; for(int i = start + 1; i < weak.size(); i++) { if(check[weak[i]%n]) break; else if(weak[i] - weak[start] <= dist[cur]) { check[weak[i] % n] = true; chk++; } else { start = i; break; } } if(chk == wSize) return ret; } return 987654321; } int solution(int n, vector<int> weak, vector<int> dist) { int answer = 987654321; wSize = weak.size(); for(int i = 0; i < wSize- 1; i++) weak.push_back(weak[i] + n); makeChance(1, 0, dist.size()); for(auto c : chance) for(int i = 0; i < wSize; i++) answer = min(answer, solve(c, i, n,weak, dist)); if(answer == 987654321) answer = -1; return answer; }

---

G번 문제는 자주 나오는 메모이제이션 완전탐색 스킵합니다

< 2021 카카오 BLIND RECRUITMENT 1차예선 풀이글 >

2021 KAKAO BLIND RECRUITMENT 1차예선 풀이(진행중)

태그 : #2020 카카오 코딩테스트 #2020 카카오 코테 #카카오 코딩테스트 #카카오 코테 #2020 카카오 #2020 카카오 블라인드 코딩테스트 1차

#2020 카카오 코딩테스트 2차 #2020 카카오 블라인드 1차 #카카오 문제 #카카오 순위검색 #프로그래머스 문자열 압축 #프로그래머스 괄호 변환

#2020 KAKAO BLIND RECRUITMENT #카카오 1차 합격컷 #카카오 1차 합격