코딩코딩

#include <string>
#include <vector>
#include <cctype>
using namespace std;

string solution(string s) {
    string answer = "";
    for(int i=0; i<s.size(); i++){
        if(s[i]>='A' && s[i]<='Z'){
            s[i]= s[i]-'A'+'a';
        }
    }
    for(int i=1; i<s.size(); i++){
        if(s[0]>='a'&& s[0]<='z'){
            s[0] = s[0]-'a'+'A';
        }
        if(isspace(s[i]) && (s[i+1] >='a' && s[i+1]<='z')){
            s[i+1]  = s[i+1]-'a'+'A';
            i++;
        }
        
    }
    return s;
}

#include <iostream>
#include<vector>
#include <algorithm>

using namespace std;

int solution(vector<int> A, vector<int> B)
{
    int answer = 0;

    sort(A.begin(),A.end());
    sort(B.begin(),B.end(),greater<int>());
    for(int i=0; i<A.size(); i++){
        answer+=  A[i]*B[i];
    }

    return answer;
}

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    unordered_map<string, int> m;
    string tmp ="";
    for(int i=0; i<phone_book.size(); i++){
        tmp = "";
        for(int j=0; j<phone_book[i].size(); j++){
            tmp += phone_book[i][j];
            m[tmp]++;
        }
    }
    for(int i=0; i<phone_book.size(); i++){
        if(m[phone_book[i]]>1) return false;
    }
    return answer;
}

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    int sum = 0;
    for(int i=1; i<=n; i++){
        sum = 0;
        for(int j=i; j<=n; j++){
            sum += j;
            if(sum == n) {
                answer++;
                break;
            }
            else if(sum>n){
                break; 
            }
        }
    }
    return answer;
}

DP 사용 

#include <string>
#include <vector>

using namespace std;
int d[100001];

int solution(int n) {
    int answer = 0;
    d[0] = 0;
    d[1] = 1;
    for(int i=2; i<=n; i++){
        d[i] = (d[i-1]+d[i-2])%1234567;
    }
    answer = d[n];
    return answer;
}

- 초기에  next_permutation으로 모든 요소 값 비교해서 넣으려했더니 시간초과로 아주 펑펑 터졌다 아오 ㅋㅋ 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
bool compare(string s1, string s2){
    if(s1+s2 > s2+s1) return true;
    return false; 
}
string solution(vector<int> numbers) {
    string answer = "";
    vector<string> vec;
    for(int i=0; i<numbers.size(); i++){
        vec.push_back(to_string(numbers[i]));
    }
    sort(vec.begin(),vec.end(),compare);
    for(int i=0; i<vec.size(); i++){
        answer+=vec[i];
    }
    if(answer[0]=='0') answer = "0";
    return answer;
}

정렬을 몇번이나 한건지,,, 조합 사용.. 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool prime(int num){
    if(num <= 1) return false;
    for(int i=2; i*i<=num; i++){
        if(num%i == 0) return false;
    }
    return true;
}

int solution(string numbers) {
    int answer = 0;
    vector<char> number;
    vector<int> vec; 
    for(int i=0; i<numbers.size(); i++){
        number.push_back(numbers[i]);
    }
    sort(number.begin(),number.end());
    
    do{
        string tmp ="";
        for(int i=0; i<number.size(); i++){
            tmp += number[i];
            vec.push_back(stoi(tmp));
        }    
    }while(next_permutation(number.begin(),number.end()));
    
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    for(int i=0; i<vec.size(); i++){
        if(prime(vec[i]))  answer++;
    }
    return answer;
    
}

DFS사용

#include <string>
#include <vector>

using namespace std;
int result;
void DFS(vector<int> numbers, int target, int L, int sum){
    if(L == numbers.size()){
        if(sum == target){
            result++;
            return;
        }
    }
    else{
         DFS(numbers,target,L+1,sum+numbers[L]);
         DFS(numbers,target,L+1,sum-numbers[L]);
    }
}
int solution(vector<int> numbers, int target) {
    DFS(numbers, target ,0,0);
    return result;
}

BFS 사용 

