코딩테스트준비
2022 카카오 테크 인턴십 - 프로그래머스
haeullee
2023. 8. 29. 19:40
https://school.programmers.co.kr/learn/challenges?order=recent&partIds=31236
코딩테스트 연습 | 프로그래머스 스쿨
개발자 취업의 필수 관문 코딩테스트를 철저하게 연습하고 대비할 수 있는 문제를 총망라! 프로그래머스에서 선발한 문제로 유형을 파악하고 실력을 업그레이드해 보세요!
school.programmers.co.kr
1. 성격 유형 검사하기
- 특징: map
- 구현방법: map을 이용하여, 점수 부여
- 코드
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
unordered_map<char, int> _map;
string solution(vector<string> survey, vector<int> choices)
{
string answer = "";
int n = survey.size();
int score[7] = {3, 2, 1, 0, 1, 2, 3};
_map['R'] = 0; _map['T'] = 0; _map['C'] = 0; _map['F'] = 0;
_map['J'] = 0; _map['M'] = 0; _map['A'] = 0; _map['N'] = 0;
for(int i = 0; i < n; i++)
{
char first = survey[i][0];
char second = survey[i][1];
int curv = choices[i];
if(curv >= 5)
{
_map[second] += score[curv-1];
}
if(curv <= 3)
{
_map[first] += score[curv-1];
}
}
if(_map['R'] >= _map['T']) answer.push_back('R');
else answer.push_back('T');
if(_map['C'] >= _map['F']) answer.push_back('C');
else answer.push_back('F');
if(_map['J'] >= _map['M']) answer.push_back('J');
else answer.push_back('M');
if(_map['A'] >= _map['N']) answer.push_back('A');
else answer.push_back('N');
return answer;
}
2. 두 큐 합 같게 만들기
- 특징: queue, 그리디
- 구현방법:
- 입력으로 들어온 queue1, queue2 벡터값을 _queue1, _queue2(queue<int> 형)에 넣고, 각각의 합을 구해서 q1(long long형), q2(long long형)에 저장함
- while(true)
- q1 > q2 이면, q1의 맨 앞의 값을 빼서 q2에 넣고, answer(몇번 이 연산을 했는지 저장)을 1증가시킴 (반대의 경우에도)
- q1 == q2이면, break
- **_queue1, _queue2가 empty이거나, p1 + p2값이 홀수이거나, answer이 600000보다 커지면 종료
- 어려웠던 부분
- 마지막 종료 조건을 못찾아서 시간 초과가 발생했다..... queue1 = queue2 <= 300,000이므로 600000연산을 수행하면, 이미 탐색했던 구간으로 돌아온다...프로그래머스에서 제공하는 테스트케이스로 시간초과가 난건데,,, 시험때 이부분까지 생각해서 종료 조건을 넣을 수 있을지,,,, 모르겠다.
- 코드
#include <bits/stdc++.h>
using namespace std;
int solution(vector<int> queue1, vector<int> queue2) {
int answer = 0;
long long q1 = 0; long long q2 = 0;
queue<int> _queue1; queue<int> _queue2;
for(int i = 0; i < queue1.size(); i++)
{
q1 += queue1[i];
_queue1.push(queue1[i]);
}
for(int i = 0; i < queue2.size(); i++)
{
q2 += queue2[i];
_queue2.push(queue2[i]);
}
long long avg = (q1 + q2) % 2;
long long avg1 = (q1 + q2) / 2;
while(true)
{
if(_queue1.empty() || _queue2.empty() || avg == 1 || answer > 600000)
{
answer = -1;
break;
}
if(q1 > q2)
{
int q1front = _queue1.front();
_queue1.pop();
_queue2.push(q1front);
q1 -= q1front;
q2 += q1front;
answer++;
}
else if(q1 < q2)
{
int q2front = _queue2.front();
_queue2.pop();
_queue1.push(q2front);
q2 -= q2front;
q1 += q2front;
answer++;
}
else
{
break;
}
}
return answer;
}3. 코딩테스트 공부
- 특징: dp
- 어려웠던 부분
- 문제 읽고 포기했다. 해답을 보니 역시나 dp였다... dp인거 알고 풀어보려했는데,,, 못풀었다.
- 참고 블로그: https://taehoung0102.tistory.com/211
- 구현 방법
- 목표 알고력과 목표 코딩력을 구함
- alp가 목표 알고력보다 클 경우, alp = 목표 알고력/ cop가 목표 코딩력 클 경우, cop= 목표 알고력 (dp 배열의 인덱스가 초과하는 경우를 막기 위해)
- dp[i][j] 정의 (알고력이 i이고, 코딩력이 j일 때, 최단시간)
- alp부터 목표 알고력, cop부터 목표 코딩력을 순회하면서
- dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1);
- dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1);
- 문제 순회하면서 문제 풀수 있는 경우
- dp[i+p[2]][j+p[3]] = min(dp[i+p[2]][j+p[3]] , dp[i][j] + p[4]);
- i+p[2]와 j+p[3]가 각각 ga, gc보다 클경우는 따로 처리 -> 목표보다 값이 클경우도 목표값으로 설정해둬야 anwer을 dp[목표알고력][목표코딩력]으로 구할 수 있다.
- 코드
#include <bits/stdc++.h>
using namespace std;
int dp[155][155];
int solution(int alp, int cop, vector<vector<int>> problems) {
int answer = 0;
int ga = 0; int gc = 0;
//목표값 구하기
for(int i = 0; i< problems.size(); i++)
{
ga = max(ga, problems[i][0]);
gc = max(gc, problems[i][1]);
}
if(alp >= ga && cop >= gc)
{
return answer;
}
if(alp >= ga) alp = ga;
if(cop >= gc) cop = gc;
for(int i = 0; i < 155; i++)
{
fill(dp[i], dp[i]+154, INT_MAX);
}
dp[alp][cop] = 0;
for(int i = alp; i <= ga; i++)
{
for(int j = cop; j <= gc; j++)
{
dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1);
dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1);
for(auto p: problems)
{
if(i >= p[0] && j >= p[1]) //문제 풀 수 있으면
{
if(i+p[2] >= ga && j+p[3] >= gc)
{
dp[ga][gc] = min(dp[ga][gc], dp[i][j] + p[4]);
}
else if(i+p[2] >= ga && j+p[3] < gc)
{
dp[ga][j+p[3]] = min(dp[ga][j+p[3]], dp[i][j] + p[4]);
}
else if(i+p[2] < ga && j+p[3] >= gc)
{
dp[i+p[2]][gc] = min(dp[i+p[2]][gc], dp[i][j] + p[4]);
}
else
{
dp[i+p[2]][j+p[3]] = min(dp[i+p[2]][j+p[3]] , dp[i][j] + p[4]);
}
}
}
}
}
answer = dp[ga][gc];
return answer;
}4. 등산코스 정하기
- 특징: 다익스트라
- 어려웠던 부분
- 이 문제를 dfs로 풀었다,,, 그러면 시간초과가 난다.
- 뭔가 아이디어가 떠오르면 바로 구현하는 데, 시간 복잡도랑 예외 상황을 충분히 생각하는 습관을 들여야 될거같다.
- 답지를 찾아보니 다익스트라로 푸는 문제였다.
- 다익스트라는 한 노드에서 모든 노드로의 최단거리를 구하는 알고리즘으로, 시간복잡도는 O(E logV) 이다. 이문제에서 출입구별로 다익스트라 알고리즘을 돌리게되면, V * O(E logV) 가되어 대략 10^10이된다.
- 이 문제에서는 출입구가 어디인지는 상관이 없다. 따라서 모든 출입구에서 동시에 출발하여 다익스트라 알고리즘을 한번만 돌리는 방식으로 문제를 풀 수 있다.
- 한가지 주의할 점은 , paths를 순회하면서, adj 그래프를 받을 때, 노드를 나타내는 u나 v가 출입구 혹은 산봉우리라면 따로 처리를 해주어야 한다는 것이다.
- 산봉우리 노드에서는 다른 노드로 갈 수 없고, 출입구 노드에서는 다른 노드로부터 들어올 수 없다. 따라서 단방향 그래프로 받아줘야한다.
- 산봉우리나 출입구가 아닌 노드는 양방향 그래프로 받아준다.
- 이 문제를 dfs로 풀었다,,, 그러면 시간초과가 난다.
//dfs 코드로 시간초과가 난다
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> adj[50004]; // 거리, 이어진지점
int pri[50004]; // 지점 속성(0: 쉼터, 1: 출입구, 2: 산봉우리) *1부터 시작
int ans[50004]; //테스트용
int dist[50004];
map<int, int> m; //산봉우리, 최솟값
int firstgate;
int mx;
int tn; int gsize; int ssize;
void dfs(int cur, int curn)
{
if(cur == tn-gsize-ssize+1) return;
for(auto nxt: adj[curn])
{
int nxtw = nxt.first;
int nxtp = nxt.second;
if(dist[nxtp] != -1) continue;
if(pri[nxtp] == 1) continue;
int prevmx = mx;
dist[nxtp] = 1;
mx = max(mx, nxtw);
if(pri[nxtp] == 2)
{
if(m.find(nxtp) != m.end() && m[nxtp] > mx)
{
m[nxtp] = mx;
}
if(m.find(nxtp) == m.end() )
{
m[nxtp] = mx;
}
dist[nxtp] = -1;
mx = prevmx;
continue;
}
dfs(cur+1, nxtp);
dist[nxtp] = -1;
mx = prevmx;
}
}
bool cmp(const pair<int,int>& a, const pair<int,int>& b) {
if (a.second == b.second) return a.first < b.first;
return a.second < b.second;
}
vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
vector<int> answer;
tn = n;
gsize = gates.size();
ssize = summits.size();
for(int i = 0; i < paths.size(); i++) //지점 1부터 시작
{
int st = paths[i][0];
int en = paths[i][1];
int w = paths[i][2];
adj[st].push_back(make_pair(w, en));
adj[en].push_back(make_pair(w, st));
}
for(int i = 0; i < gates.size(); i++)
{
pri[gates[i]] = 1;
}
for(int i = 0; i < summits.size(); i++)
{
pri[summits[i]] = 2;
}
//게이트 기준으로 dfs
for(int i = 0; i < gates.size(); i++)
{
fill(dist, dist+50003, -1);
mx = 0;
firstgate = gates[i];
dist[firstgate] = 1;
dfs(0, firstgate); //cur, 시작점
}
vector<pair<int,int>> vec( m.begin(), m.end() );
sort(vec.begin(), vec.end(), cmp);
answer.push_back(vec[0].first); answer.push_back(vec[0].second);
return answer;
}
- 코드
#include <bits/stdc++.h>
using namespace std;
int u, v, w;
vector<pair<int, int>> adj[50002];
int d[50002];
int mn;
int answer_summits;
unordered_set<int> s;
unordered_set<int> g;
vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
vector<int> answer;
for(int i = 0; i < summits.size(); i++)
{
s.insert(summits[i]);
}
for(int i = 0; i < gates.size(); i++)
{
g.insert(gates[i]);
}
for(int i = 0; i < paths.size(); i++)
{
u = paths[i][0]; v = paths[i][1]; w= paths[i][2];
if(s.find(u) != s.end()) // u가 산봉우리이면 나가는 간선 없음
{
adj[v].push_back(make_pair(w, u));
}
else if(s.find(u) != g.end()) // u가 입구이면 들어오는 간선 없음
{
adj[u].push_back(make_pair(w, v));
}
else if(s.find(v) != s.end()) // v가 산봉우리이면
{
adj[u].push_back(make_pair(w, v));
}
else if(s.find(v) != s.end()) // v가 입구이면
{
adj[v].push_back(make_pair(w, u));
}
else
{
adj[u].push_back(make_pair(w, v));
adj[v].push_back(make_pair(w, u));
}
}
fill(d, d+n+1, INT_MAX);
mn = INT_MAX;
priority_queue<pair<int ,int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for(int i = 0; i < gates.size(); i++)
{
d[gates[i]] = 0;
pq.push(make_pair(d[gates[i]], gates[i])); // 비용, 노드
}
while(!pq.empty())
{
auto cur = pq.top(); pq.pop();
if(d[cur.second] != cur.first) continue;
for(auto nxt: adj[cur.second])
{
if(d[nxt.second] <= max(d[cur.second], nxt.first)) continue;
d[nxt.second] = max(d[cur.second], nxt.first);
pq.push(make_pair(d[nxt.second], nxt.second));
}
}
for(int i = 0; i < summits.size(); i++)
{
mn = min(mn, d[summits[i]]);
}
sort(summits.begin(), summits.end());
for(int i = 0; i < summits.size(); i++)
{
if(d[summits[i]] == mn)
{
answer_summits = summits[i];
break;
}
}
answer.push_back(answer_summits); answer.push_back(mn);
return answer;
}