https://programmers.co.kr/learn/courses/30/lessons/64062
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
아래의 카카오 테크 블로그에서도 해설을 볼 수 있다.
https://tech.kakao.com/2020/04/01/2019-internship-test/
2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설
“2019년 카카오 개발자 겨울 인턴십” 공개 채용을 위한 1차 코딩 테스트가 지난 2019년 11월 9일 오후 2시부터 6시까지 총 4시간에 걸쳐 진행되었습니다. ’19년 신입공채 1차 코딩 테스트 시에 7문제가 출제되고 5시간의 풀이 시간이 주어졌던 것과는 달리 이번 인턴 코딩 테스트는 5문제가 출제되고 4시간의 풀이 시간이 주어졌습니다. 인턴의 경우 신입 공채와는 달리 인턴 과정을 통해 추가 […]
tech.kakao.com
위의 해설을 참고해서 이분 탐색으로 효율성을 해결했다.
m번째 친구가 다리를 건널 수 있는지 확인할 때, m-1번째 친구까지는 건넜다고 가정한다.
그러면 각 stone에서 m-1을 빼준 후에(m-1번째까지 건넜으므로) 연속으로 0 이하인 부분이 k개가 나오면 m번째 친구는 다리를 건널 수 없으므로 m명보다 더 적은 수로 건널 수 있는지 다시 검사한다.
0하인 부분이 연속으로 k개만큼 나오지 않아서 다리를 건널 수 있다면 m명보다 더 많은 친구들이 건널 수 있는지 검사한다.
이 m번째를 mid값으로 놓고 이분 탐색을 진행하면 된다.
이분 탐색의 초기 최댓값은 stones 배열 각 원소들의 최댓값인 200,000,000 으로 놓는다.
|
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#include <string>
#include <vector>
#define MAX 200000000
using namespace std;
int maxval;
bool check(vector<int> stones, int k, int m) {
//m-1번째까지는 건넜다고 가정
int size = stones.size();
int cnt = 0;
for (int i = 0; i < size; i++) {
if ((stones[i] - (m - 1)) <= 0) {
cnt++;
if (cnt == k) return false; //0이하가 연속으로 k면 건널수 없다.
}
else {
//연속되지 않는다면 0으로 초기화
cnt = 0;
}
}
return true;
}
void binarySearch(vector<int> stones, int k, int left, int right) {
if (left > right) return;
int mid = (left + right) / 2;
bool res = check(stones, k, mid);
if (res) {
//mid번째 친구가 건널 수 있다면 최댓값과 비교
if (maxval < mid) maxval = mid;
//mid보다 더 큰 값이 가능한지 이분 탐색
binarySearch(stones, k, mid + 1, right);
}
else {
//mid번째 친구가 건널 수 없다면 mid보다 더 작은 값 범위 탐색
binarySearch(stones, k, left, mid - 1);
}
}
int solution(vector<int> stones, int k) {
int answer = 0;
maxval = 0;
binarySearch(stones, k, 1, MAX);
answer = maxval;
return answer;
}
Colored by Color Scripter
|
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 [2020카카오공채] 가사 검색 c++ (3) | 2020.05.06 |
|---|---|
| 2019 카카오 개발자 겨울 인턴십 호텔 방 배정 ( C++ ) (0) | 2020.04.11 |
| 2019 카카오 개발자 겨울 인턴십 불량 사용자 ( C++ ) (0) | 2020.04.09 |
| 2019 카카오 개발자 겨울 인턴십 튜플 ( C++ ) (3) | 2020.04.09 |
| 2019 카카오 개발자 겨울 인턴십 크레인 인형뽑기 게임 ( C++ ) (0) | 2020.04.08 |