#include<vector>
#include<queue>
#include <iostream>
using namespace std;
int dist[101][101];
int dx[4] ={0,1,0,-1};
int dy[4] ={1,0,-1,0};

int solution(vector<vector<int> > maps)
{
    int answer = -1;
    queue<pair<int,int> > que;
    que.push({0,0});
    dist[0][0] =1;
    cout<<maps.size()<<"\n";
    cout<<maps[0].size()<<"\n";
    while(!que.empty()){
        int x = que.front().first;
        int y = que.front().second;
        que.pop();
        
        if(x == maps.size()-1 && y == maps[0].size()-1){
            return dist[x][y];
        }
        
        for(int i=0; i<4; i++){
            int nx = x +dx[i];
            int ny = y +dy[i];
            if(nx<0 || nx>=maps.size() || ny<0 || ny>=maps[0].size()) continue;
            if(dist[nx][ny]!=0 || maps[nx][ny] ==0) continue;
            que.push({nx,ny});
            dist[nx][ny] = dist[x][y]+1;
        }
        
    }
    
    return answer;
}

그리디 문제  정렬하여  최소무게 + 최대무게 <= 한계 값  인지 체크 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(),people.end());
    int st = 0;
    int ed = people.size()-1;
    while(st<=ed){
        if(people[st]+people[ed]<=limit){
            st++;
            ed--;
            answer++;
        }
        else{
            ed--;
            answer++;
        }
    }
    return answer;
}

단순히 예전에 푼 백준의 숨바꼭질 시리즈 문제와 유사한 줄 알고 BFS 로 삽질을 했다 ㅠ

순간이동 같은 경우  무조건 이동거리의 *2 로 이동가능이라   시작할 때 무조건 k 만큼 점프를 해야한다.

점프를 하는 경우 그 수 만큼 전력 소모가 심함 -> 순간이동을 우선으로 사용해야함 

=> 즉 n에서 부터 순간이동을 할때 ( /2)  나누어 떨어지지 않는 경우에만(=홀수)  1 만큼 빼서 짝수를 만들어준다

짝수를 만들어주는 (=1을 빼는) 횟수가 즉 최소 전력의 소모 량이다.      

#include <iostream>
using namespace std;

int solution(int n)
{
    int ans = 0;
    
    while(n>0){
        if(n%2 != 0){
            ans++;
            n--;
        }
        n/=2;
    }
    return ans;
}

혹시나 하는 마음에 while +. for문 조합으로 돌리니 역시나 실패,, 

연달아 나오는 문자가 같으면 빼면 되는것이기 때문에 stack을 활용했다  흔히 접하는 괄호?문제와 유사한거 같음 

#include <iostream>
#include<string>
#include <stack>
using namespace std;

int solution(string s)
{
    int answer = 0;
    stack<char> st;
    for(int i=0; i<s.size(); i++){
        if(st.empty() || st.top() != s[i]) st.push(s[i]);
        else st.pop();
    }
    if(st.empty()) answer = 1;
    return answer;
}

크게 두 가지로 나눴다 

1.  해당 문자열이 올바른지 체크 - stack 사용

2. 문자열을 한 칸씩 이동 - deque 사용

2번 이동시키는걸 초기 0번 이동 부분을 넘기고 1번 이동시켰을 때 부터의 개수를 세어 주기 때문에

마지막에 초기 s가 올바른지 체크하는 과정을 추가함 ! 

#include <string>
#include <vector>
#include <deque>
#include <stack>

using namespace std;

bool checkStack(string str){
    stack<char> st;
    for(int i=0; i<str.size(); i++){
        if(st.empty()) st.push(str[i]);
        else if(st.top() =='(' && str[i] ==')') st.pop();
        else if(st.top()=='[' && str[i] == ']') st.pop();
        else if(st.top()=='{' && str[i]=='}') st.pop();
        else st.push(str[i]);
    }
    
    if(st.empty()) return true;
    else return false; 
}

int solution(string s) {
    int answer = 0;
    deque<char> dq;
    for(int i=0; i<s.size(); i++){
        dq.push_back(s[i]);
    }
    
    
    for(int i=0; i<s.size()-1; i++){
        string tmp="";
        dq.push_back(dq.front());
        dq.pop_front();
        for(int j=0; j<dq.size(); j++){
            tmp += dq[j];
        }
        if(checkStack(tmp)) answer++;
    }
    if(checkStack(s)) answer++;
    return answer;
}

