|
*점프 슈트(while문)
K칸을 앞으로 점프 > 건전지 사용.
현재까지 온 거리 X 2 > 순간이동 건전지 사용 안함.
이동 거리 N 까지 건전지 사용 최솟값 구하기.
#include <iostream>
using namespace std;
int solution(int n)
{
int ans = 0;
while(n > 0)
{
if(n % 2 == 0)
n = n / 2;
else
{
n -= 1;
ans++;
}
}
return ans;
}
=====================================================
*다음 큰 숫자 (while문)
자연수 n, 다음 큰 숫자 구하기.
2진수로 변환했을때 1의 갯수가 같은 수중에 최솟값.
#include <iostream>
#include <vector>
using namespace std;
int resultCount(int n)
{
vector v;
while(n > 0)
{
v.push_back(n % 2);
n /= 2;
}
int count = 0;
vector::iterator iter;
for(iter = v.begin(); iter != v.end(); ++iter)
{
if(*iter == 1)
count++;
}
return count;
}
int solution(int n) {
int answer = 0;
int i = 0;
int k = 0;
i = resultCount(n);
while(true)
{
n++;
k = resultCount(n);
if(i == k)
break;
}
return n;
}
다른 방식
#include <iostream>
using namespace std;
int resultCount(int n)
{
int count = 0;
while(n > 0)
{
count += n % 2;
n /= 2;
}
return count;
}
int solution(int n) {
int answer = 0;
int i = 0;
int k = 0;
i = resultCount(n);
while(true)
{
n++;
k = resultCount(n);
if(i == k)
break;
}
return n;
}
=====================================================
*문자열중에 같은 문자 확인(string)
대소문자 구분 없음.
'p', 'y' 의 개수가 같으면 true, 다르면 false 리턴.
#include <iostream>
#include <string>
using namespace std;
bool solution(string s)
{
bool answer = true;
int a = 0, b = 0;
for(int i = 0; i < s.length(); i++)
{
string str = s.substr(i, 1);
if(str == "p" || str == "P")
a++;
else if(str == "y" || str == "Y")
b++;
}
if(a == b)
answer = true;
else
answer = false;
return answer;
}
=====================================================
*약수 더하기.(for문)
n의 약수를 모두 더한값 리턴.
#include <iostream>
using namespace std;
int solution(int n) {
int answer = 0;
for(int i = 1; i <= n; i++)
{
if(n % i == 0)
answer += i;
}
return answer;
}
=====================================================
*직사각형 별 찍기.(for문)
가로 n 세로 m 의 직사각형 별 찍기.
#include <iostream>
#include <string>
using namespace std;
int main(void)
{
int n;
int m;
cin >> n >> m;
string s;
for(int i = 0; i < n; i++)
{
s += "*";
}
for(int j = 0; j < m; j++)
{
cout<< s << "\n";
}
return 0;
}
=====================================================
*완주하지 못한 선수(해시,정렬)
참여 선수 배열 participant, 완주 선수 배열 completion.
완주하지 못한 선수 이름 리턴.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
string solution(vector participant, vector completion)
{
string answer = "";
sort(participant.begin(), participant.end());
sort(completion.begin(), completion.end());
for(int i = 0; i < participant.size(); i++)
{
if(participant[i] != completion[i])
{
answer = participant[i];
break;
}
}
return answer;
}
=====================================================
*전화번호 목록(해시,정렬)
전화번호를 담은 배열 phone_book의 어떤 번호가
다른 번호의 접두어인 경우가 있으면 false를 아니면 true를 리턴
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool solution(vector phone_book)
{
bool answer = true;
sort(phone_book.begin(), phone_book.end());
string temp = phone_book[0];
for(int i = 1; i < phone_book.size(); i++)
{
if(phone_book[i].find(temp) != string::npos)
{
answer = false;
break;
}
}
return answer;
}
=====================================================
*위장(해시맵)
clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
같은 이름을 가진 의상은 존재하지 않습니다.
스파이는 하루에 최소 한 개의 의상은 입습니다.
[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int solution(vector<vector> clothes) {
int answer = 0;
map<string, int> tmap;
for(auto elem : clothes)
{
string key = elem.second;
if(tmap.end() != tmap.find(key))
{
tmap[key]++;
}
else
{
tmap.insert(make_pair(key, 1));
}
}
answer = 1;
for(auto elem : tmap)
{
int value = elem.second;
answer *= value + 1;
}
answer -= 1;
return answer;
}
=====================================================
*베스트앨범
=====================================================
*탑(스택)
수평 직선에 탑 N대를 세웠습니다.
발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다.
또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다.
#include <iostream>
#include <vector>
using namespace std;
vector solution(vector heights) {
vector answer;
answer.push_back(0);
for(int i = 1; i < heights.size(); i++)
{
for(int j = i - 1; j >= 0; j--)
{
if(heights[j] > heights[i])
{
answer.push_back(j + 1);
break;
}
else if(j == 0)
{
answer.push_back(0);
}
}
}
return answer;
}
=====================================================
*소수의 합(기타)
2부터 N까지의 모든 소수의 합을 구하기.
#include <iostream>
using namespace std;
long long solution(int N) {
long long answer = 0;
vector nums;
nums.assign(N + 1, 1); // N + 1 만큼의 배열 개수를 1의 값으로 채운다.
for(int i = 2; i <= N; i++)
{
if(nums[i] != 0)
{
for(int j = i * 2; j <= N; j += i)
nums[j] = 0;
}
}
for(int i = 2; i <= N; i++)
{
if(nums[i] != 0)
answer += i;
}
return answer;
}
=====================================================
*k번째 수(정렬)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector solution(vector array, vector<vector> commands) {
vector answer;
for(auto elem : commands)
{
vector temp;
for(int i = elem[0] - 1; i < elem[1]; i++)
{
temp.push_back(array[i]);
}
sort(temp.begin(), temp.end(), less());
answer.push_back(temp[elem[2] - 1]);
}
return answer;
}
=====================================================
*2016년
a월 b일 요일 구하기.
16년 1월 1일은 금요일. 윤년(2.29)
#include <iostream>
using namespace std;
string solution(int a, int b) {
string answer = "";
vector day = {"THU","FRI","SAT","SUN","MON","TUE","WED"};
vector month = {31,29,31,30,31,30,31,31,30,31,30,31};
int count = 0;
for(int i = 0; i < a - 1; i++)
{
count += month[i];
}
count += b;
answer = day[count % 7];
return answer;
}
=====================================================
*가운데 글자 가져오기(string)
#include <iostream>
#include <string>
using namespace std;
string solution(string s) {
string answer = "";
int len = s.length();
int center = (len + (len % 2)) / 2;
int pos = 2 - (len % 2);
answer = s.substr(center - 1, pos);
return answer;
}
=====================================================
*같은 숫자는 싫어
배열에 연속적으로 나타나는 숫자 하나만 남기고 제거.
#include <iostream>
#include <vector>
using namespace std;
vector solution(vector arr)
{
vector answer;
int temp = arr[0];
answer.push_back(temp);
for(int i : arr)
{
if(i != temp)
{
answer.push_back(i);
temp = i;
}
}
return answer;
}
=====================================================
*문자열 내맘대로 정렬하기(string)
문자열 리스트 strings와 정수 n이 주어짐.
문자열의 n번째 인덱스 비교. 오름차순 정렬.
단 문자열 n번째가 같으면 전체 문자열 비교.
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int pos;
bool compareStr(string a, string b)
{
if(a[pos] == b[pos])
{
return a < b;
}
return a[pos] < b[pos];
}
vector solution(vector strings, int n) {
vector answer;
pos = n;
sort(strings.begin(), strings.end(), compareStr);
return strings;
}
=====================================================
*문자열 다루기 기본
#include <iostream>
#include <algorithm>
using namespace std;
bool solution(string s)
{
for ( char c : s )
{
if ( isdigit(c) == false )
return false;
}
if ( s.length() != 4 && s.length() != 6 )
return false;
}
=====================================================
*소수 찾기
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환
#include <iostream>
#include <vector>
using namespace std;
int solution(int n) {
int answer = 0;
vector nums = {0,0};
for(int i = 2; i <= n; i++)
{
nums.push_back(1);
}
for(int i = 2; i <= n; i++)
{
if(nums[i] == 1)
{
for(int j = i * 2; j <= n; j += i)
{
nums[j] = 0;
}
}
}
for(int b : nums)
{
answer += b;
}
return answer;
}
=====================================================
*수박수박수?
n의 값에 따른 "수박수박수.." 출력.
#include <iostream>
#include <string>
using namespace std;
string solution(int n) {
string answer = "";
for(int i = 0; i < n; i++)
{
if(i % 2 == 0)
answer.append("수");
else
answer.append("박");
}
return answer;
}
=====================================================
*문자열을 정수로 바꾸기(음수도 stoi 됨;)
#include <iostream>
#include <string>
using namespace std;
int solution(string s) {
int answer = 0;
answer = stoi(s);
return answer;
}
=====================================================
*약수의 합
#include <iostream>
using namespace std;
int solution(int n) {
int answer = 0;
/**case1*/ O(n)
for(int i = 1; i <= n; i++)
{
if(n % i == 0)
answer += i;
}
/**case2*/ O(logn)
for(int i = 1; i * i <= n; i++)
{
if(n % i == 0)
answer = answer + i + n/i;
if(i * i == n)
answer = answer - i;
}
return answer;
}
=====================================================
* 시저암호(string)
각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꿈.
Z - A, z - a 로 바뀜. 공백은 공백.
#include <iostream>
#include <string>
using namespace std;
string solution(string s, int n) {
string answer = "";
int pos;
for(int i = 0; i < s.size(); i++)
{
if(s[i] == ' ')
answer += ' ';
else
{
pos = (s[i] >= 'a') ? 'a' : 'A';
answer += pos + (s[i] - pos + n) % 26;
}
}
return answer;
}
=====================================================
*예산(정렬)
신청한 금액 배열, 예산이 있음.
예산으로 물품 구매 가능한 부서 최대값.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int solution(vector d, int budget) {
int answer = 0;
sort(d.begin(), d.end());
for(int i : d)
{
budget -= i;
if(budget < 0)
break;
answer++;
}
return answer;
}
=====================================================
*이상한 문자 만들기
공백을 기준으로 짝수는 대문자 홀수는 소문자 변환하기.
0번째 인덱스는 짝수로 처리.
#include <iostream>
#include <string>
using namespace std;
string solution(string s) {
string answer = "";
int count = 0;
for(int i = 0; i < s.size(); i++)
{
if(s[i] == ' ')
{
count = 0;
}
else
{
if(count % 2 == 0)
s[i] = toupper(s[i]);
else
s[i] = tolower(s[i]);
count++;
}
}
return s;
}
=====================================================
*프린터(스택/큐)
중요도 대기목록, location 위치의 문서가 몇번째로 인쇄되는지.
인쇄 대기목록의 젤 처음을 꺼냄.
대기목록에서 중요도가 가장 높으면 인쇄. 아니면 젤뒤로 넣음.
#include <iostream>
#include <deque>
#include <pair>
using namespace std;
int solution(vector priorities, int location) {
int answer = 0;
deque<pair<int, bool>> que;
for(int i = 0; i < priorities.size(); i++)
{
bool b = false;
if(i == location)
b = true;
que.push_back(make_pair(priorities[i], b));
}
int count = 0;
while (!que.empty())
{
int pivot = que[0].first;
bool b = que[0].second;
int i;
for (i = 0; i < que.size(); i++)
{
if (que[i].first > pivot)
{
que.push_back(que[0]);
que.pop_front();
break;
}
}
if (i == que.size()) // 중요도 높은게 없다.
{
count++;
que.pop_front();
if (b)
return count;
}
}
}
=====================================================
*가장 큰 수(정렬 & 문자열)
주어진 배열의 값들로 최대값 만들기.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool compareNum(int a, int b)
{
string s1 = to_string(a);
string s2 = to_string(b);
return s1 + s2 > s2 + s1;
}
string solution(vector numbers) {
string answer = "";
sort(numbers.begin(), numbers.end(), compareNum);
for(auto elem : numbers)
{
answer += to_string(elem);
}
if(answer[0] == '0')
answer = '0';
return answer;
}
=====================================================
*H-Index(정렬)
논문 n편 중, h번 이상 인용된 논문이 h편 이상 나머지 논문이 h번 이하 인용되었다면 h = H-Index.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int solution(vector citations) {
int answer = 0;
sort(citations.begin(), citations.end(), greater());
int p = 0;
while(true)
{
if(p >= citations[p])
break;
p++;
}
return answer = p;
}
=====================================================
*체육복(탐욕법 Greedy)
전체 학생의 수 n, 체육복을 도난당한 학생 lost[], 여분 학생 reserve[]
reserve[] +1, -1 번호 학생에게 빌려줄수 있음.
수업을 들을 수 있는 학생의 최대값
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int solution(int n, vector lost, vector reserve) {
int answer = 0;
vector in;
in.assign(n + 2, 1);
for(int i = 0; i < lost.size(); i++)
{
in[lost[i]]--;
}
for(int i = 0; i < reserve.size(); i++)
{
in[reserve[i]]++;
}
for(int i = 1; i <= n; i++)
{
if(in[i] == 1 || in[i] == 2)
answer++;
else
{
if(in[i - 1] > 1)
{
in[i]++;
in[i - 1]--;
answer++;
continue;
}
if(in[i + 1] > 1)
{
in[i]++;
in[i + 1]--;
answer++;
continue;
}
}
}
return answer;
}
=====================================================
*정수 제곱근 판별
임의의 정수 n에 대해 어떤 정수 x의 제곱인지 아닌지 판단.
n이 x의 제곱이면 x+1의 제곱 리턴. 아니면 -1 리턴.
#include <iostream>
using namespace std;
long long solution(long long n) {
long long answer = 0;
double d = sqrt(n);
int i = sqrt(n);
if(d - i == 0)
answer = pow(i + 1, 2);
else
answer = -1;
return answer;
}
=====================================================
*제일 작은 수 제거하기.
가장 작은 수를 제거. 빈 배열이면 -1을 채워 리턴.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector solution(vector arr) {
vector answer;
vector::iterator iter;
iter = min_element(arr.begin(), arr.end());
arr.erase(iter);
if(arr.size() == 0)
arr.push_back(-1);
answer = arr;
return answer;
}
=====================================================
*평균 구하기.
정수를 담고 있는 배열 arr의 평균값을 리턴.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
double solution(vector arr) {
double answer = accumulate(arr.begin(), arr.end(), 0);
return answer / arr.size();
}
=====================================================
*스킬트리
선행 스킬 순서를 지켜야 하고 배운 순서가 뒤바뀌면 사용 불가능.
이전 스킬을 배워야 이후 스킬을 배움. 안배우면 사용 불가능.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int solution(string skill, vector skill_trees) {
int answer = 0;
vector learned;
for (int i = 0; i < skill_trees.size(); i++)
{
string tree = skill_trees[i];
string s;
for (int j = 0; j < tree.size(); j++)
{
for (int k = 0; k < skill.size(); k++)
{
if (tree[j] == skill[k])
{
s += tree[j];
}
}
}
learned.push_back(s);
}
for(int i = 0; i < learned.size(); i++)
{
string s = learned[i];
bool flag = false;
for(int j = 0; j < s.size(); j++)
{
if(s[j] == skill[j])
flag = true;
else
{
flag = false;
break;
}
}
if(flag == true || s.size() == 0)
answer++;
}
return answer;
}
|
cs |
|
|
::public/코딩테스트 풀이