📌문제
https://school.programmers.co.kr/learn/courses/30/lessons/1845
🎖️난이도
Level 1
✔️풀이
// 정답
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int solution(vector<int> nums)
{
int N = nums.size();
set<int> s(nums.begin(), nums.end());
return N / 2 > s.size() ? s.size() : N / 2;
}
// 오답 (시간초과) => 순열과 조합 다 구할 필요 X
#include <iostream>
#include <vector>
#include <set>
#include <algorithm> // next_permutation(순열), 조합
using namespace std;
int solution(vector<int> nums)
{
int N = nums.size();
int max_num = 0;
// 0, 1을 넣어 임시 조합(combination) 생성 => nCk
vector<int> tmpVec;
for (int i = 0; i<N / 2; i++) {
tmpVec.push_back(1); // k개만큼 1넣기
}
for (int j = 0; j<N / 2; j++) {
tmpVec.push_back(0); // n-k개만큼 0넣기
}
sort(tmpVec.begin(), tmpVec.end()); // 정렬
do {
set<int> s;
for (int i = 0; i < N; i++) { // N : tmpVec.size()
if (tmpVec[i] == 1) {
//cout << nums[i] << " ";
s.insert(nums[i]);
}
}
//cout << endl;
max_num = max(max_num, int(s.size()));
} while (next_permutation(tmpVec.begin(), tmpVec.end()));
return max_num;
}
🧠노트
-
🔍참고
-
'[ 알고리즘 ] > Implementation' 카테고리의 다른 글
[프로그래머스/C++] 숫자 문자열과 영단어 (0) | 2022.10.10 |
---|---|
[프로그래머스/C++] 소수 찾기 (0) | 2022.10.10 |
[프로그래머스/C++] 2016년 (0) | 2022.10.10 |
[프로그래머스] 교점에 별 만들기 (0) | 2022.10.07 |
[프로그래머스] 스킬트리 (0) | 2022.10.07 |