2020년 카카오 인턴쉽 코딩 테스트를 하기 전 연습을 위해 19년 겨울 인턴쉽 코딩 테스트를 연습하기로 했다. 그래서 4시간 시간을 재고 5문제를 쭉 풀어보았다.
시간 내에 5문제를 모두 풀 수 있었지만 5번에서 실수도 하고 O(N)의 풀이가 있었는데 생각해내지 못해 O(NlgN)으로 풀었다. 그래서 끝나고 더 알아봐서 풀게 되었고 여기에 3가지의 풀이를 적어놓았다.
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
N x N 크기의 정사각 격자가 있다. 각 격자 칸에는 다양한 1 x 1 크기의 인형이 격자의 가장 아래 칸부터 쌓여 있다. 입력으로 크레인이 뽑아갈 열의 번호가 주어진다. 그러면 크레인은 가장 위의 칸의 인형을 들어 오른쪽의 바구니의 가장 아래 칸부터 인형을 놓는다. 만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 바구니에서 사라진다.
이때 사라지는 인형의 총개수를 출력한다.
$N \times N$ 격자에서 주어진 열 번호에서 가장 위의 인형부터 뽑히게 된다. 뽑힌 인형은 격자에서 0으로 처리해주면 되고 그 인형을 바구니에 담아야 한다. 바구니는 가장 아래 칸부터 인형이 쌓이고 연속해서 쌓이면 없어지므로 Stack의 구조를 가진다. 따라서 맵에서 뽑아갈 때마다 위의 인형을 가지고 stack에 넣고 만일 넣기 전에 stack의 top이 뽑은 인형과 같은 경우 stack에서 pop을 해주고 터진 인형의 개수를 체크해주면 된다.
격자에서 인형을 뽑아갈 때 단순히 위에서부터 탐색해주면서 0으로 만들어줘도 되고 각 열을 queue로 만들어서 관리해주어도 된다.
#include <bits/stdc++.h>
using namespace std;
queue<int> q[31];
int solution(vector<vector<int>> board, vector<int> moves) {
int answer = 0;
int n = board.size();
int m = board[0].size();
stack<int> st;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if(board[j][i]!=0)
q[i+1].push(board[j][i]);
}
}
for (int i = 0; i < moves.size(); i++) {
if (st.empty()) {
if (!q[moves[i]].empty()) {
st.push(q[moves[i]].front());
q[moves[i]].pop();
}
}
else {
if (!q[moves[i]].empty()) {
if (q[moves[i]].front() == st.top()) {
st.pop();
q[moves[i]].pop();
answer+=2;
}
else {
st.push(q[moves[i]].front());
q[moves[i]].pop();
}
}
}
}
return answer;
}
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
튜플 문제에서 중요한 성질은 튜플은 순서가 달라지면 다른 튜플이라는 점과 ai는 집합에 n - i + 1번 나온다는 점이다.
a1은 모든 집합에서 n번 나오고 a2는 n-1번 나온다. 그렇다는 얘기는 집합의 원소가 1개는 a1이고 집합의 원소가 2개인 집합은 a1, a2가 들어있다는 말이다. 따라서 집합의 크기가 i인 집합은 {a1~ai}를 가진다.
그러면 집합의 순서가 섞여서 입력이 들어오므로 이 집합들을 분리하여 사이즈 크기로 정렬을 한다면 순차적으로 a1이 들어있는 집합, a1, a2가 들어있는 집합 순으로 정렬이 된다. 정렬을 했으므로 집합의 크기가 작은 순서대로 있는 원소를 set에 집어넣는다면 결국 그게 답이 된다.
#include <bits/stdc++.h>
using namespace std;
vector<int> solution(string s) {
vector<int> answer;
vector<vector<int>> ss(501);
set<int> st;
bool flg = 0;
int cnt = 0;
string num = "";
for (int i = 0; i < s.size(); i++) {
if (!flg && s[i] == '{') {
flg = 1;
}
else if(flg && s[i]==','){
ss[cnt].push_back(strtol(num.c_str(),NULL,10));
num = "";
}
else if (flg && s[i] == '}') {
flg = 0;
ss[cnt].push_back(strtol(num.c_str(), NULL, 10));
num = "";
cnt++;
}
else if (s[i] >= '0' && s[i] <= '9') {
num += s[i];
}
}
sort(ss.begin(),ss.begin()+cnt ,
[](vector<int> a, vector<int> b) {return a.size() < b.size(); });
for(int i=0;i<cnt;i++) {
for(int j=0; j<ss[i].size();j++) {
if (!st.count(ss[i][j])) {
st.insert(ss[i][j]);
answer.push_back(ss[i][j]);
}
}
}
return answer;
}
3번 불량 사용자
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
여러 개의 user_id가 주어지고 그 중 보안을 위해 1개 이상의 문자를 *로 가려서 제제할 banned_id가 주어진다. 그때 밴할 수 있는 경우의 수를 모두 구하는 문제이다. 처음은 해당되는 경우를 다 카운트해서 조합으로 구해야 하나 했는데 N의 제한이 8이어서 그냥 완전 탐색으로 풀 수 있는 문제였다.
완전 탐색으로 푸는데 *로 아이디가 가려지기 때문에 다른 banned_id로 체크를 해도 같은 user_id가 가려질 수도 있다. 따라서 같은 경우가 나오는 경우를 체크해줘서 그럴 경우에는 result를 증가시켜주면 안 된다. 나는 그 경우를 set과 비트를 이용하여 같은 경우를 체크해주었다.
#include <bits/stdc++.h>
using namespace std;
int vis;
set<int> st;
int ans = 0;
int n,m;
void dfs(vector<string> user_id, vector<string> banned_id,int idx, int cnt) {
if (cnt == m) {
if (st.count(vis))
return;
st.insert(vis);
ans++;
return;
}
for (int i = idx; i < m; i++) {
for (int j = 0; j < n; j++) {
if (vis & (1<<j)) continue;
if (user_id[j].size() != banned_id[i].size()) continue;
int bs = banned_id[i].size();
bool ok = 0;
for (int k = 0; k < bs; k++) {
if (banned_id[i][k] == '*') continue;
if (banned_id[i][k] != user_id[j][k]) {
ok = 1;
break;
}
}
if (!ok) {
vis |=1<<j;
dfs(user_id, banned_id, i+1, cnt+1);
vis &= ~(1<<j);
}
}
}
}
int solution(vector<string> user_id, vector<string> banned_id) {
int answer = 1;
n = user_id.size();
m = banned_id.size();
st.clear();
dfs(user_id, banned_id, 0, 0);
answer = ans;
return answer;
}
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제가 요구하는 것은 아주 간단하다. 하지만 제한사항이 $10^{12}$이기에 생각해내기가 어려웠다. N도 200000이기에 O(N)이나 O(NlgN)으로 풀어야했다. NlgN을 생각했더니 떠오르는 게 set이 있었고 수가 다 있다고 가정하고 있을 때 그 수를 저장하고 없을 때는 남아있는 것 중 크거나 같은 수를 저장하면 되겠다생각을 했다. 그래서 전 처리과정을 해주었다.
Set은 항상 정렬이 된 상태로 유지하므로 맨 뒤의 값이 최댓값이다. 따라서 저장된 룸 번호를 정렬을 해주면 set안에 있는 값이 나왔을 때 최댓값보다 큰 값을 insert 해주고 없으면 그대로 값을 insert 해준다.
이제 set안에는 배정될 룸번호가 정렬된 상태로 모여있다. 이걸 다시 인덱스 순으로 set안에 있을 땐 그 값을 정답 벡터에 넣어주고 지우면 되고, set안에 없을 경우는 lower_bound를 구해주면 크거나 같은 수 중 가장 최솟값을 구해주므로 그 값을 정답 벡터에 넣고 erase 해주면 된다.
set은 erase와 insert 모두 lgN이므로 O(NlgN)이다
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
vector<long long> solution(long long k, vector<long long> room_number) {
vector<long long> answer;
vll tmp = room_number;
sort(tmp.begin(), tmp.end());
set<ll> st;
st.insert(tmp[0]);
for(int i=1; i < tmp.size();i++) {
if (st.count(tmp[i])) {
ll sum = *st.rbegin()+1;
if (sum < tmp[i]) {
sum = tmp[i];
}
st.insert(sum);
}
else {
st.insert(tmp[i]);
}
}
for (int i = 0; i < room_number.size(); i++) {
if (st.count(room_number[i])) {
answer.push_back(room_number[i]);
st.erase(room_number[i]);
}
else {
ll loc = *st.lower_bound(room_number[i]);
answer.push_back(loc);
st.erase(loc);
}
}
return answer;
}
map으로 풀 수 있는 풀이가 있다. union find 함수에서 find와 경로 압축 기법을 사용하는 방식이다.
map에서 처음 생길 때는 값을 그냥 리턴해주고 p[x]=y+1을 해준다. 다음에 같은 좌표가 입력이 되면 p[x]=find(p[x]) 를 통하여 다음 노드들을 불러오면서 경로를 압축해주어 시간 복잡도를 줄인다. 하지만 이 방법은 결국 경로를 계속 따라가는 리스트 형식이기 때문에 위의 방법보다는 느리다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#include <string>
#include <vector>
#include <map>
using namespace std;
map<ll, ll> p;
ll find(ll x) {
if (p[x] == 0) return x;
else {
p[x] = find(p[x]);
return p[x];
}
}
vector<ll> solution(ll k, vector<ll> room_number) {
vector<ll> answer;
for (ll x : room_number) {
ll y = find(x);
answer.push_back(y);
p[y] = y + 1;
}
return answer;
}
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
징검다리는 무조건 건널수 있는 가장 가까운 돌을 건너야 한다. 그렇게 되면 한 명이 건널 때마다 모든 돌의 값이 1씩 줄어든다. 그런데 k만큼 점프를 할 수 있으므로 구간 k개안에 돌이 한 개라도 있으면 건너갈 수 있다. 따라서 1~k, 2~k+1, 3~k+2.... i~i+k-1 (i <=n-k+1)의 구간으로 나눴을 때 각 구간 별 최댓값의 최솟값이 정답이 된다.
이 문제는 모든 테스트 케이스가 통과하는 O(NlgN), O(NlgM) 방법 2가지와 O(N) 방법이 있다. (내가 푼 풀이로는) O(NK)처럼 단순히 모든 구간을 탐색해도 정답은 나오지만 시간 복잡도가 크기때문에 효율성 테스트를 통과하지 못한다.
첫 번째 방법은 이분 탐색이다. 이 방법은 각 구간 별 최댓값의 최솟값은 결국 1~M(stones의 MAX) 이므로 이분 탐색을 통해 만족하는 값을 찾아서 구하는 방식이다. 그 값이 만족하는지 여부는 연속되는 k개만큼 stones의 각 원소들이 전부 다 작으면 못 넘어가므로 그 수를 세어 체크해주면 된다. 각 시뮬레이션마다 이분 탐색을 하므로 O(NlgM)의 시간 복잡도를 가진다. (M은 최대 2억)
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define INF 1e9
using namespace std;
typedef vector<int> vi;
bool check(int mid, vector<int> stones, int k) {
int cnt = 0;
int mx = 0;
for (int i = 0; i < stones.size(); i++) {
if (stones[i] < mid) {
cnt++;
}
else {
if (cnt > mx)
mx = cnt;
cnt = 0;
}
}
mx=max(mx,cnt);
return mx >= k;
}
int solution(vector<int> stones, int k) {
int answer = 0;
int n = stones.size()-1;
int mi = 2*INF;
int s = 1;
int e = *max_element(all(stones));
int mid = 0;
while (s <= e) {
mid = (s + e) >> 1;
if (check(mid, stones, k)) {
e = mid - 1;
}
else {
mi = mid;
s = mid + 1;
}
}
answer = mi;
return answer;
}
두 번째 방법은 세그먼트 트리이다. 구간 합을 구할 때 쓰는 가장 대표적인 자료구조로 각 쿼리별로 lgN의 시간이 걸린다. 따라서 세그먼트 트리를 만들게 되면 init에 O(N) 쿼리별 O(lgN)으로 O(NlgN)의 시간복잡도를 가진다. O(N)으로 풀려다가 잘 생각이 안 나서 시간제한을 두고 문제를 풀 때 그냥 세그먼트 트리를 구현했다.
그런데 프로그래머스가 입력을 함수를 통해 주는 것때문에 init 함수에 stones 벡터를 값 복사 인자로 주어서 시간 초과 실수를 저지르기도 했다. 그래서 비 재귀로 다시 구현을 하였고 다시 재귀로 구현하여 &붙여 벡터를 바로 전달해주니까 잘 되었다.
세그먼트 트리의 구현은 이전 글을 참고해주기 바란다. → 세그먼트 트리
재귀
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
int seg[800000];
void init(int idx, int l, int r, vector<int> &stones) {
if (l != r) {
int mid = (l + r) >> 1;
init(idx << 1, l, mid, stones);
init(idx << 1 | 1, mid + 1, r, stones);
seg[idx] = max(seg[idx << 1], seg[idx << 1 | 1]);
}
else
seg[idx] = stones[l-1];
}
int getval(int idx, int l, int r, int i, int j) {
if (l > j || r < i) return 0;
if (i <= l && r <= j) {
return seg[idx];
}
int mid = (l + r) >> 1;
return max(getval(idx << 1, l, mid, i, j), getval(idx << 1 | 1, mid + 1, r, i, j));
}
int solution(vector<int> stones, int k) {
int answer = 0;
int n = stones.size();
int mi=1e9;
init(1,1,n,stones);
for(int i=1;i<=n-k+1;i++){
mi=min(mi,getval(1,1,n,i,i+k-1));
}
answer=mi;
return answer;
}비재귀
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
int n;
int seg[400000];
void init(vector<int>& stones) {
for (int i = 0; i < n; i++) {
seg[i + n] = stones[i];
}
for (int i = n - 1; i >= 1; i--) {
seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}
}
int getval(int l, int r) {
int ans = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
ans = max(ans, seg[l++]);
}
if (r & 1) {
ans = max(ans, seg[--r]);
}
}
return ans;
}
int solution(vector<int> stones, int k) {
int answer = 0;
n = stones.size();
int mi = 1e9;
init(stones);
for (int i = 0; i <= n - k ; i++) {
mi = min(mi, getval(i, i + k ));
}
answer = mi;
return answer;
}
세 번째 방법은 덱이다. 덱은 앞, 뒤로 모두 삽입과 제거가 가능한 자료구조이다. 이 덱을 이용해서 O(N)의 시간 복잡도의 코드를 구현할 수 있다. 위에서 말했듯이 우리에게 중요한 건 각 구간 별 최댓값이다. 그러면 어떠한 K개의 구간을 덱에 넣었을 때 만약 현재 넣는 값이 덱의 back보다 크면 덱의 back 값은 지금 넣는 값보다 인덱스도 전이고 값도 낮으므로 필요가 없다. 따라서 그 값을 빼주고 다시 비교를 한다.
이 작업을 반복하게 되면 덱의 front 값은 현재 구간의 최댓값이 남게 된다. 그럼 이제 구간을 지나갔을 때 지나간 원소가 최댓값일 수도 있다. 그래서 stones[i-k]과 front 값을 비교를 한다. 만일 같지 않으면 우리가 앞에서 저장할 필요가 없는 값이어서 덱에 넣지 않은 값이므로 다시 위의 작업을 해주고 같은 값일 경우 front를 pop 해준다.
이 작업은 모든 원소를 한 번씩 넣고 한 번씩 빼므로 최대 2N으로 시간 복잡도 O(N)이 된다.
1. 덱에 순차적으로 값을 넣어준다.
2. k개를 지났을 때부터 덱의 front가 stones[i-k]와 같으면 pop 해준다.
3. 덱의 back이 stones [i]보다 크거나 같을 때까지 pop 해준다.
4. 덱에 stones[i]를 넣는다.
5. 3,4를 반복한다.
6. 덱의 front였던 값의 최솟값이 답이 된다.
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
int solution(vector<int> stones, int k) {
int answer = 0;
int n = stones.size();
deque<int> dq;
int cnt = 0;
set<int> st;
for (int i = 0; i < n; i++) {
if (cnt < k) {
while (!dq.empty() && dq.back() < stones[i]) {
dq.pop_back();
}
dq.push_back(stones[i]);
cnt++;
if (cnt == k) {
st.insert(dq.front());
}
}
else {
if (dq.front() == stones[i - k]) {
dq.pop_front();
}
while (!dq.empty() && dq.back() < stones[i]) {
dq.pop_back();
}
dq.push_back(stones[i]);
st.insert(dq.front());
}
}
answer = *st.begin();
return answer;
}'카카오 > 코딩 테스트' 카테고리의 다른 글
| 2021 카카오 신입 개발자 블라인드 2차 코딩 테스트 합격 (0) | 2020.10.14 |
|---|
댓글