문제1. K번째수 (난이도: Level 1)
문제는 다음과 같습니다.
제 코드는 다음과 같습니다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> solution(vector<int> array, vector<vector<int>> commands) {
vector<int> ans;
for(int i=0; i<commands.size(); i++){
vector<int> tmp;
for(int j=commands[i][0]-1; j<commands[i][1]; j++){
tmp.push_back(array[j]);
}
sort(tmp.begin(), tmp.end());
ans.push_back(tmp[commands[i][2]-1]);
}
return ans;
}많은 투표를 받은 풀이는 다음과 같습니다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> solution(vector<int> array, vector<vector<int>> commands) {
vector<int> answer;
vector<int> temp;
for(int i = 0; i < commands.size(); i++) {
temp = array;
sort(temp.begin() + commands[i][0] - 1, temp.begin() + commands[i][1]);
answer.push_back(temp[commands[i][0] + commands[i][2]-2]);
}
return answer;
}- 살펴볼 지점
✅temp = array로 반복문 이용 없이 바로 벡터 복사할 수 있음
✅ 벡터 정렬 수행 시, 벡터 범위 길이 지정할 수 있음
문제2. 가장 큰 수 (난이도: Level 2)
문제는 다음과 같습니다.
얼핏보면 너무 쉽지만 함정이 숨어있는 문제
두 번째 예시만 잘 보면 바로 알 수 있다!
그냥 내림차순으로 정렬을 해야 할 것 같지만,
"3", "30" 에서는 330 > 303 이므로, "3" 이 "30" 보다 크도록 정렬을 수행해줘야 합니다.
다른 경우에서는 그냥 내림차순으로 정렬을 진행해야하는데, 이 경우에 대해서는 따로 처리를 해줘야하나? 생각했었는데, 생각해보니 두 문자열을 더해서 이를 비교해주면 바로 끝나게 됩니다.
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool cmp(const string &a, const string &b){
return a + b > b + a;
}
string solution(vector<int> numbers) {
vector<string> v;
for(int i=0; i<numbers.size(); i++){
v.push_back(to_string(numbers[i]));
}
sort(v.begin(), v.end(), cmp);
string s = "";
for(int i=0; i<v.size(); i++) s += v[i];
if(s[0]=='0') return "0";
else return s;
}그리고 주의해야 할 점이
numbers의 원소는 0부터라는 점!
즉 "000000" 과 같은 문자열이 저장이 되면 -> 숫자로 되면 0이 반환 되겠지만,
우리는 숫자의 범위가 매우 커서 이를 문자열로 바꿔서 계산해주었으므로
문자열의 맨 앞이 "0" 으로 시작하는 경우 -> (이후에도 계속 0이므로) 이를 "0" 으로 반환을 해주어야합니다.
많은 투표를 받은 풀이는 다음과 같습니다.
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
bool compare(const string &a, const string &b)
{
if (b + a < a + b)
return true;
return false;
}
string solution(vector<int> numbers) {
string answer = "";
vector<string> strings;
for (int i : numbers)
strings.push_back(to_string(i));
sort(strings.begin(), strings.end(), compare);
for (auto iter = strings.begin(); iter < strings.end(); ++iter)
answer += *iter;
if (answer[0] == '0')
answer = "0";
return answer;
}문제3. H-Index (난이도: Level 2)
문제는 다음과 같습니다.
솔직히 문제가 설명이 부족한 것 같습니다.
(문제풀다가 나 난독증이 있는 줄 😅)
질문하기에서 문제에 대해서 좀 찾아보다가 "함정에 빠지면 안되는거. h는 배열의 값중 하나가 아닙니다." 라는 말을 듣고 바로 다시 고쳐서 풀게 되었습니다.
중요한 건, h는 배열의 값 중 하나가 아니어도 된다는 것입니다!
즉 0부터 ~ 배열의 사이즈 중 가장 큰 값 이 사이 중 어느 하나의 값이 될 수 있다는 것입니다
먼저 제 풀이는 다음과 같습니다.
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int solution(vector<int> c) {
sort(c.begin(), c.end(), greater<int>()); // 내림차순 정렬
int ans = 0;
for(int i=c.size(); i>=0; i--){
for(int j=0; j<c.size(); j++){
if(c[j] >= i && j+1 >=i){
ans = i; break;
}
}
if(ans) break;
}
return ans;
}많은 투표를 받은 풀이는 다음과 같습니다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> citations) {
sort(citations.begin(), citations.end(), greater<int>());
for (int i = 0; i < citations.size(); ++i) {
if (citations[i] < i + 1) {
return i;
}
}
return citations.size();
}위 풀이도 참고해서 개선한 풀이는 다음과 같습니다.
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int solution(vector<int> c) {
sort(c.begin(), c.end(), greater<int>()); // 내림차순 정렬
int ans = 0;
for(int i=0; i<=c.size(); i++){ // max 값은 : c.size() -> 논문 수
if(i+1 >= c[i]) return i;
}
return ans;
}설명만 좀 더 친절했었다면 .. 좀 더 좋았을 텐데!
