https://school.programmers.co.kr/learn/challenges?order=recent&partIds=37527
코딩테스트 연습 | 프로그래머스 스쿨
개발자 취업의 필수 관문 코딩테스트를 철저하게 연습하고 대비할 수 있는 문제를 총망라! 프로그래머스에서 선발한 문제로 유형을 파악하고 실력을 업그레이드해 보세요!
school.programmers.co.kr
1. 개인정보 수집 유효 기간
문제 설명
개인 정보 n개가 주어진다. 약관 종류는 여러 가지가 있으며, 각 약관마다 개인정보 보관 유효기간이 정해져 있다. 각 개인 정보가 어떤 약관으로 수집됐는지 알 때, 유효 기간이 지난 개인 정보는 파기해야 한다.
모든 달은 28일까지 있다고 가정한다.
today: 오늘 날짜를 의미, "YYYY.MM.DD" 형태로 주어진다.
terms: 약관의 유효기간을 담은 1차원 문자열 배열, "약관 종류 유효기간" 의 형태로 주어진다.
privacies: 수집된 개 정보의 정보를 담은 1차원 문자열 배열, "날짜 약관 종류"의 형태로 주어진다.
해결
그동안 c++로 하는 문자열 문제는 까다로워서 외면해왔는데... 이렇게 마주하니 1번부터 멘탈이 털렸다.
문자열 관련 함수도 몰라 하나하나 parsing 하고 있다가 substr, stoi 등 함수를 알게 되었다.
또한 '모든 달은 28일까지 있다.' 이 조건을 신경 쓰지 않아 계속 삽질하였다...
문제를 풀 때는 개인 정보의 수집 일자 + 유효 기간이 현재 날짜보다 전이라면 answer 벡터에 넣어 주는 식으로 풀었다.
문자열 관련 함수들을 더 공부하면 더 깔끔하게 풀 수 있을 것 같다.
vector<int> parsing (string today)
- 문자열을 받아 연, 월, 일을 정수로 바꾸고, 벡터에 넣어 리턴한다.
int parsing2(string terms)
- 유효 기간을 정수로 바꾸어 리턴한다.
vector<int> solution(string today, vector<string> terms, vector<string> privacies):
- 오늘 날짜, 개인 정보 수집 날짜, 유효 기간을 정수형으로 바꾸어 연산할 수 있게 한다.
- 날짜의 대소 비교를 할 때는 한달이 28일이라는 정보를 사용한다.
- 연 * 28 * 12 + 월 * 28 + 일 * 28
코드
#include <string>
#include <iostream>
#include <vector>
using namespace std;
vector<int> parsing(string today) {
int year = (today[0] - '0') * 1000 +(today[1] - '0') * 100 + (today[2] - '0') * 10 + (today[3] - '0');
int month = (today[5] - '0') * 10 + (today[6] - '0');
int day = (today[8] - '0') * 10 + (today[9] - '0');
vector<int> v = {year, month, day};
return v;
}
int parsing2(string terms) {
int res2 = stoi(terms.substr(2));
return res2;
}
vector<int> solution(string today, vector<string> terms, vector<string> privacies) {
vector<int> answer;
vector<int> v = parsing(today);
int TODAY = v[0] * 336 + v[1] * 28 + v[2];
for (int i = 0; i < privacies.size(); i++) {
vector<int> p = parsing(privacies[i]); // 날짜
char type = privacies[i][11]; // 약관 종류
for (int j = 0; j < terms.size(); j++) {
if (type == terms[j][0]) {
int res = parsing2(terms[j]);
int limit = p[0] * 336 + p[1] * 28 + p[2];
limit += res * 28;
if (limit <= TODAY) answer.push_back(i + 1);
}
}
}
return answer;
}
2. 택배 배달과 수거하기
문제 설명
일렬로 나열된 n개의 집에 택배를 배달한다. 배달할 물건은 모두 크기가 같은 택배 상자에 담아 배달하며, 배달을 다니면서 빈 택배 상자들을 수거한다. 트럭에는 택배 상자를 최대 cap개 실을 수 있다. 각 집마다 배달할 택배 상자의 개수와 수거할 빈 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구한다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있다.
cap: 트럭에 실을 수 있는 상자의 최대 개수
n: 배달할 집의 개수
deliveries: 배달할 택배 상자의 개수를 담은 1차원 정수 배열
pickups: 수거할 택배 상자의 개수를 담은 1차원 정수 배열
해결
처음 문제를 읽었을 때는 그리디하다? 라는 생각이 들었다. 제일 먼 곳에서부터 택배를 배달하고, 수거하면 될 것 같다.
이를 위해 스택을 사용하였다.
del 스택: 배달할 집을 순서대로 저장
pick 스택: 수거할 집을 순서대로 저장
이렇게 저장하면 스택의 제일 위엔 제일 먼 곳의 위치가 담겨 있다.
두 스택의 top 위치를 비교하며 더 먼 곳의 위치 * 2 를 answer에 더해 주었다.
한번 돌 때마다 cap만큼 택배 상자를 옮기도록 하였다.
여기서 '각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있다.' 라는 조건을 고려해야 한다.
각 집의 택배 상자를 한번에 옮겨야 하는 줄 알았는데... 하나씩도 옮길 수 있다.
이 과정에서 모든 택배 상자를 옮긴 집을 pop해 주며 스택의 원소들을 하나씩 지워 준다.
스택에 아무것도 담겨 있지 않다면 모든 집을 방문하여 수행해 준 것이다.
코드
#include <string>
#include <vector>
#include <stack>
#include <utility>
#include <iostream>
#define x first
#define y second
using namespace std;
long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
long long answer = 0;
stack<int> del, pick;
for (int i = 0; i < n; i++) {
if (deliveries[i]) del.push(i);
if (pickups[i]) pick.push(i);
}
int cnt = 0;
while (del.size() || pick.size()) {
if (!del.size() && pick.size()) answer += (pick.top() + 1) * 2;
else if (del.size() && !pick.size()) answer += (del.top() + 1) * 2;
else if (del.top() < pick.top()) answer += (pick.top() + 1) * 2;
else answer += (del.top() + 1) * 2;
int f1 = cap, f2 = cap;
while (del.size() && f1 - deliveries[del.top()] >= 0) {
f1 -= deliveries[del.top()]; deliveries[del.top()] = 0; del.pop();
}
if (del.size())
deliveries[del.top()] -= f1;
while (pick.size() && f2 - pickups[pick.top()] >= 0) {
f2 -= pickups[pick.top()]; pickups[pick.top()] = 0; pick.pop();
}
if (pick.size())
pickups[pick.top()] -= f2;
}
return answer;
}
3. 이모티콘 할인행사
문제 설명
카카오톡에서 이모티콘을 무제한으로 사용할 수 있는 이모티콘 플러스 서비스 가입자 수를 늘리려고 한다.
이를 위해 이모티콘 할인 행사를 하는데, 목표는 다음과 같다.
1. 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
2. 이모티콘 판매액을 최대한 늘리는 것.
1번 목표가 우선이며, 2번 목표는 그 다음이다.
- n명의 카카오톡 사용자들에게 이모티콘 m개를 할인하여 판매한다.
- 이모티콘마다 할인율은 다를 수 있으며, 10%, 20%, 30%, 40% 중 하나로 설정된다.
- 각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매한다.
- 각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입한다.
n: 카카오톡 사용자
users: n명의 구매 기준을 담은 2차원 정수 배열
emoticons: 이모티콘 m개가 정가를 담은 1차원 정수 배열
해결
문제를 딱 처음 보고 '어떻게 풀어야 되지?' 하는 생각이 딱 들었다.
일단 10%, 20%, 30%, 40% 모두를 모든 이모티콘에 적용해야 한다는 생각을 했다.
모두 적용하고 best의 상황을 찾아야 한다.
이때 백준의 n과 m문제가 딱 생각났고, dfs로 풀어 보았다.
깊이가 emoticon의 개수와 같으면 종료하는 dfs이다.
emoticon의 개수만큼 들어갔다면 할인율을 계산해서 다 더해 준다.
다 더했을 때, 사용자들의 기준에 따라 이모티콘을 모두 구매할지, 이모티콘 플러스 서비스에 가입할지 결정한다.
그 후 (이모티콘 플러스 서비스 유저, 이모티콘 매출액) 을 리턴하여 이모티콘 플러스 서비스 유저가 제일 많은 답을 구한다.
코드
#include <string>
#include <vector>
#include <iostream>
#include <utility>
#define x first
#define y second
using namespace std
int sale[7];
pair<int, int> dfs(int cnt, vector<int> emoticons, vector<vector<int>> users) {
if (cnt == emoticons.size()) {
pair res = {0, 0}; // 이모티콘 플러스 유저, 이모티콘 매출액
for (int i = 0; i < users.size(); i++) {
int sum = 0;
for (int j = 0; j < emoticons.size(); j++) {
if (users[i][0] <= sale[j]) sum += emoticons[j] * (100 - sale[j]) / 100;
}
if (users[i][1] <= sum) res.x++;
else res.y += sum;
}
return res;
}
pair<int, int> res = {0, 0};
for (auto i : {10, 20, 30, 40}) {
sale[cnt] = i;
pair<int, int> tmp = dfs(cnt + 1, emoticons, users);
if (res.x < tmp.x) res = tmp;
else if (res.x == tmp.x && res.y < tmp.y) res = tmp;
}
return res;
}
vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
vector<int> answer;
pair<int, int> res = dfs(0, emoticons, users);
answer.push_back(res.x);
answer.push_back(res.y);
return answer;
}6. 미로 탈출 명령어
문제 설명
nxm 격자 미로가 있다. (x, y)에서 출발해 (r, c)로 이동해서 탈출해야 한다.
1. 격자의 바깥으로는 나갈 수 없다.
2. (x, y)에서 (r, c)까지 이동하는 거리가 총 k여야 한다. 이때 (x, y)와 (r, c)를 포함해, 같은 격자를 두 번 이상 방문해도 된다.
3. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 한다.
이동경로는 다음과 같이 문자열오 바꿀 수 있다.
- l: 왼쪽으로 한 칸 이동
- r: 오른쪽으로 한 칸 이동
- u: 위쪽으로 한 칸 이동
- d: 아래쪽으로 한 칸 이동
위 조건대로 탈출할 수 없는 경우는 "impossible"을 리턴한다.
해결
문제의 입출력을 보자마자 bfs라는 것을 깨달았다.
제일 좋아하는 유형이기 때문에 제일 처음으로 풀었다.
queue에 현재 좌표와 string을 넣어서 bfs를 돌려 주었다.
1. 사전순인 아래쪽, 왼쪽, 오른쪽, 위쪽 (d, l, r, u) 순으로 돎
2. 같은 격자를 방문할 수 있으므로 이동 거리를 포함한 3차원 visited 배열을 사용
3. 한번 이동할 때마다 string에 추가하여 queue에 추가
코드
#include <string>
#include <vector>
#include <queue>
#include <utility>
#include <iostream>
#define x first
#define y second
using namespace std;
// n, m : 격자 크기
// x, y: 출발 위치
// r, c: 탈출 지점
// k: 이동해야 하는 거리
int dx[4] = {1, 0, 0, -1}, dy[4] = {0, -1, 1, 0};
int visited[51][51][2501];
int range_over(int nx, int ny, int n, int m){
return nx <= 0 || ny <= 0 || nx > n || ny > m;
}
char mapping(int i){
if (i == 0) return 'd';
if (i == 1) return 'l';
if (i == 2) return 'r';
if (i == 3) return 'u';
}
string solution(int n, int m, int x, int y, int r, int c, int k) {
string answer = "z";
queue<pair<pair<int, int>, string>> q;
q.push({{x, y}, ""});
while (!q.empty()) {
auto cur = q.front(); q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = dx[dir] + cur.x.x, ny = dy[dir] + cur.x.y;
if (range_over(nx, ny, n, m) || visited[nx][ny][k - (cur.y + mapping(dir)).length()]) continue;
if (nx == r && ny == c && cur.y.length() + 1 == k) {
if (answer > cur.y + mapping(dir)) answer = cur.y + mapping(dir);
}
visited[nx][ny][k - (cur.y + mapping(dir)).length()] = 1;
if (cur.y.length() >= k) continue;
q.push({{nx, ny}, cur.y + mapping(dir)});
}
}
if (answer == "z") return "impossible";
return answer;
}
리뷰
처음 하는 것치고 7개 중에 4개... 반타작 한 것으로 만족했다.
다만 c++을 하면서 골치아파 멀리했던 문자열 문제들... 다시 봐야 할 필요가 있다는 것을 깨달았다...
또한 평소에 그리디, bfs만 열심히 풀어서 진짜 그리디, bfs만 손쉽게 풀 수 있었다. 다른 유형들도 열심히 해 봐야겠다고 다짐했다...
더 연습하다 보면 코테의 답답한 코딩 환경, 고정된 변수들. 에 적응 할 수 있을 것 같다.
나머지 못 푼 3 문제들은 다음 포스팅에서 다룰 예정이다.