JArchive 프로그래밍 일기

문제

암호 만들기 백준 1759번

리뷰

완전탐색 문제다.

주어진 C개의 문자 중에서 L개만 선택해서 만들 수 있는 암호의 개수를 센다.

암호 문자열의 조건은 자음이 2개 이상, 모음이 1개 이상이면 답이 된다.

1. 암호를 전부 만들어 본다. --> 함수 bf()
2. L개의 문자를 고른 순간, 자음/모음 개수 조건을 충족하면 출력해준다. --> 함수 check()

L개를 다 고를 때 까지 주어진 문자들을 순회하며 (idx 변수 ) string st 에 이어 붙여본다.

string st 의 길이가 L개가 되는 순간, 자음/모음 개수 조건을 확인한다.

idx 위치의 문자를 선택 한다/안한다로 재귀 호출한다.

void bf(string st, int idx){

    if(L == st.length()){ // L 개 다 고름  

        if(check(st)){ // 자음 모음 개수 충족 여부 확인  
            cout << st << '\n';
        }
        return;
    }

    if(alpha.size() <= idx) return; // 끝 

    bf(st + alpha[idx], idx+1); // idx 문자를 선택해서 st에 이어붙인다.  

    bf(st, idx+1);  // 선택안하고 지나간다. 

}

자음/모음 조건을 확인하는 함수다.

vector STL이 제공하는 find()의 기능을 활용했다.

momo 에서 x가 존재하면 x의 인덱스를 반환하고, 없으면 end()를 반환한다.

vector<char> momo{'a', 'e', 'i', 'o', 'u'};

bool check(string &pw){ // 자음 모음 개수 세기 

    int ja = 0, mo = 0;    

    for(char x : pw){

        if( find(momo.begin(), momo.end(), x) != momo.end() ){
            mo++;
        }else{
            ja++;
        }
    }

    return (ja >= 2 && mo >= 1); 
}

코드

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

int L, C;
vector<char> alpha; // 주어진 문자 
vector<char> momo{'a', 'e', 'i', 'o', 'u'};

bool check(string &pw){ // 자음 모음 개수 세기 

    int ja = 0, mo = 0;    

    for(char x : pw){

        if( find(momo.begin(), momo.end(), x) != momo.end() ){
            mo++;
        }else{
            ja++;
        }
    }

    return (ja >= 2 && mo >= 1);
}


void bf(string st, int idx){

    if(L == st.length()){ // L 개 다 고름  

        if(check(st)){ // 자음 모음 개수 충족 여부 확인  
            cout << st << '\n';
        }
        return;
    }

    if(alpha.size() <= idx) return;

    // 선택 
    bf(st + alpha[idx], idx+1);
    // 선택안함 
    bf(st, idx+1); 

}

int main() {

    string st; // 암호  
    char ch;    

    cin >> L >> C; //C개 중에 L개를 골라 암호 만들기  

    for(int i = 0; i < C; i++){    // 주어진 문자 
        cin >> ch;
        alpha.push_back(ch);
    } // 입력받기 끝 

    sort(alpha.begin(), alpha.end()); // 오름차순 정렬 

    bf(st, 0); // 모든 조합 시도 

    return 0;
}

문제

단어 뒤집기 백준 9093번

리뷰

scanf 로 테스트케이스 숫자를 받고나서 자꾸 공백이 찍히는게 이상해서 구글링을 했다.

getline 함수로 문장을 받기 전에, 버퍼를 비워줘야 했다!!

**코드

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

char A[1002];

int main(void){

    freopen("input.txt", "rt", stdin);

     int N = 0;
     cin >> N; 

     string bufferflush; 
     getline(cin, bufferflush); // 버퍼를 비운다 

     while(N--){

         string st, rev_st;
         getline(cin, st); // 한 줄 입력받기 

         for(int i = 0; i < st.length(); i++){

             if(st[i] == ' '){
                 // 띄어쓰기 만날 때 마다 뒤집은 것 출력
                reverse(rev_st.begin(), rev_st.end());
                cout << rev_st << ' ';
                rev_st.clear(); // 출력 끝났으니까 비운다 

            }else{
                rev_st += st[i]; 
            }
        }

        // 문장의 마지막 단어 출력 후 개행  
        reverse(rev_st.begin(), rev_st.end());
        cout << rev_st << endl;
    }

     return 0;
}

