23.09.09. 풀었던 문제들
Programmers PCCP 모의고사 #1 외톨이 알파벳, 5분
프로그래머스 짝지어 제거하기를 풀어봤다면 바로 이어져 나오는 중복 char를 쉽게 줄일 수 있다. stack을 쓰든, string의 뒤에 중복을 빼고 붙여넣든. 이 방법을 사용하면 중복을 제거할 수 있고, 그러면 map으로 count만 하면 된다. 간단한 손풀기 문제.
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <stack>
using namespace std;
string solution(string str) {
stack<char> stk;
for(char c : str){
if(!stk.empty() && stk.top() == c) continue;
stk.push(c);
}
map<char, int> m;
while(!stk.empty()){
m[stk.top()]++;
stk.pop();
}
string answer = "";
for(auto &[key, value] : m) {
if(value > 1) answer += key;
}
sort(answer.begin(), answer.end(), less<char>());
return answer == "" ? "N" : answer;
}
시간복잡도
string 중복 제거에 O(n), map에 넣는 데 O(n)이 걸린다.
Programmers PCCP 모의고사 #1 체육대회, 18분
처음에는 이걸 어떻게 시간 내에 풀지..? 하고 나중에 풀었었는데. 그냥 단순한 순열 문제다! 순열은 뭐.. 예전에 포스팅했었고 별로 어렵지 않게 DFS로 코드를 짤 수 있었다.
문제 조건은 10이므로 10!, 약 3백만으로 넉넉하게 풀 수 있다.
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// stat[i][j] : i번째 학생이 종목 j의 능력치
// vertex가
/*
DP vs graph vs BF
앞 단에서 최대값을 택한다고, 전체가 최대가 되는 게 아님. -> BF 써야 하긴 하는데.
worst 10^10
*/
// 일단 DFS
int answer = -1e9;
vector<vector<int>> stats;
vector<bool> isSelected; // isSelected[i] : i번째 학생을 골랐는지 여부
int student_num, event_num;
void DFS(int cur_d, int max_d, int result){
if(cur_d == max_d){
answer = max(answer, result);
return;
}
for(int i = 0; i<student_num; i++){
if(!isSelected[i]){
isSelected[i] = true;
DFS(cur_d + 1, max_d, result + stats[i][cur_d]);
isSelected[i] = false;
}
}
}
int solution(vector<vector<int>> input) {
stats = input;
student_num = input.size();
event_num = input[0].size();
isSelected.resize(student_num);
fill(isSelected.begin(), isSelected.end(), false);
DFS(0, event_num, 0);
return answer;
}
시간복잡도
10!의 순열이므로 O(10!), 약 3백만
후기
일단은 naive하게 되는 대로 DFS로 풀었는데, 바로 맞아서 다행이다. 역시 아무것도 안 하는 것보다는 BF로 부분점수라도 받는 마인드가 맞다.
Programmers PCCP 모의고사 #1 유전법칙, 31분
규칙 찾기 문제. 각 그룹은 무조건 1개의 parent와 4개의 child로 이루어져 있으므로 몇 번째 generation의 몇 번째 index인지만 찾으면 된다.
사실 진법 변환이랑 같은 류의 로직. 언제 끝내고 어떻게 처리할지만 잘 처리해 주면 된다. 나는 map에 vector를 넣어서 해결했다!
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;
// 4^15는 1억이 넘으므로 전부 다 계산하고 뽑는 것은 안 된다. 적당히 찾아야 한다.
// record[i] : i+1번째 generation에서 어떤 index를 가지는지
// ex) record[2] == 2 : 3번째 generation에서 index가 2
// 2번째 generation까지 계산함. 1번째 generation은 있기 때문.
vector<int> getRecords(int n, int p){
vector<int> records;
records.push_back((p-1) % 4);
while(n > 2){
int before = ceil(((double)p)/4);
records.push_back((before-1) % 4);
p = before;
n--;
}
reverse(records.begin(), records.end());
return records;
}
// n : 세대, p : 개체
// 윗세대가 어떤 것인지 찾아야 한다.
string process(int n, int p){
if(n == 1) return "Rr";
map<string, vector<string>> m;
m["RR"] = {"RR", "RR", "RR", "RR"};
m["Rr"] = {"RR", "Rr", "Rr", "rr"};
m["rr"] = {"rr", "rr", "rr", "rr"};
vector<int> records = getRecords(n, p);
string cur = "Rr";
for(int record : records){
//cout<<"cur : "<<cur<<", record : "<<record<<endl;
cur = m[cur][record];
}
//cout<<endl;
return cur;
}
vector<string> solution(vector<vector<int>> queries) {
vector<string> answer;
for(vector<int> query : queries){
answer.push_back(process(query[0], query[1]));
}
return answer;
}
시간복잡도
n이 15이므로, getRecords() 함수의 while loop는 15번 돈다. 그러니까 O(n). map에 접근하는 것은 map size가 3이므로 사실상 O(1)로 치고. 그러면 O(n)이다.
Programmers PCCP 모의고사 #1 운영체제, 38분
많이 봤던 simulation 문제. pq를 써서 주어진 대로 풀면 된다.
실수했던 점은, future와 wait 2개의 queue에 다른 우선순위를 적용시켜줘야 했는데, 같은 우선순위를 썼었다. future의 경우에는 빨리 오는 게 먼저 와야 하고, wait queue의 경우에는 점수가 낮은 것이 먼저 와야 했다.
이것 말고는 뭐.. 딱히 실수한 것이 없었고, 잘 구현했던 것 같다. 디버깅도 빨리 해서 다행이다.
#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
typedef long long ll;
struct info{
int point;
int income_time;
int running_time;
};
// 정렬 기준 : 1. 빨리 오는 것 2. 우선순위 높은 것
struct futurecmp{
bool operator()(info &a, info &b){
if(a.income_time == b.income_time) return a.point > b.point; // 우선순위 숫자 작은 게 top에
return a.income_time > b.income_time; // income time 빠른 게 top에
}
};
// 정렬 기준 : 1. 우선순위 높은 것 2. 빨리 오는 것
struct waitcmp{
bool operator()(info &a, info &b){
if(a.point == b.point) return a.income_time > b.income_time; // income time 빠른 게 top에
return a.point > b.point; // 우선순위 숫자 작은 게 top에
}
};
// 초기화 : 시작 시간이 t보다 작은 것들을 waits에 넣음
void pushIntoWaitsLessThanT(int t, priority_queue<info, vector<info>, waitcmp> &waits, priority_queue<info, vector<info>, futurecmp> &future){
while(1){
if(future.empty()) break;
if(future.top().income_time > t) break;
if(future.top().income_time <= t){
waits.push(future.top());
future.pop();
}
}
}
vector<long long> solution(vector<vector<int>> program) {
priority_queue<info, vector<info>, waitcmp> waits; // 실행 대기 중인 thread queue
priority_queue<info, vector<info>, futurecmp> future; // 미래에 thread queue
for(vector<int> p : program){
info i;
i.point = p[0];
i.income_time = p[1];
i.running_time = p[2];
future.push(i);
}
// 초기화
int time = 0;
pushIntoWaitsLessThanT(time, waits, future);
cout<<endl;
// answer[0] : 모든 프로그램 종료 시간, answer[i] : 점수가 i인 프로그램 대기시간 합
vector<long long> answer(11, 0);
while(1){
if(waits.empty()){
// 종료조건
if(future.empty()) break;
// future가 남아있으면 그것 넣음
waits.push(future.top());
time = future.top().income_time;
future.pop();
}
// waits 중 제일 높은 것 실행 중으로 변경
info cur = waits.top();
waits.pop();
// cout<<"현재 시간 : "<<time<<endl;
// cout<<"현재 실행 중 : "<<cur.point<<", "<<cur.income_time<<", "<<cur.running_time<<endl;
// 해당 thread의 대기시간 추가
int wait_time = time - cur.income_time;
answer[cur.point] += wait_time;
// cout<<"대기시간 : "<<wait_time<<endl;
time += cur.running_time;
// cout<<"끝난 시간 : "<<time<<endl;
pushIntoWaitsLessThanT(time, waits, future);
// cout<<endl;
}
answer[0] = time;
return answer;
}
시간복잡도
n이 10만이고, pq의 각 연산이 O(logn)이므로 O(nlogn)에 얼추 풀린다.
후기
디버깅이 빨리 끝나서 다행이다. 구조화를 잘 해놔서..
Programmers PCCP 모의고사 #2 실습용 로봇, 10분
손 푸는 문제. 2D 좌표에서 이동하는 방법만 알면 된다. 실수했던 건 direction-- 이후 modular 연산을 한 것. C++에서는 음수의 modular 연산을 하면 a = bq + r에서 r = a - bq로 연산한다. 이것 때문에 한 3분? 날린 듯. 그래도 빨리 찾아서 다행이다. 디버깅도 안 찍었고.
#include <string>
#include <vector>
using namespace std;
int direction = 0; // dx, dy의 index. R이면 +1, L이면 -1
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
vector<int> position = {0, 0};
void rotate(char command){
if(command == 'R'){
direction++;
if(direction == 4) direction = 0;
}
else if(command == 'L'){
direction--;
if(direction < 0) direction = 3;
}
}
void move(char command){
int d = direction;
if(command == 'B'){
d += 2;
d %= 4;
}
position[0] += dx[d];
position[1] += dy[d];
}
vector<int> solution(string command) {
for(char c : command){
if(c == 'R' || c == 'L'){
rotate(c);
}
else if(c == 'G' || c == 'B'){
move(c);
}
}
return position;
}
Programmers PCCP 모의고사 #2 신입사원 교육, 5분
문제를 딱 보면 greedy같다는 느낌이 든다. 증명해볼까?
점수가 a, b, c, ... 순서로 오름차순 정렬되어 있다고 할 때,
- a와 b를 합치는 경우 a+b, a+b, c, ...가 된다.
- a와 c를 합치는 경우 a+c, a+c, b, ...가 된다.
- 이 둘의 차이는 c-b인데, 이는 무조건 양수이다. 따라서 최소인 것을 고르지 않으면 sum이 최소가 되지 않는다는 것을 proof by contradiction으로 보일 수 있다.
그러면 min값 2개를 뽑으면 되는데, 이건 pq를 쓰면 쉽다.
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(vector<int> ability, int n) {
priority_queue<int, vector<int>, greater<int>> pq;
for(int a : ability) pq.push(a);
while(n--){
int first = pq.top(); pq.pop();
int second = pq.top(); pq.pop();
pq.push(first + second);
pq.push(first + second);
}
int answer = 0;
while(!pq.empty()){
answer += pq.top();
pq.pop();
}
return answer;
}
시간복잡도
ability는 백만, n은 1만. 한 번의 연산에 O(log(1백만))이고 이 연산을 O(n)번 하므로 O(1만 * log(1백만))이다. 여기서 log(1백만)이 20 정도로, O(20만)으로 처리할 수 있다.
Programmers PCCP 모의고사 #2 실습용 로봇, 18분 풀고 이후 40분, 총 58분
처음에는 간단한 시뮬레이션 문제인 줄 알고 풀었는데.. 생각보다 까다로운 문제였다.
중요한 건 예외가 하나 있었다는 건데, 만들고 나가는 사람 + 들어오는 사람이 있으면 무조건 만들고 나가는 사람이 먼저 나간다는 것이다. 때문에 이에 대한 예외 연산을 빼놓지 않고 풀었어야 했다. 다행인 건 예제에 이 edge case를 저격하는 예외가 있었다는 것. 덕분에 쉽게 풀었다.
#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int solution(vector<int> menu, vector<int> order, int k) {
int total_num = order.size();
queue<int> waits; // 대기자 목록. 들어오는 것은 index
int future_idx = 0; // 제일 근미래에 올 사람의 index
int time = 0;
int answer = -1;
while(1){
// 종료조건
if(time >= total_num * k) break;
// time보다 빨리 와서 그동안 줄을 선 손님들 waitQ에 추가
while(1){
if(future_idx < total_num && future_idx * k <= time){
waits.push(future_idx);
future_idx++;
}
else break;
}
// 만듬
if(!waits.empty()){
time += menu[order[waits.front()]];
}
// 만들 동안 와서 그동안 줄을 선 손님들 waitQ에 추가
while(1){
if(future_idx < total_num && future_idx * k <= time){
waits.push(future_idx);
future_idx++;
}
else break;
}
// 대기열 계산. 단, 만들고 나간 시간 == 들어온 시간이면 1을 빼 주어야 함.
int isDuplicated = (time%k == 0 ? 1 : 0);
answer = max(answer, (int)waits.size() - isDuplicated);
// 만들었다면, 빼고, 그렇지 않다면 타임트립.
if(!waits.empty()) waits.pop();
else{
time = future_idx * k;
}
}
return answer;
}
시간복잡도
menu length는 100, order length는 1만으로, time을 1씩 늘려가면서 계산해도 1백만 정도로 시간은 여유롭다.
후기
이 문제는 진짜 아슬아슬했다.
Programmers PCCP 모의고사 #2 보물 지도, 50분
Acmicpc 벽 부수고 이동하기를 풀어봤다면 매우 쉽게 접근할 수 있는 문제. 아이템의 사용 여부도 visited 배열에 넣음으로써 쉽게 풀 수 있다.
단.. 이 문제의 경우 (x, y) 좌표로 주어지는데, 이를 (r, c) 좌표로 변환해야 했다. 이것 때문에 시간을 많이 잡아먹었다.
처음에 hole 위치를 초기화 할 때 seg fault가 나는 것을 보고 엥? 싶었는데.. 이런... 역시 문제를 잘 읽어야 한다. 항상 인지하고 문제를 읽지만 이런 "당연히 이러겠지" 싶은 것에서 항상 뒤통수를 맞는 것 같다.
#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
int INF = 1e9;
int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};
struct info{
int r;
int c;
int used;
int dist;
};
int solution(int n, int m, vector<vector<int>> holes) {
vector<vector<int>> board(m, vector<int>(n, 0)); // 0 : 빈칸, 1 : 함정
// (m-1, 0)부터 (0, n-1)까지 가야 함.
for(vector<int> hole : holes){
int r = m - hole[1];
int c = hole[0]-1;
// cout<<r<<", "<<c<<endl;
board[r][c] = 1;
}
vector<vector<vector<int>>> visited(m, vector<vector<int>>(n, vector<int>(2, 0)));
// visited[r][c][u] : (r, c) 위치를 방문했는지 여부. u가 1이면 신발 쓴 것이고, 0 신발 안 쓴 것.
queue<info> q;
info i; i.r = m-1; i.c = 0; i.used=0; i.dist=0;
q.push(i);
visited[m-1][0][0] = true;
int answer = INF;
while(!q.empty()){
info cur = q.front(); q.pop();
// cout<<"현재위치 : "<<cur.r<<", "<<cur.c<<", 사용여부 : "<<cur.used<<", dist : "<<cur.dist<<endl;
// 종료조건
if(cur.r == 0 && cur.c == n-1) answer = min(answer, cur.dist);
// 안 쓰고 넘어가는 경우
for(int d = 0; d<4; d++){
int nr = cur.r + dr[d];
int nc = cur.c + dc[d];
if(0 <= nr && nr < m && 0 <= nc && nc < n && board[nr][nc] == 0 && !visited[nr][nc][cur.used]){
// 사용 여부는 이전 상태 유지
visited[nr][nc][cur.used] = true;
info next; next.r = nr; next.c = nc; next.used = cur.used; next.dist = cur.dist+1;
q.push(next);
}
}
// 쓰고 넘어가는 경우
if(cur.used == 1) continue;
for(int d = 0; d<4; d++){
int nr = cur.r + 2*dr[d];
int nc = cur.c + 2*dc[d];
if(0 <= nr && nr < m && 0 <= nc && nc < n && board[nr][nc] == 0 && !visited[nr][nc][1]){
visited[nr][nc][1] = true;
info next; next.r = nr; next.c = nc; next.used = 1; next.dist = cur.dist+1;
q.push(next);
}
}
}
return answer == INF ? -1 : answer;
}
시간복잡도
m, n이 각각 1000 총 vertex size는 mn이고, O(1백만)이고,
각 vertex당 아이템을 사용하지 않을 때 4개 방향 + 아이템을 사용할 때 4개 방향으로 8개의 edge가 있다.
BFS의 시간복잡도는 O(V+E)이므로 O(9mn), O(mn)이다.
후기
왜 문제를 (x, y)로 냈을 까... 그냥 푸는 사람들을 괴롭히기 위해서가 아닐까?
Leetcode 377. Combination Sum IV, 30분
첫 접근 : duplicated permutation
일단은 문제를 딱 보고... [순서를 신경쓰는 + 합이 k가 되게 만드는 조합]이라길래 중복순열 딱 생각나서 중복순열로 풀었따. 그러나 문제의 input은 nums.size()가 200이기 때문에... 절대 풀 수 없다. 중복순열의 시간복잡도는 O(n$^n$)이니까. DFS 스택이 너무 많이 터져서 MLE가 떴다.
class Solution {
public:
vector<vector<int>> answer;
vector<int> nums;
int target;
void duplicatePermutation(int cur_d, vector<int> result, int sum){
if(sum == target){
answer.push_back(result);
return;
}
for(int i = 0; i<nums.size(); i++){
if(nums[i] + sum > target) continue;
result.push_back(nums[i]);
duplicatePermutation(cur_d + 1, result, sum + nums[i]);
result.pop_back();
}
}
int combinationSum4(vector<int>& i_nums, int i_target) {
nums = i_nums;
target = i_target;
sort(nums.begin(), nums.end(), less<int>());
duplicatePermutation(0, {}, 0);
return answer.size();
}
};
/*
중복순열 문제 같은데. + 합이 k가 되는...
*/
두 번째 접근 : DP
다른 방법이 필요하다... DFS의 tree를 보면 sum이 같을 때, 같은 연산을 반복하는 중복이 꽤나 발생하는 것을 알 수 있다. 이를 줄이기 위해서는? memoization이다. memozation? DP다!
앞선 관측에서 중복되는 부분은 [남은 값]으로 판별했다. 그러면, dp[i]를, [남은 값이 i일 때 만들 수 있는 경우의 수]로 세우면 될 것이다! 이것만 만들면 일사천리다.
점화식은 다음과 같으며, 이를 코드로 나타내면 된다. dp[0] = 1이니까 top-down이 쉬울 것 같다!
- dp[0] = 1. (초기값)
- dp[i] = 모든 n에 대해 dp[i-n]의 합
// Runtime 3 ms Beats 50.37%
// Memory 6.7 MB Beats 20.91%
class Solution {
public:
vector<int> nums;
int INF = -1;
vector<int> dp;
int recurse(int remain){
if(dp[remain] != INF) return dp[remain];
int num_cases = 0;
for(int n : nums){
if(n > remain) break;
num_cases += recurse(remain - n);
}
dp[remain] = num_cases;
return dp[remain];
}
int combinationSum4(vector<int>& i_nums, int target) {
nums = i_nums;
dp.resize(target + 1, INF);
dp[0] = 1;
sort(nums.begin(), nums.end(), less<int>());
return recurse(target);
}
};
시간복잡도
nums.size()가 n, target이 t일 때, recurse()를 수행하기 위해서 O(n)이 걸리고, 모든 dp 배열을 채우기 위해서 O(t)가 필요하므로 O(nt)이다.
후기
dp 으악