1. 체육복
1) 문제
여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
제한사항
전체 학생의 수는 2명 이상 30명 이하입니다.
체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.입출력 예
n lost reserve return
5 [2, 4][1, 3, 5] 5
5 [2, 4][3] 4
3 [3][1] 2
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
#include <string> #include <vector> #include <algorithm> using namespace std; int solution(int n, vector<int> lost, vector<int> reserve) { vector<int> students (n+1, 1); for (auto& l : lost) students[l]--; for (auto& r : reserve) students[r]++; // 진행방향이 오른쪽 for (int i=1; i<n+1; i++) { if (students[i] == 0) { // 진행방향에 맞춰서 왼쪽에서 빌릴 수 있으면 먼저 빌리기 if (i != 1 && students[i-1] == 2) { students[i]++; students[i-1]--; } else if (i != n && students[i+1] == 2) { students[i]++; students[i+1]--; } } } return n - count(students.begin()+1, students.end(), 0); }
2. 단속 카메라
1) 문제
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.
제한사항
차량의 대수는 1대 이상 10,000대 이하입니다.
routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.입출력 예
routes return
[[-20,-15], [-14,-5], [-18,-13], [-5,-3]] 2
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
#include <string> #include <vector> #include <algorithm> using namespace std; bool cmp(const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; } int solution(vector<vector<int>> routes) { int answer = 0; //가장 빨리 떠나는 차부터 찍히도록 하자 sort(routes.begin(), routes.end(), cmp); // 가장 빨리 떠나는 차의 진출 지점에 카메라 설치 int before = routes[0][1]; answer++; for (int i=1; i<routes.size(); i++) { // 설치한 카메라로 이 차량을 찍을 수 있는지 확인 if (routes[i][0] <= before && before <= routes[i][1]) { continue; } else { //없으면 카메라 추가 answer++; before = routes[i][1]; } } return answer; }
3. 큰 수 만들기
1) 문제
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한사항
number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.입출력 예
number k return
"1924" 2 "94"
"1231234" 3 "3234"
"4177252841" 4 "775841"
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
#include <string> #include <vector> #include <stack> using namespace std; string solution(string number, int k) { vector<char> vec; // 앞의 숫자중 큰 것을 남기려고 노력 for (int i = 0; i<number.size(); i++) { while (vec.size() != 0) { if (vec.back() >= number[i]) break; if (k==0) break; vec.pop_back(); k--; } // 조건이 맞춰진 스택에 값 넣기 vec.push_back(number[i]); } // K개 제거하지 못한 경우 처리 while(k!=0) { vec.pop_back(); k--; } return string(vec.begin(), vec.end()); }
