2020문제들이라 그런지 최근 2021, 2022에 나온 문제들보단 단순한것같다.
시간을 재면서 풀었는데 5번 문제를 늦게 풀어서 아쉽다.
1. 키패드 누르기 00:10
그냥 구현문제이다. 난 왜인지 모르겠는데 코딩테스트를 풀어볼때면 젤 쉬운 1번 문제에서 좀 버벅인다.
vector<pair<int, int>> p{
{3, 1},{0, 0}, {0, 1}, {0, 2},
{1, 0},{1,1}, {1,2},
{2,0}, {2,1}, {2,2},
{3, 0}, {3,2},
};
int dist(int i, int j){
return abs(p[i].first - p[j].first) + abs(p[i].second - p[j].second);
}
string solution(vector<int> numbers, string hand) {
string answer = "";
int l = 10, r = 11;
for(int n: numbers){
if(n == 1 || n == 4 || n == 7){
l = n;
answer += 'L';
}else if(n == 3 || n == 6 || n == 9){
r = n;
answer += 'R';
}else{
int L_dist = dist(l, n);
int R_dist = dist(r, n);
if(L_dist < R_dist){
l = n;
answer += 'L';
}else if(L_dist > R_dist){
r = n;
answer += 'R';
}else{
if(hand == "right"){
r = n;
answer += 'R';
}else{
l = n;
answer += 'L';
}
}
}
}
return answer;
}
2. 수식 최대화 00:28
요것도 문자열을 이용한 파싱및 구현 문제였다. c++ 로 문자열을 다루는데 익숙해서 그럭저럭 풀만한데
코드도 정말 더럽게 풀었다. 이게뭐지..?
대충 next_permutation 으로 6가지 경우에 대해 탐색해주며 스택을 이용해 우선순위 순으로 모두 계산해줘서 값을 비교해주면 된다.
long long solution(string s) {
vector<string> arr;
for (int i = 1, j = 0; i <= s.size(); i++) {
if (i == s.size() || s[i] == '+' || s[i] == '-' || s[i] == '*') {
arr.pb(s.substr(j, i - j));
if (i != s.size())
arr.pb(s.substr(i, 1));
j = i + 1;
}
}
auto run = [&](string op, ll a, ll b) {
if (op == "*") return a * b;
else if (op == "+") return a + b;
else return a - b;
};
string op = "+-*";
sort(all(op));
ll ans = numeric_limits<ll>::min();
do {
map<char, int> p;
p[op[0]] = 1, p[op[1]] = 2, p[op[2]] = 3;
auto tmp = arr;
ll t = 0;
vector<string> tack;
for (int pri = 1; pri <= 3; pri++) {
for (int i = 0; i < sz(tmp); i++) {
if (p[tmp[i][0]] == pri) {
tack.push_back(tmp[i]);
} else {
if (sz(tack) && (op.find(tack.back()) != string::npos && p[tack.back()[0]] == pri)) {
string oper = tack.back();
tack.pop_back();
ll L = stoll(tack.back());
tack.pop_back();
ll R = stoll(tmp[i]);
tack.push_back(to_string(run(oper, L, R)));
} else {
tack.push_back(tmp[i]);
}
}
}
tmp = tack;
tack.clear();
}
ans = max(ans, abs(stoll(tmp[0])));
} while (next_permutation(all(op)));
return ans;
}
3. 보석 쇼핑 00:37
투 포인터 문제였다. 이때 약간 카카오가 이 알고리즘을 알면 그냥 풀수있게 해줄게 라는 문제의 느낌이 내게 문제들을 낸것같다.
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
vector<int> solution(vector<string> gems) {
vector<int> answer;
set<string> s;
for(auto ss: gems) s.insert(ss);
int m = s.size();
int n = gems.size();
int filled = 0;
int l = 0, r = 0;
map<string, int> cnt;
for(r = 0; r < n; r++){
if(cnt[gems[r]] == 0){
filled++;
}
cnt[gems[r]]++;
if(filled == m) break;
}
while(l < r && cnt[gems[l]] > 1){
cnt[gems[l]]--;
l++;
}
// cout << l << ", " << r;
vector<int> to(n, 1e9);
int min_len = r - l + 1;
to[l] = r;
for(r++; r < n; r++){
cnt[gems[r]]++;
while(l < r && cnt[gems[l]] > 1){
cnt[gems[l]]--;
l++;
}
to[l] = min(to[l], r);
min_len = min(min_len, r - l + 1);
}
for(int i = 0; i< n; i++){
if(to[i] - i + 1 == min_len){
return {i+1, to[i] + 1};
}
}
// cout << min_len << ", " << to[2];
return answer;
}
4. 경주로 건설 00:43
단순한 BFS 문제였다.
int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1}, op[] = {2, 3, 0, 1};
int solution(vector<vector<int>> b) {
int n = sz(b);
vector<vvi> dist(n, vvi(n, vi(4, 1e9)));
queue<array<int, 3>> q;
if(!b[0][1]){
dist[0][1][1] = 100;
q.push({0, 1, 1});
}
if(!b[1][0]){
dist[1][0][2] = 100;
q.push({1, 0, 2});
}
while(sz(q)){
auto[y,x,cur_d] = q.front();
q.pop();
for(int d = 0; d < 4 ; d++){
int w = d == cur_d ? 100 : 600;
int ny = y + dy[d], nx = x + dx[d];
if(ny >= 0 && ny < n && nx >= 0 && nx < n && !b[ny][nx]){
if(dist[ny][nx][d] > dist[y][x][cur_d] + w){
dist[ny][nx][d] = dist[y][x][cur_d] + w;
q.push({ny,nx,d});
}
}
}
}
return mine(dist[n-1][n-1]);
}
5. 동굴 탐험 01:44
문제의 특징을 잘못파악해서 한참 돌아갔던 문제이다.
대충 생각난건 dfs 순서대로 정점들을 매기고 라인스위핑을 하는건줄 알았는데 따져보니 그거랑 아무런 관련이 없는 문제였다.(오일러 투어 테크닉이 코테에 나올리가…)
뭐지이게 하고 그냥 먼저 방문해야되는거와 늦게 방문해야되는걸 구분하고 대충 BFS를 돌렸는데, BFS를 짜다보니
먼저 방문해야하는 곳을 방문한뒤에 늦게 방문해야되는 곳이 방문될 수 있었는데 못방문되었다면 늦게 방문해야되는 곳을 큐에 넣어주면 된다는게 보여서 풀 수 있었다.
사실 이러한 BFS 유형은 저번에 유사코문제를 풀때 본거같은데 알아차리기 어려웠다.
코딩테스트문제를 풀어본적이 거의 없어서 느낌이 안오는건지 원…
bool solution(int n, vvi ee, vvi order) {
vvi edges(n);
vi in(n);
int dfsn = 0;
vi A(n, -1), B(n, -1);
for (auto &pp: ee) edges[pp[0]].pb(pp[1]), edges[pp[1]].pb(pp[0]);
for (auto &pp: order) {
int a = pp[0], b = pp[1];
A[a] = b;
B[b] = a;
}
if (~B[0]) return false;
queue<int> q;
q.push(0);
vi vis(n), vis2(n);
vis[0] = 1;
while (sz(q)) {
int cur = q.front();
q.pop();
vis[cur] = 1;
if (~A[cur]) {
B[A[cur]] = -1;
if (vis2[A[cur]]) {
B[A[cur]] = -1;
q.push(A[cur]);
vis[A[cur]] = 1;
}
A[cur] = -1;
}
for (int to: edges[cur]) {
if (!vis[to]) {
if (~B[to]) {
vis2[to] = 1;
continue;
}
vis[to] = 1;
q.push(to);
}
}
}
return acc(vis) == n;
}
뭔가 4번까지 빨리풀어서 1시간내에 푸는것을 도전해보고 싶었지만 어림도없는 시도였다.
재밌는 문제였다.
Comments