신청 URL : https://career.programmers.co.kr/competitions/2627
코딩테스트 실전 대비 모의고사
career.programmers.co.kr
1번
접근법 :
빈콜라병 n개가 있을때 a개마다 b개를 줘서 몇개의 콜라까지 받아 마실수있는지 물어보는 문제입니다.
빈콜라병으로 콜라를 받아마시고 계속 마실수 있을 때까지 탐색하는 문제입니다.
바꿔먹지 못할때까지 콜라를 받아먹으면
되기때문에 코드만 보면 바로 이해하 실수있습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
#include<bits/stdc++.h>
using namespace std;
int solution(int a, int b, int n) {
int answer = 0;
int pet = 0;
while (true) {
int m = n / a; //바꿔 먹을 수 있는 콜라수
int mod = n % a; //바꿔 먹지 못해 남은 콜라병
if (m > 0) {
n = m * b + mod; //바꿔먹은후 남은 콜라병가 받아먹은 콜라병을 그대로 콜라병수를 셋팅
answer += m * b;//바꿔먹은 콜라
}
else
break;
}
return answer;
}
|
cs |
2번
접근법 :
결론만 말하자면 스택문제입니다. 문제 조건에서 아주 대놓고 스택쓰라고 나와있습니다.
아래에서 위로 쌓인다는 말 부터하면 이건 스택쓰라는 얘기겠죠?
햄버거재료가 1열로 나열되어있는데 1231을 꺼내서 또다시 1231을 만들어지면 또 햄버거를 만들수있는 문제입니다.
2,1,1,2,3,1,2,3,1 에서 -> 3번째 1231 을 빼가면 2,1,1,2,3,1이되고 다시 3번째에 1231이 존재하니 다시빼면 2,1,1 이되서
햄버거 2개를 만들수 있다는 얘기입니다.
즉 이런식으로 몇번 제거 하면 되는지 묻는문제이기때문에
순서대로 스택에 저장해서 뒤에서 1231이 있으면 1231을 몇번 제거했는지 묻는문제입니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
int solution(vector<int> ingredient) {
int answer = 0;
vector<int> st, hambuger = { 1,2,3,1 };//st는 스택이라고 생각
for (int t : ingredient) {
st.push_back(t);
if (st.size() >= 4) {
vector<int> temp(st.begin() + st.size() - 4, st.end());//뒤에서 부터 데이터 4개 저장
if (temp == hambuger) { //햄버거랑 같으면 제거
for (int i = 0; i < 4; i++)
st.pop_back();
answer++;
}
}
}
return answer;
}
|
cs |
3번
접근법 :
처음 천만개 배열 만들어서 누적합하듯이 풀어볼까? 생각했는데 답은 나오고 메모리낭비 + 조금 느릴것같아서
다른방법을 갈구했는데 생각해보면 모든 경비병들의 휴식시간에 통과한다면 반드시
distance 길이만큼 갈수있겠죠?
그리고 경비병들이 근무지가 아닌곳은 그냥 볼필요도없이
통과할수있으니 경비병들의 근무지만 확인하기로 합니다.
그렇다면 1초마다 1m씩 갈수있으니 해당 내가 병사의 첫근무지 xm까지 왔다면 x초왔다는 얘기이다.
그리고 경비병은 근무시간과 휴식시간이 계속 반복된다 즉
근무시간+휴식시간을 하나의 주기로 생각하고 x/(근무시간+휴식시간) 해서 나온 몫을 d라고 할때
근무시간과 휴식시간을 반복했다는 얘기입니다.
그리고 다시 d+1부터 근무를시작하고 d+근무시간까지 근무를 하고 그후엔 휴식시간이라는 점만 안다면
d+1 부터 해당근무 마지막까지 근무시간인지 휴식시간인지 파악한다면 되는문제입니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
int solution(int distance, vector<vector<int>> scope, vector<vector<int>> times) {
int answer = 0;
vector<tuple<int, int, int>> v;
for (int i = 0; i < scope.size(); i++) {
if (scope[i][0] > scope[i][1])swap(scope[i][0], scope[i][1]);//작은수를 뒤쪽으로
v.push_back({ scope[i][0],scope[i][1],i });
}
sort(v.begin(), v.end());//정렬
for (int i = 0; i < v.size(); i++) {
int s1, s2, idx, t1, t2, l;
tie(s1, s2, idx) = v[i];
tie(t1, t2) = { times[idx][0], times[idx][1] };//해당병사 근무시간, 휴식시간
l = t1 + t2; //l이 주기
int d = (s1 / l) * l;
int k = 0;
int idx2 = 0;
for (int j = d + 1; j <= s2; j++) {
k++;
if (s1 <= j && j <= s2 && idx2 == 0) {//해당 근무지에 근무시간에 걸려버리면 거기까지옴
return j;
}
if (times[idx][idx2] == k) {//휴식시간 혹은 근무시간까지 왔다면 매번 바꿔줌
idx2 = !idx2;
k = 0;
}
}
}
return distance;//운좋게 휴식시간 다통과함
}
|
cs |
4번
접근법 : 솔직히 개인적으로 어렵게 생각했던 문제입니다. 4번 문제
4시간정도 고민했네요.
아무리봐도 단순 dfs나 bfs로 안풀릴것같았고 2분그래프인가? 생각했는데 1번 테스트케이스를 보니
아니었다. 다르게 생각해보니 dp문제로 접근했는데 역시나 dp문제였다.
하나의 우선 내가 여기서 등불을 켰을때와 등불을 껐을때 한꺼번에 생각해야합니다.
등불은 껏을때는 반드시 다음이든 이전이든 등불은 켜져있어야하고
등불이 켜져있다면 반드시 이전이든 다음이든 꺼져있어도 되고 켜저있어도 상관없다
즉
dp[0][cur] +=dp[1][next] 의 모든수를 더해주고
dp[1][cur]+=min(dp[1][next],dp[0][next])가 성립한다
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> v;
vector<int> dp[2];
void dfs(int cur) {
dp[1][cur] = 1;//1번은 무조건 켜줌
for (int next : v[cur]) {
if (dp[1][next] == 0) {//방문까지도 한꺼번에 처리
dfs(next);
dp[0][cur] += dp[1][next];//반드시 켜저있는것을 가져감
dp[1][cur] += min(dp[0][next], dp[1][next]);//켜져있는곳은 켜져있든 꺼져있든 작게 등불을 켜진것을 가져감
}
}
}
int solution(int n, vector<vector<int>> lighthouse) {
int answer = 0;
v = vector<vector<int>>(n + 1);
dp[0] = dp[1] = vector<int>(n + 1);
for (vector<int>& l : lighthouse) {
v[l[0]].push_back(l[1]);
v[l[1]].push_back(l[0]);
}
dfs(1);
return min(dp[0][1], dp[1][1]);
}
|
cs |
후기:
난이도는 이전보다는 조금 올린것같지만 그렇게 어려운편은 아닙니다.
이번엔 제 스스로가 방심했습니다. 이번에도 쉽겠지 생각했고 졸면서 도서관에서 풀었는데 더우니까 더 졸렸는데
1,2,3번이 생각보다 늦게 풀리고 답이 자꾸 틀렸지만 풀리긴 풀리더군요
근데 4번문제 1시간 이상 고민해도 답이 안나왔습니다. 결국 제한시간 다끝나고 어떻게든 풀어보겠다고 끝가지 물고
늘어졌습니다. 이번엔 제한시간 내로 못풀었네요 ㅠ.ㅠ
그래도 3시간정도 더고민했고 솔직히 아예 못풀줄 알았는데 결국 풀렸네요
결국엔 풀리긴했지만 dp공부좀 해야할것같습니다.
역시 이전에 쉬웠다고 방심은 금물 반성하게되네요
궁금한점이나 조언 , 지적 어떤 질문이든 댓글은 언제나 환영입니다.
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 숫자 카드 나누기 (0) | 2022.12.19 |
|---|---|
| 프로그래머스 우박수열 정적분 (2) | 2022.12.19 |
| 프로그래머스 코딩테스트 실전 대비 모의고사 2차 문제집 22년 07월 27일 14:00 ~ 08월 23일 (5) | 2022.07.27 |
| 프로그래머스 코딩테스트 실전 대비 모의고사 1차 문제집 22년 07월 13일 10:00 ~ 08월 23일 (1) | 2022.07.21 |
| 프로그래머스 입양 시각 구하기(2) (0) | 2022.03.29 |