문제

문자열 분석 백준 10820번

리뷰

오늘의 교훈은... 문자 초기화를 제대로 하자!!! 였다.

ROT13 문제를 풀고나서 비슷하길래 자신있게 풀었는데,

int lower=0, upper=0, num=0, space=0; // 이렇게 초기화 해야하는데. 

int lower, upper, num, space=0; // 이렇게 해서. 대여섯번을 뭐가 잘못됬나 헤맸다.

지역변수는 초기화를 잘 하자.

코드

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

int main () {

    string s;

    while(getline(cin, s)){ // 공백 포함한 문자열 받을 때는 getline이 좋다.

        int lower=0, upper=0, num=0, space=0; // 초기화를 잘 하자. 

        for(int i = 0; i < s.length(); i++){

            if(islower(s[i]) ) lower++;
            else if(isupper(s[i]) ) upper++;
            else if(isdigit(s[i]) ) num++;
            else if(' ' == s[i]) space++;
        }

        printf("%d %d %d %d\n", lower, upper, num, space);
    }

    return 0;
}

문제

접미사 배열 백준 11656번

리뷰

string STL 의 substr 을 쓰면 풀 수 있었다.

substr(i) 함수는 string의 i 인덱스 부터 마지막 인덱스까지 추출해준다.

코드

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

int main(void){

    vector<string> v;
     string S = "";
    cin >> S;

     for(int i = 0; i < S.size(); i++){
         string temp = S.substr(i); // 인덱스 i부터 끝까지 추출.
         v.push_back(temp);
    }

    sort(v.begin(), v.end()); // 정렬 

    for(int i = 0; i < S.size(); i++){ // 출력 
        cout << v[i] << '\n';
    }

    return 0;
}

문제

네 수 백준 10824번

리뷰

10 과 20 을 이어붙여서 1020가 된다면, 1000 + 20 과도 같다.

따라서 20의 자리 수 만큼(2만큼) 10에 10을 2번 곱해주면 1000이 된다.

A, B, C, D 를 입력받는데, B와 D의 자리수만 알면 된다.

    while(tempB > 0){ // B의 자리수 센다
        tempB /= 10;
        B_len++;
    }

B의 자리수를 알아냈으면, pow() 함수를 이용해서 10을 2번 곱해준다.

그리고 A에 더한다.

A = A * pow(10, B_len) + B;

문제해결 과정

pow() 함수를 쓸 때는 반드시 cmath 를 include 해 줘야 한다!

안그러면 컴파일 에러가 난다...

(1 ≤ A, B, C, D ≤ 1,000,000) 숫자의 크기가 크다. 도움이 된 질문게시판 글

네 수 모드 100만이면, 답이 int 형의 범위를 넘는다. 따라서 long long 자료형으로 선언해야 한다.

코드

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

// 10824 네 수 

long long A, B, C, D;
long long answer;

int main(void){

    cin >> A >> B >> C >> D;

    int B_len=0, D_len = 0;
    long long tempB = B, tempD = D;

    while(tempB > 0){ // B의 자리수 센다
        tempB /= 10;
        B_len++;
    }

    while(tempD > 0){ // D의 자리수 센다
        tempD /= 10;
        D_len++;
    }

    A = A * pow(10, B_len) + B;
    C = C * pow(10, D_len) + D;

    answer = A+C;

    cout << answer;

    return 0;
}

문제

ROT13 백준 11655번

리뷰

아스키 코드를 이용해서 풀었다.

공백은 32 , 숫자는 '0'과 '9'는 48 ~ 57. 대문자 65 ~ 90, 소문자 97 ~ 122 이다.

찾아보니까 대소문으로 조건으로 비교하기 보다는

if(st[i] <= 'A' && st[i] <= 'Z'){} // 대문자 

else if(st[i] <= 'a' && st[i] <= 'z'){} // 소문자      

string STL에 있는 islower 와 isupper를 쓰면 간결하게 짤 수 있었다.

코드

영 맘에 안들지만 내가 처음에 맞은 코드다.

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

