코딩코딩

- 1940번  주몽 

<풀이>

어제 푼 문제 복습 겸 투포인터 문제를 풀어보았다.. 어제 문제랑 접근 법이 아주 동일하다

필요한 수 값의 범위 때문에 for문을 돌릴경우 당연히 시간초과가 발생한다. 고로 투포인터로 접근하면 된다.

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int n,m;
vector<int> vec;

int main(void){
   cin>>n;
   cin>>m;
   for(int i=0; i<n; i++){
       int num;
       cin>>num;
       vec.push_back(num);
   }

   sort(vec.begin(),vec.end());
   int left = 0 , right = n-1, cnt =0;
   while(left<right){
       int sum = vec[left]+vec[right];
       if(sum == m) {
           cnt++;
           right--;
       }
       else if(sum>m){
           right--;
       }
       else left++;
   }
    
    cout<<cnt<<"\n";
}

- 1806번 부분합

<풀이>

투포인터 재밌네,, 이 문제 또한 투포인터 !!!! 

1. 시작 점 부터 더해주면서 해당 값에 도달or 넘었는지 확인

2. 넘었다면 도달한 거리를 갱신해주고 ->최단거리를 구하기 위해 시작점을 이동시켜주며 더해준 값을 빼줌

3. 합이 아직 부족하다면 배열의 길이를 늘려간다  / 이 때 배열에 끝에 도달했는데도 합을 충족시키지 못한다면 반복문을 나온다

4. 초기값에 따라 부분합을 구할 수 있는지 or 최단거리가 있는지 출력해준다.

문제 난이도는 골드인데 위에 푼 실버랑 크게 큰 차이는 없는 느낌..? 

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int n,m;
vector<int> vec;

int main(void){
   cin>>n>>m;
  
   for(int i=0; i<n; i++){
       int num;
       cin>>num;
       vec.push_back(num);
   }

   int st =0,end =0, sum=vec[0], ans = 214700000;
   while(st<=end){
       if(sum>=m){
           ans = min(ans, (end-st)+1);
           sum -= vec[st++];
       }
       else if(sum<m){
           if(end == n) break;
           sum +=vec[++end];
       }
   }

   if(ans ==214700000 ) cout<<0<<"\n";
   else cout<<ans<<"\n";
}

- 3273번 두 수의 합

<풀이>

처음엔 혹시나 하는 마음에 2중 for문을 썼지만, 당연히 시간초과가 떴다. 결국 투포인터로 접근 !

이중 탐색처럼 left , right를 나눠서 vector 에 저장된 값들을 두개씩 더해주면서 합을 비교해줬다. 

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int n,k;
vector<int> vec;
int main(void){
    cin>>n;
    for(int i=0; i<n; i++){
        int num;
        cin>>num;
        vec.push_back(num);
    }
    sort(vec.begin(),vec.end());
    cin>>k;
    
    int left= 0, right =n-1 ,cnt =0;
    while(left<right){
        int sum = vec[left]+vec[right];
        if(sum==k){
            cnt++;
            right--;
        }
        else if(sum>k) right--;
        else left++;
    }
    cout<<cnt<<"\n";
}

- 16431번 베시와 데이지

<풀이>

간단한 BFS문제였다. 베시 / 데이지 각각 함수를 두 개 구현하려다가.. 그냥 하나에 몰아서 매개변수로 베시/데이지 구별하여 탐색할 수 있도록 구현했다.. 쫌더 짧게 코딩하고 싶어서 그랬는데 오히려 더 지저분해진 기분..

문제 접근은 다음과 같다.

1. 주어진 베시의 시작점에서 존 까지의 이동 시간 기록 ( =  BFS)

2. 주어진 데이지의 시작점에서 존 까지의 이동시간 기록

3. 1,2에서 구한 시간을 비교해서 더 빠르게 도착한 사람의 이름을 출력해주면 된다. 

예전에 주구장창 풀었던 최단거리나,, 등등 문제 구현 코드가 다 가물가물해져서 큰일이다 ~ 

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <cstring>


using namespace std;

int dx[4] ={-1,0,1,0};
int dy[4] ={0,1,0,-1};
int ddx[8]={-1,-1,-1,0,1,1,1,0};
int ddy[8]={-1,0,1,1,1,0,-1,-1};

int ch[2001][2001];
int px,py;
int BFS(int x, int y, int num){
    queue<pair<int,int> > que;
    memset(ch,0,sizeof(ch));
    que.push(make_pair(x,y));
    ch[x][y] = 1;

    while(!que.empty()){
        int xx= que.front().first;
        int yy =que.front().second;
        que.pop();

        if(xx == px  && yy == py) return ch[xx][yy]-1;
        
        //Bessie
        if(num == 1){
            for(int i=0; i<8; i++){
                int nx = xx + ddx[i];
                int ny = yy + ddy[i];

                if(nx<1 || nx>1001 || ny<1 || ny>1001) continue;
                if(ch[nx][ny]) continue;
                que.push(make_pair(nx,ny));
                ch[nx][ny] = ch[xx][yy] + 1;
            }
        }
        //Daisy
        else if(num == 2){
            for(int i=0; i<4; i++){
                int nx = xx + dx[i];
                int ny = yy + dy[i];

                if(nx<1 || nx>1001 || ny<1 || ny>1001) continue;
                if(ch[nx][ny]) continue;
                que.push(make_pair(nx,ny));
                ch[nx][ny] = ch[xx][yy] + 1;
            }
        }

    }

    return 0;
}