어쩌다 보니 오늘 모두 스택관련 문제네  마지막은 귀여운 스택문제로 마무리 

#include<string>
#include <iostream>
#include <stack>
using namespace std;

bool solution(string s)
{
    bool answer = true;
    stack<char> st;
    for(int i=0; i<s.size(); i++){
        if(st.empty()) st.push(s[i]);
        else if(s[i]==')' && st.top()=='(')st.pop();
        else st.push(s[i]);
    }
    
    if(!st.empty()) answer = false;

    return answer;
}

level2 부터 진짜 너무어렵네 아오 ㅋㅋㅋ 머리가 안돌아가요 ㅠ

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> solution(vector<vector<int>> arr1, vector<vector<int>> arr2) {
    vector<vector<int>> answer;
    for(int i=0; i<arr1.size(); i++){
        vector<int> vec;
        for(int j=0; j<arr2[0].size(); j++){
            int sum = 0;
            for(int k=0; k<arr1[0].size(); k++){
                sum += arr1[i][k]*arr2[k][j];
            }
            vec.push_back(sum);
        }
        answer.push_back(vec);
    }
    return answer;
}

이제 거의 남은 문제들이 끝판왕스타일이라... 조낸 하기싫다....아오.....ㄱ- ㅋㅋ .... 

#include <string>
#include <vector>
using namespace std;

int countOne(int num){
    int cnt = 0;
    while(num>0){
        if(num%2 == 1) cnt++;
        num /=2;
    }
    return cnt;
}

int solution(int n) {
    int answer = 0;
    int num = countOne(n);
    int idx = n;
    while(1){
        if(num == countOne(++idx)){
            answer=idx;
            return answer;       
        }
    }
}

DP 사용 

초기 접근 : 단순히 for문을 활용하여 모든 행의 최댓값을 저장 / 최댓값의 열 위치를 저장하여 그걸 기준으로 중복해서 나오지 않도록 설계함   =>  오류가 존재함... ( 최댓값으로 만 뽑아도 합이 최대가 안되는 경우가 발생  => 즉 , 모든 상황을 체크해줘야한다) 

그 전 단계와 열 위치가 같으면 안되기 때문에  모든 경우의 수 중에 가장 큰 값을 더해주며 최대로 땅을 먹을 수 있는

최댓값을 출력해준다. 

#include <iostream>
#include <vector>
using namespace std;

int solution(vector<vector<int> > land)
{
    int answer = 0;

    for(int i=1; i<land.size(); i++){
        land[i][0] += max(max(land[i-1][1],land[i-1][2]),land[i-1][3]);
        land[i][1] += max(max(land[i-1][0],land[i-1][2]),land[i-1][3]);
        land[i][2] += max(max(land[i-1][1],land[i-1][0]),land[i-1][3]);
        land[i][3] += max(max(land[i-1][1],land[i-1][2]),land[i-1][0]);
    }
    for(int i= 0; i<4; i++){
        answer = max(answer, land[land.size()-1][i]);
    }
    return answer;
}

큐 + 우선순위 큐 사용

인덱스와 중요도를 큐에 넣어주고, 우선순위 큐에  프린트 중요도를 넣어준다. 

while문을 돌면서 우선순위와 비교하며 큐 내의 프린트물 순서를 바꿔준다.  우선순위가 아닌 경우  조건 처럼 맨 뒤로 갈 수 있도록 pop한 요소를 다시 큐에 넣어주며 회전 시킨다. 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    queue<pair<int,int> >que;
    priority_queue<int> pq;
    for(int i=0; i<priorities.size(); i++){
        que.push({i,priorities[i]});
        pq.push(priorities[i]);
    }
    while(!que.empty()){
        int pos = que.front().first;
        int p = que.front().second;
        que.pop();
        if(pq.top()== p){
            pq.pop();
            answer++;
            if(pos == location) return answer; 
        }
        else{
            que.push({pos,p});
        }
    }
}

