SCPC와 일정이 완전히 겹치는 바람에 준비는 무슨 시험시간도 간신히 맞춰서 접속했다. 코딩테스트는 완전 파이썬쓰라는 문제만 나와서 조금 실망스럽지만, 서술형은 실제 서비스 시 고민해봐야할 문제들이 많았어서 공부할 건덕지라도 줘서 만족스럽다.
결과적으로 코테 탈락했다. 코딩에서 떨어질 수준은 아니라서 서술형 문제에서 많이 갈린 것 같다. 서술형 문제는 평소에도 많은 고민을 해봐야 풀 수 있는 수준이었다. 조금 반성하게 되네..
1. 멋쟁이 숫자
digit으로만 이루어진 문자열이 주어질 때, 길이가 3인 substring의 digit이 모두 같은 substring중 가장 큰 수를 구하는 문제다. 이런 substring이 없는 경우 -1을, 000인 경우는 0만 출력한다.
그냥 구현… 고민할게 없다.
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
os << pai.first << ' ' << pai.second;
return os;
}
template <typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
is >> pai.first >> pai.second;
return is;
}
#ifndef DEBUG
#define endl '\n'
#endif
#define all(x) (x).begin(), (x).end()
#define sz(v) ((int)(v).size())
#define INF (INT_MAX / 2)
#define MAX_N 5005
#define MOD 998'244'353
#define MOD2 1'000'000'009
int solution(string s) {
int answer = -1;
for (int i = 0; i < sz(s) - 2; ++i) {
if (s[i] == s[i + 1] && s[i + 1] == s[i + 2]) {
answer = max(answer, s[i] - '0');
}
}
if (answer == -1) {
return answer;
} else {
return answer * 100 + answer * 10 + answer;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}
2. 적당히 어려운 문제
문제들의 난이도가 주어질 때 난이도 상위 25%문제 중 가장 난이도가 낮은 문제를 출력하는 문제다. 만약 그런 문제가 없는 경우엔 -1을 출력해야한다.
역시 그냥 구현이다… 다만, 상위 25%가 없다는 말은, 만약 문제가 3개밖에 없는 경우 가장 난이도가 높은 문제를 선택해도 상위 33%이기 때문에 조건에 해당하는 문제가 없는 것이다. 따라서 4개 미만인 경우를 따로 처리해주어야한다.
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
os << pai.first << ' ' << pai.second;
return os;
}
template <typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
is >> pai.first >> pai.second;
return is;
}
#ifndef DEBUG
#define endl '\n'
#endif
#define all(x) (x).begin(), (x).end()
#define sz(v) ((int)(v).size())
#define INF (INT_MAX / 2)
#define MAX_N 260
#define MOD 998'244'353
#define MOD2 1'000'000'009
int solution(vector < int > levels) {
int top25 = sz(levels) / 4;
if (top25 == 0) return -1;
int answer = 0;
sort(all(levels));
return levels[sz(levels) - top25];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}
3. 던전 탐험
초기 체력과 각 던전당 요구체력, 소요체력이 주어진다. 탐험가능한 최대 던전수를 구하는 문제다.
던전이 8개밖에 안 되므로 완전탐색하면 된다.
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
os << pai.first << ' ' << pai.second;
return os;
}
template <typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
is >> pai.first >> pai.second;
return is;
}
#ifndef DEBUG
#define endl '\n'
#endif
#define all(x) (x).begin(), (x).end()
#define sz(v) ((int)(v).size())
#define INF (INT_MAX / 2)
#define MAX_N 10
#define MOD 998'244'353
#define MOD2 1'000'000'009
vector < vector < int >> dungeons;
bool picked[MAX_N];
int dfs(int remainHp) {
int ret = 0;
for (int i = 0; i < sz(dungeons); ++i) {
if (picked[i]) continue;
if (dungeons[i][0] > remainHp) continue;
picked[i] = true;
ret = max(ret, dfs(remainHp - dungeons[i][1]) + 1);
picked[i] = false;
}
return ret;
}
int solution(int k, vector < vector < int >> d) {
int answer = -1;
dungeons = d;
answer = dfs(k);
return answer;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}
4. 초대왕을 찾아라
초대 이벤트를 여는데, 초대 이벤트의 점수는 (직접 초대한 사람 수 * 10 + 직접 초대한 사람이 초대한 사람 수 * 3 + 직접 초대한 사람이 초대한 사람이 초대한 사람 수)로 주어진다. 이벤트 로그에 남은 (초대한 사람, 초대당해 가입한 사람) 리스트가 주어질 때 초대 점수가 가장 높은 3명을 출력하는 문제다.
아… dfs로 풀었는데, tc 하나가 끝까지 안 풀렸다. 일단, ID 범위가 2^64라 압축을 하거나 map을 써야했는데, 간단해보여서 map을 도입했다. 문제는 초대 점수가 가장 높은 사람들을 출력하는 순서를 처리해줘야하고, dfs 때문에 adj 설정 때문에 약간 애를 먹었다.
tc하나는 1시간정도 소요했음에도 불구하고 끝까지 해결 못 하고, 마무리했다. 풀이는 dfs가 맞는 것 같은데 참 아쉽다..
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
os << pai.first << ' ' << pai.second;
return os;
}
template <typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
is >> pai.first >> pai.second;
return is;
}
#ifndef DEBUG
#define endl '\n'
#endif
#define all(x) (x).begin(), (x).end()
#define sz(v) ((int)(v).size())
#define INF (INT_MAX / 2)
#define MAX_N 10
#define MOD 998'244'353
#define MOD2 1'000'000'009
struct Score {
vector <ll> scores {0,0,0};
};
unordered_map < ll, Score > inveteScore;
unordered_map < ll, vector < ll >> adj;
unordered_map < ll, int > lastInvite;
void dfs(int here) {
vector < ll > & scores = inveteScore[here].scores;
scores[0] = sz(adj[here]);
for (ll & nxt: adj[here]) {
if (!inveteScore.count(nxt)) {
dfs(nxt);
}
scores[1] += inveteScore[nxt].scores[0];
scores[2] += inveteScore[nxt].scores[1];
}
}
vector < ll > solution(vector < vector < ll >> invitationPairs) {
vector < ll > answer;
for (auto & pair: invitationPairs) {
adj[pair[0]].emplace_back(pair[1]);
}
vector < pll > temp;
set < ll > visited;
for (int i = 0; i < sz(invitationPairs); ++i) {
const auto & pair = invitationPairs[i];
lastInvite[pair[0]] = i;
if (visited.count(pair[0])) continue;
visited.emplace(pair[0]);
if (!inveteScore.count(pair[0])) dfs(pair[0]);
ll score = inveteScore[pair[0]].scores[0] * 10 + inveteScore[pair[0]].scores[1] * 3 + inveteScore[pair[0]].scores[2];
temp.emplace_back(score, pair[0]);
}
sort(all(temp), [](pll & a, pll & b) -> bool {
if (a.first == b.first) return lastInvite[a.second] < lastInvite[b.second];
return a.first > b.first;
});
for (int i = 0; i < 3 && i < sz(temp); ++i) {
cout << temp[i] << endl;
answer.emplace_back(temp[i].second);
}
return answer;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}
5. 작업 빨리 처리하기
진행해야할 작업들의 난이도가 1차원 배열로 주어진다. 작업은 반드시 같은 난이도를 갖는 작업끼리 동시에 처리해야하는데 2개 또는 3개만 동시에 처리할 수있다. 즉, 1개만 있으면 처리를 하지 못 한다. 최소 처리 횟수를 구하는 문제다.
간단…하다. 같은 난이도의 작업이 1개만 있으면 작업을 마칠 수 없으므로 반드시 -1, 2개면 1번에 가능, 3개면 1번에 가능, 4개면 2 2로 나누어서 해야하므로 2번에 가능, 5번도 3 2로 나누어서 해야하므로 2번에 가능, 6번도 3 3..
이런식으로 하다보면 3으로 나눈 몫 + (3으로 나누어 떨어지지 않는 경우 1 : 0)로 구할 수 있다.
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
os << pai.first << ' ' << pai.second;
return os;
}
template <typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
is >> pai.first >> pai.second;
return is;
}
#ifndef DEBUG
#define endl '\n'
#endif
#define all(x) (x).begin(), (x).end()
#define sz(v) ((int)(v).size())
#define INF (INT_MAX / 2)
#define MAX_N 10
#define MOD 998'244'353
#define MOD2 1'000'000'009
int solution(vector < int > tasks) {
int answer = 0;
unordered_map < int, int > taskCount;
for (auto task: tasks) {
taskCount[task]++;
}
for (const pii & p: taskCount) {
if (p.second == 1) {
answer = -1;
break;
}
answer += p.second / 3 + (p.second % 3 ? 1 : 0);
}
return answer;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}
6. 만보기 랭킹
3일동안 기록된 만보기의 기록이 주어진다. 만약 같은 날에 같은 사람의 기록이 중복되어서 들어올 경우, 가장 큰 기록이 기록된다. 3일 동안 걸은 걸음 수가 큰 순서대로 정렬해서 출력하는 문제다.
사람을 나누는 기준이 문자열이라는 점이 참… 짜증 나는 문제다. unordered_map을 사용해서 전부 관리해주고, 조건에 따라 처리를 해주면 된다.
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
os << pai.first << ' ' << pai.second;
return os;
}
template <typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
is >> pai.first >> pai.second;
return is;
}
#ifndef DEBUG
#define endl '\n'
#endif
#define all(x) (x).begin(), (x).end()
#define sz(v) ((int)(v).size())
#define INF (INT_MAX / 2)
#define MAX_N 10
#define MOD 998'244'353
#define MOD2 1'000'000'009
unordered_map < string, int > sum;
unordered_map < string, int > scores[3];
vector < string > solution(
vector < int > steps_one, vector < string > names_one,
vector < int > steps_two, vector < string > names_two,
vector < int > steps_three, vector < string > names_three
) {
for (int i = 0; i < sz(steps_one); ++i) {
scores[0][names_one[i]] = max(scores[0][names_one[i]], steps_one[i]);
}
for (int i = 0; i < sz(steps_one); ++i) {
sum[names_one[i]] += scores[0][names_one[i]];
}
for (int i = 0; i < sz(steps_two); ++i) {
scores[1][names_two[i]] = max(scores[1][names_two[i]], steps_two[i]);
}
for (int i = 0; i < sz(steps_two); ++i) {
sum[names_two[i]] += scores[1][names_two[i]];
}
for (int i = 0; i < sz(steps_three); ++i) {
scores[2][names_three[i]] = max(scores[2][names_three[i]], steps_three[i]);
}
for (int i = 0; i < sz(steps_three); ++i) {
sum[names_three[i]] += scores[2][names_three[i]];
}
vector < string > answer;
for (auto p: sum) {
answer.emplace_back(p.first);
}
sort(all(answer), [](string & a, string & b) -> bool {
if (sum[a] == sum[b]) return a < b;
return sum[a] > sum[b];
});
return answer;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}
7. 주식 쓸어담기
현재 갖고 있는 돈의 액수와 각 주식들의 가치와 현재가격이 주어질 때 최대한으로 확보할 수 있는 가치의 최대값을 구하는 문제다.
자명한 냅색DP다. 뭐.. 공간복잡도 최적화가 가능하긴 했는데 굳이…?
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <typename a, typename b>
ostream& operator<<(ostream& os, const pair<a, b>& pai) {
os << pai.first << ' ' << pai.second;
return os;
}
template <typename a, typename b>
istream& operator>>(istream& is, pair<a, b>& pai) {
is >> pai.first >> pai.second;
return is;
}
#ifndef DEBUG
#define endl '\n'
#endif
#define all(x) (x).begin(), (x).end()
#define sz(v) ((int)(v).size())
#define INF (INT_MAX / 2)
#define MAX_N 100005
#define MOD 998'244'353
#define MOD2 1'000'000'009
ll dp[MAX_N][105];
ll solution(int money, vector < vector < ll >> stocks) {
ll answer = 0;
dp[money][0] = 0;
if (money >= stocks[0][1]) {
dp[money - stocks[0][1]][0] = stocks[0][0];
answer = stocks[0][0];
}
for (int i = 1; i < sz(stocks); ++i) {
for (int j = 0; j <= money; ++j) {
dp[j][i] = dp[j][i - 1];
if (j + stocks[i][1] <= money) {
dp[j][i] = max(dp[j][i], dp[j + stocks[i][1]][i - 1] + stocks[i][0]);
}
answer = max(answer, dp[j][i]);
}
}
return answer;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}