int main(void){

     string st;

     getline(cin, st);

     for(int i = 0; i < st.size(); i++){

         if(st[i] == ' ') cout << ' ';
         else if(st[i] <= '9'){
             cout << st[i];
        }
         else if(st[i] <= 'Z'-13){ // 대문자  
            st[i] += 13; 
            cout << st[i];
        }else if(st[i] <= 'Z'){
            st[i] = st[i] + 13 - 26;  
            cout << st[i];
        }else if(st[i] <= 'z'-13){ // 소문자  
            st[i] += 13; 
            cout << st[i];
        }else{
            st[i] = st[i] + 13 - 26;
            cout << st[i];
        }

    }

    return 0;
}

코드2

질문게시판의 다른 분들의 코드를 보며 고쳐본 코드다.

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

int main(void){

     string st;
     getline(cin, st);
     int len = st.length();

     for(int i = 0; i < len; i++){

         if(isupper(st[i])){ // 대문자 

            if(st[i] + 13 > 'Z') st[i] = st[i]+13-26;
            else st[i] += 13;

        }else if(islower(st[i])){ // 소문자 

            if(st[i] + 13 > 'z') st[i] = st[i]+13-26;
            else st[i] += 13;         
        }
        cout << st[i];
    }

    return 0;
}

에디터 백준 1406번

리뷰

스택 2개를 이용해 풀었다.

커서를 기준으로 왼쪽에 있는 문자들은 왼쪽 스택에, 오른쪽에 있는 문자들은 오른쪽 스택에 넣는다.

커서를 기준으로 문자를 삭제하거나 삽입하거나 하기 때문에 stack을 활용할 수 있었다.

커서를 오른쪽으로 옮기는 연산은, 왼쪽 스택의 top을 오른쪽 스택에 push 하는 것이다.

커서를 왼쪽으로 옮기는 연산은, 오른쪽 스택의 top을 왼쪽 스택에 push 하는 것이다.

문제 해결 과정 

처음에는 런타임 에러가 났다. 고치다가 안되니까 1406번 문제 질문 게시판을 찾아봤다.

stack에서 pop 하기 전에 empty() 함수로 스택이 비었는지를 확인했어야 했다. 도움된 글

empty() 조건을 추가했더니, 이번에는 시간 초과가 났다.

이유는 결과 출력을 할 때, 스택에서 꺼낸 문자들을 string에 이어붙여가면서 했기 때문이었다.

왼쪽 스택에 있던 문자를 전부 오른쪽 스택으로 옮기고.

오른쪽 스택을 top 부터 빌때까지 전부 출력하면 시간 초과가 나지 않고 맞출 수 있었다.

코드

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

int main(void){

    stack<char> st_L, st_R; // 커서 기준으로 왼쪽 스택, 오른쪽 스택. 
    int M;
    string answer;

    cin >> answer >> M; // 초기 문자열과 명령어 횟수 입력받기 

    // 초기에 주어진 문자열을 전부 왼쪽 스택에 넣는다.  
    for(int i = 0; i < answer.size(); i++){
        st_L.push(answer[i]);
    }

    while(M--){ // 명령어 횟수 만큼 수행 

        char order, ch;
        cin >> order; // 명령어 입력받기 

        if(!st_L.empty() && (order == 'L') ){ // 왼쪽 스택의 top을 오른쪽 스택에 push

            ch = st_L.top();
            st_R.push(ch);
            st_L.pop();

        }else if(!st_R.empty() && (order == 'D') ){ // 오른쪽 스택의 top을 왼쪽 스택에 push

            ch = st_R.top();
            st_L.push(ch);
            st_R.pop();

        }else if(!st_L.empty() && (order == 'B') ){ // 왼쪽 스택을 pop 하면 top을 삭제한 셈.

            st_L.pop();

        }else if(order == 'P'){ // 문자를 받아서 왼쪽에 삽입

            cin >> ch;
            st_L.push(ch);
        }        
    }

    // 문자열을 처음부터 출력하기 위해, 
    // 왼쪽에 있는 문자들을 전부 오른쪽 스택으로 옮기기.
    while(!st_L.empty()){
        st_R.push(st_L.top());
        st_L.pop();
    }

    while(!st_R.empty()){ // 최종 출력 
        cout << st_R.top();
        st_R.pop();
    }
    return 0;
}