포인트는 for문을 돌고 나서 마지막 요소를 넣어 줘야함... 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cctype>
using namespace std;

string solution(string s) {
    string answer = "";
    string tmp ="";
    vector<int> vec;
    for(int i=0; i<s.size(); i++){
        if(isspace(s[i])){
            vec.push_back(stoi(tmp));
            tmp.clear();
        }
        else{
            tmp+=s[i];
        }
    }
    vec.push_back(stoi(tmp));
    sort(vec.begin(),vec.end());
    answer = to_string(vec.front())+" "+to_string(vec.back());
    return answer;
}

최소 힙을 사용하여 문제를 풀었다.

 힙의 사이즈가 1이상이고, 힙의 top 값이 (최솟값) K의 값 보다 작으면 계속 반복해서 돌 수 있도록.. 

아무리 음식의 스코빌 지수를 섞어도 K미만으로 나오는 상황에 대한 예외처리를 안해줘서 실패가 떴었다. 

문제좀 제대로 천천히..읽자... 어디에 쫓기는거 아니잖아요..ㅠ ㅋㅋㅋㅋ

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int,vector<int>, greater<int>> pq;
    for(int i=0; i<scoville.size(); i++){
        pq.push(scoville[i]);
    }
    
    while(pq.size()>1 && pq.top()<K){
        int x = pq.top();
        pq.pop();
        int y = pq.top();
        pq.pop();
        int num = x + y*2;
        pq.push(num);
        answer ++;        
    }
    if(pq.top()<K) return -1;
    else return answer;
}

완전탐색 문제

노란색에 갈색 테투리로 둘러 싸인 형태이기 때문에 최소 세로 길이는 3부터다

갈색과 노란색을 더한 합을 높이로 나누면 가로의 길이가 나오는데   

주어지는 노란색의 개수는  가로-2* 세로-2 이다.  노란색 주위를 갈색이 둘러싸고 있는 형태이기 때문에 -2를 해줌

while문을 돌며  노란색+갈색 의 합이 세로의 길이로 나누어 떨어지고, 계산한 노란색의 개수와 주어진 노란색의 개수가 같을 때 까지 모든 경우의 수를 탐색한다. 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int sum = brown+yellow;
    int y = 3;
    while(1){
        if(sum%y == 0){
            int x = sum/y;
            if((x-2)*(y-2) == yellow){
                answer.push_back(x);
                answer.push_back(y);
                break;
            }
        }
        y++;
    }
    return answer;
}

어제 쉬었기 때문에 오늘은 4문제.. 풀었다

접근법은 주식 가격이 하락하지 않은 날짜 (=횟수)를 세어주면 된다.

즉 2중 for문을 돌며 해당 값이 앞서 확인하는 값 보다 큰 경우 ( = 즉 떨어지는 구간이 있으면) 탐색을 멈춰준다. 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    for(int i=0; i<prices.size(); i++){
        int cnt =0;
        for(int j=i+1; j<prices.size(); j++){
            cnt++;
            if(prices[i]>prices[j]) break;        
        }
        answer.push_back(cnt);
    }
    return answer;
}

걍 공식 보고 함수만 만들면 된다... 

#include <string>
#include <vector>

using namespace std;

int GCD(int a, int b){         
    if(a == 0) return b;
    return GCD(b % a, a);
}
int LCM(int a, int b){         
    return a * b / GCD(a,b);
}
int solution(vector<int> arr) {
    int answer = 0;
    answer = arr[0];
    for(int i=1;i<arr.size();i++){
        answer = LCM(answer, arr[i]);
    }
    return answer;
}

처음엔 문제를 잘못읽고 인용되는 h를  citations내의 값으로 생각해서  계속 틀렸습니다 가 나왔다

2번째로 다시 재접근했지만 16번 테케 해결이 안되어서 보니  h가 0일때의 부분을 생각 안해줘서 또 틀렸다.

3번째 수정 할 때는 9번 테케가 또 오류가 떠서 걍 다시 지우고 처음부터 재 접근했더니  테케 [5,5,5,5,5] 일때 5가 안나오고 4가 나와서 또 틀렸다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