int main(void){
    int ax,ay,bx,by;
    cin>>ax>>ay;
    cin>>bx>>by;
    cin>>px>>py;

    int bessie = BFS(ax,ay,1);
    int daisy = BFS(bx,by,2);
    if(bessie>daisy) cout<<"daisy"<<"\n";
    else if(bessie<daisy) cout<<"bessie"<<"\n";
    else cout<<"tie"<<"\n";

}

<양심없는 브론즈 문제 풀이>

- 10988번 팰린드롬인지 확인하기 

<풀이> 

팰린드롬 = 뒤집었을 때도 동일한 경우

1. 문자열 입력받음

2. 입력받은 문자열  reverse함수로 뒤집음

3. 1==2 이면 1출력 아니면 0 

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>



using namespace std;

int main(void){
    string st;
    cin>>st;
    string tmp = st;
    reverse(tmp.begin(),tmp.end());

    if(st == tmp) cout<<1<<"\n";
    else cout<<0<<"\n";
}

-2744번 대소문자 바꾸기

<풀이>

그냥 바꿔주면 됩니다...

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>

using namespace std;

int main(void){
    string st;
    cin>>st;
    string tmp="";
    for(int i=0; i<st.size(); i++){
        if(st[i]>='a' && st[i]<='z'){
            tmp+=st[i]-'a'+'A';
        }
        else tmp+= st[i]-'A'+'a';
    }
    cout<<tmp<<"\n";
}

-9933번 민균이의 비밀번호

<풀이>

자기자신부터 체크하라는 부분을 빼먹어서 한번 틀렸다 .... 

입력되는 단어 중에 비밀번호가 되려면 뒤집은 단어도 존재해야한다.

이 문제는 다음과 같이 접근했다.

1. 단어의 수 만큼 벡터에 일단 다 저장

2. 단어의 수 만큼 하나씩 뒤집어주고, 자기 자신부터 뒤집었을 때의 값과 동일한 경우 (=비밀번호) 바로 출력해주고 멈춤 

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int main(void){
    int n;
    cin>>n;
    vector<string> vec;
    for(int i=0; i<n; i++){
        string st;
        cin>>st;
        vec.push_back(st);
    }
  
    for(int i=0; i<vec.size(); i++){
        string tmp = vec[i];
        reverse(tmp.begin(),tmp.end());
        for(int j=0; j<vec.size(); j++){
            if(tmp == vec[j]) {
                cout<<tmp.size()<<" "<<tmp[tmp.size()/2]<<"\n";
                return 0;
            }
        }
    }
    
}

정말 오랜만에.. 백준을 다시 푼다....ㄱ- 

- 1189번 컴백홈

<풀이>

기억을 살릴 겸.. 백트래킹 문제를 풀어보았다. 주어진 조건대로 차분이 구현하면 되는 문제였다.

1. 왼쪽 아래에서 시작 

2. 오른쪽 위 목적지 (=집) 에 도달하는데, 길이가 K 이며 지난 곳을 다시 방문하지 않음 (= 체크 배열이 필요함)

3. 집에 갈 수 있는 모든 경우의 수를 찾아야함 = 백트래킹 

재귀함수를 호출할 때, 함수 종료 조건은 2번에 명시한 것과 같다. 

즉, (x,y) 상하좌우 이동하며 제일 오른쪽 상단에 도달 & 거기 까지 도달하는 길이가 K 이면 재귀함수를 종료하고 카운트를 해주면 된다.

알고리즘 실력 쌓기는 너무나 힘든데,, 쫌 쉬었다고 바로 리셋됐음..하 ^^... 쉽지않네 

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int dx[4] = {-1,0,1,0};
int dy[4] ={0,1,0,-1};
int ch[6][6];
string board[6];
int n,m,k;
int num; 

void DFS(int x, int y, int cnt){
    if(x == 0 && y == m-1 && cnt == k){
        num++;
        return;
    }
    else{
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
            if(board[nx][ny] == 'T' || ch[nx][ny]) continue;
            ch[nx][ny] = 1;
            DFS(nx,ny, cnt+1);
            ch[nx][ny] = 0;
            
        }
    }
}

int main(void){
    cin>>n>>m>>k;

    for(int i=0; i<n; i++){
        cin>>board[i];
    }
    
    ch[n-1][0] = 1;
    DFS(n-1,0,1);
    cout<<num<<"\n";
}

- 1316번 그룹 단어 체커

<풀이>

1. 입력된 문자열의 길이만큼 탐색하면서 알파벳 등장 횟수를 세어준다

2. 조건에 따르면 이미 나온 알파벳인데, 연속해서 나오지 않은경우 = 그룹단어 아님 

3. 2번 조건에 따라 그룹 단어 체커만 카운트 해준다. 

문제 자체는 어렵지 않고 .. 문자열 마다 초기화만 잘 해주면 된다..

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

int ap[30];
int n, ans;
bool check;
string str;

int main(void){
    cin>>n;
    
    while(n--){
        cin>>str;
        memset(ap,0,sizeof(ap));
        check = true;

        for(int i=0; i<str.size(); i++){
            int idx = str[i]-'a';
            if(ap[idx]){
                if(str[i-1] != str[i]){
                    check = false;
                }
            }
            ap[idx]++;
        }

        if(check) ans++;
    }

    cout<<ans<<"\n";
}