다시 코드 체크하니까 h를 0부터 보는데  배열내의 사이즈 -1 만큼만 봐서 문제였다 결국 for문 즉, h의 범위를 0~  citations.size()+1까지 로 수정하니 드디어 통과... 쉽지 않네 ^^,,,, 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int solution(vector<int> citations) {
    int answer = 0,cnt =0;
    sort(citations.begin(),citations.end());
    vector<int> vec;
    int len = citations.size();
    for(int i=0; i< citations.size()+1; i++){
        cnt = 0;
        
        for(int j=0; j<citations.size(); j++){
            if(i<=citations[j]) cnt++;
        }
        
        if(cnt>=i && len-cnt<=i){
            vec.push_back(i);
        }
    }
    sort(vec.begin(),vec.end());
    answer = vec.back();
    return answer;
}

while문을 돌며 매번  모든 요소에 speed를 더해준다.  그리고 큐 처럼 차례대로 요소가  100이상인 경우  개수를 세어주고, 해당 값을 빼준다.  100아닌 경우 count의 개수가 0이 나오기 때문에 개수가 1이상인 경우에만 answer 벡터에 넣어준다. 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    vector<pair<int,int>> vec;
    for(int i=0; i<speeds.size(); i++){
        vec.push_back({progresses[i],speeds[i]});
    }
    while(!vec.empty()){
        int count = 0;
        for(int i=0; i<vec.size(); i++){
            vec[i].first += vec[i].second;
        }
        while(vec.size()>0 && vec[0].first>=100){
            count++;
            vec.erase(vec.begin());
        }
        if(count>0) answer.push_back(count);
    }
    return answer;
}

각 라운드 마다 대진표는 해당 대진의 짝수 번호/2 값이다. 

즉,  a와 b가 만나기 위해서는  이러한 대진 번호가 같아야함 !!!!!

a,b가 짝수가 아니면 짝수로 만들어서 (해당번호+1)/2 로 새로운 대진 번호를 부여하고, 짝수면 해당번호/2 하여 번호를 새로 부여하고 라운드를 증가시킨다 ( = answer) 

a==b 즉, a,b 가 같은 라운드에 만나는 경우 탐색을 종료하고 값을 리턴하면 끝 

#include <iostream>

using namespace std;

int solution(int n, int a, int b)
{
    int answer = 0;
    while(a!=b){
        if(a%2!=0){
            a = (a+1)/2;
        }
        else a/=2;
        if(b%2 != 0){
            b = (b+1)/2;
        }
        else b/=2;
        answer++;
    }

    return answer;
}

접근방법

1. 그리디라 단순히 정렬하여 높은 순으로 number.size()-k 요소 만큼 뽑음  -> 당연히 실패 (순서가 변경되면 안되기 때문) 

2. 그리디 인데도 혹시나 하여 조합 방법 생각 -> 당연히 실패와 시간초과 ㅋㅋㅋㅋ 

3. 결국 서치 하다가 stack으로 하는 아이디어를 보아서 적용!!  -> st.top()을 pop하는 수가 k와 같다면 멈춤 

포인트 1. 매번 스택의 top과 비교를 해야함  그렇기 때문에 while  사용 ( -> 그렇지 않으면 예제 3번에서 7이 아닌 4로 시작하게 된다) 

           2. 마지막 12번 테스트 케이스를 통과하기 위해서는  스택의 사이즈가 number.size()-k 가 아닐때의 추가적인 예외처리가 필요

         (즉 7777777,2 와 같이 하나의 숫자로 이루어진 요소가 들어 올 때 값 비교가 안되어 삭제가 안되기 때문에 이 부분에 대한 예외처리가 필요함!!)   + 이 테스트케이스를 생각 못해서 많은...시간을.........    

#include <string>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

string solution(string number, int k) {
    string answer = "";
    int count = 0;
    stack<char> st;
    for(int i=0; i<number.size(); i++){
        while(!st.empty() && count!=k){
            if(st.top()<number[i]){
                st.pop();
                count++;
            }
            else break;
        }
        st.push(number[i]);
    }
    while(st.size() != number.size()-k) st.pop();
    while(!st.empty()){
        answer+=st.top();
        st.pop();
    }
    reverse(answer.begin(),answer.end());
    return answer;
}