JArchive 프로그래밍 일기

문제

시저암호 프로그래머스 level 1

어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 시저 암호라고 합니다. 예를 들어 AB는 1만큼 밀면 BC가 되고, 3만큼 밀면 DE가 됩니다. z는 1만큼 밀면 a가 됩니다. 문자열 s와 거리 n을 입력받아 s를 n만큼 민 암호문을 만드는 함수, solution을 완성해 보세요.

제한 조건

• 공백은 아무리 밀어도 공백입니다.
• s는 알파벳 소문자, 대문자, 공백으로만 이루어져 있습니다.
• s의 길이는 8000이하입니다.
• n은 1 이상, 25이하인 자연수입니다.

입출력 예

리뷰

테스트 케이스 일부를 통과 못해서 다른사람들의 질문답변을 읽고 도움을 받았다.

char는 1byte니까 1부터 128까지다. 근데 소문자 z는 122이고 25가 더해지는 경우 128을 초과한다.

소문자를 변환할때 (unsigned char) 로 캐스팅해서 테케를 전체 통과했다.

코드

#include <string>
#include <vector>

using namespace std;
string solution(string s, int n) {

    string answer = "";
    int s_len = s.length();
    int i = 0;

    for(i=0; i < s_len; i++){

        if(s[i] <= 90 && s[i] >= 65 ){ // 대문자  

            s[i] = s[i] + n;

            if(s[i] > 90){
                s[i] = s[i]  + 64 - 90;
            }

            answer += s[i];

        }else if(s[i] == ' '){ // 공백  

            answer += " ";

        }else if(s[i] <= 122 && s[i] >= 97){ // 소문자 

            s[i] += n;

            if((unsigned char)s[i] > 122){
                s[i] = s[i] -122 + 96;
            }

            answer += s[i];
        }
    }

    return answer;
}

문제

문자열 다루기 기본

프로그래머스 level 1 문제

문자열 s의 길이가 4 혹은 6이고, 숫자로만 구성돼있는지 확인해주는 함수, solution을 완성하세요. 예를 들어 s가 a234이면 False를 리턴하고 1234라면 True를 리턴하면 됩니다.

제한 사항

• s는 길이 1 이상, 길이 8 이하인 문자열입니다.

입출력 예

리뷰

길이 제한을 처리해주고, 전부 문자인지 확인하면 된다.

제출 후 다른 코드를 보니까 숫자인지 확인하는 isdigit() 함수를 쓴 분이 있었다.

isdigit()은 char 타입을 입력받는다.

10진수 숫자로 변경 가능하면 true, 그렇지않다면 0을 반환한다.

#include <cctype>

int isdigit(int c);

isdigit()

코드

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

bool solution(string s) {

    bool answer = true;
     int i = 0;
     int s_len = s.length();

     if(s_len != 4 && s_len != 6){
         return false;
    }

     for(i = 0; i < s_len; i++){
        if(s[i] > 57 || s[i] < 48 ){
            answer = false;
            break;
        }     
    }

    return answer;
}

다리를 지나는 트럭

큐를 이용해 푸는 프로그래머스 level 2 문제

어려워서 문제 해설을 찾아봤다. 큐 2개를 이용해 풀었다.

대기하는 차(truck_weight)가 1대 이상 존재하고, 차가 도로위에 올라갈 수 있다면 도로에 진입시킨다.

(도로가 견딜 수 있는 무게를 고려한다.)

도로에 올라가있는 차량 리스트를 queue로 확인 한다. ( queue count )

도로에 올라가있는 차량은 1초에 1씩 이동한다.

도로를 지나고 있는 차량의 남은 거리를 queue로 관리한다. ( queue bridge_on )

차를 pop해서 차의 남은 거리를 1씩 감소시키고, 다시 push 한다.

대기차가 없어도 도로에 차가 있다면 차가 1씩 이동하고 있으므로 시간은 1초씩 계속 흐른다.

코드

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

int solution(int bridge_length, int weight, vector<int> truck_weights) {

    // 시간
    int answer = 0;

    // 도로 위 차 
    queue<int> count;

    // 차마다 가야할 남은 거리 (도로를 얼마나 더 가야 하는지)  
    queue<int> bridge_on;

    // 도로 위의 차 무게 합계
    int current_weight = 0;

    int i = 0;

    while(true){

        //차들이 가야할 거리 
        int togo_size = bridge_on.size();

        // 차를 도로에 진입시킨다.  
        for(i = 0; i < togo_size; i++){

            // 제일 앞에 가고있는 차의 남은 거리  
            int len_front = bridge_on.front();

            bridge_on.pop();

            if(len_front <= 1){ // 남은 거리가 1 이하라면, 이 차의 무게를 제외시킨다 
                current_weight -= count.front();
                count.pop();
                continue;
            } else{
                //  거리 감소시키고 다시 push  
                bridge_on.push(--len_front); 
            }
        } 

        // 도로의 제한무게 만큼 차를 집어넣는다. 대기 차량이 1개 이상 있어야 함.  
        if(truck_weights[0] + current_weight <= weight && truck_weights.size() > 0 ) {

            count.push(truck_weights[0]); // 도로에 차 추가

            current_weight += truck_weights[0]; // 현재 도로 무게에 차 무게 추가  

            truck_weights.erase(truck_weights.begin());  // 대기 차량 삭제  

            bridge_on.push(bridge_length); // 이 차가 지나야할 도로 거리 추가  


        }

        answer++; // 시간이 지나감 

        if(count.size() == 0 && truck_weights.size() == 0){
            break;
        } 

    }

    return answer;
}

참고 포스팅

소수찾기 (에라토스테네스의 체)

에라토스테네스의 체 방식을 써야 효율성케이스까지 패스할 수 있는 문제다. (프로그래머스 level 1)

문제

문제링크

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건: n은 2이상 1000000이하의 자연수입니다.

리뷰

n이 커지면 시간초과가 난다.
에라토스테네스의 체 를 이용해야한다.

구하려는 범위 크기 + 1만큼의 배열을 선언한다.

1000000 이라면, int arr[1000001]선언.

arr[0]과 arr[1]은 사용하지 않는다. 0과 1은 소수가 아니기 때문이다.

arr의 값이 0이면 소수, 1이면 소수가 아니다.

일단 arr배열의 값은 전부 0으로 초기화 하여 처음에는 소수라고 본다.

만일, arr[i]가 0이면(숫자 i가 소수라면), i이후의 i의 배수들은 i를 약수로 가진 수들이다.

따라서 i 이후의 i의 배수에 대해 1값을 준다. (소수가 아니다.)

arr[i]가 1이면 i는 이미 소수가 아니므로 i의 배수 역시 소수가 아니다.

이렇게 배수들을 제외한다.

어느 수의 배수라는 것은 소수가 아니라는 뜻이기 때문이다.

( 이 문장이 한 번에 이해가 안 됬었다, 그치만 직접 수를 써보면서 몇 번 다시 읽어보면 이해할 수 있었다. )

2가 소수라면(arr[2] == 0) , 2의 배수들을 지운다. (arr[2의배수들] == 1)

3이 소수라면 (arr[3] == 0), 3의 배수들을 지운다. (arr[3의 배수들] == 1)

이런식으로 진행한다.

지워야 할 수가 겹치는 문제

2의 배수들: 4, 6, 8, 10, 12, 14 를 지운다.

3의 배수들: 6, 9, 12, 15 .. 를 지운다.

6과 12처럼 지워야할 수의 겹침을 피하려면, 제곱한 수 부터 배수를 지우면 된다.

예를 들어, 5의 배수를 지워야한다면 5_2, 즉 10부터 지우는게 아니라 5의 제곱 25부터 지운다.

25 + (1 * 5), 25 + (2 * 5), 25 + (3 * 5) , ... 그러면 이전에 지워진 배수들을 건너 뛰게 된다.

코드

#include <stdio.h>
#include <vector>
using namespace std;

// 소수 찾기  프로그래머스  

/*
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
n은 2이상 1000000이하의 자연수입니다.
*/


int arr[1000001]; 
// arr[0]과 arr[1]은 사용하지 않는다.  0과 1은 소수가 아니기 때문. 
// 소수면 0, 소수가 아니면 1값을 갖는다. 

int solution(int n) {

    int answer = 0;
    int i = 0, j = 0;

    for (i = 2; i * i <= n; i++)
    {
        if (arr[i] == 0){ // i가 소수라면, i의 배수는 소수가 아니다.  

            // 유의: i의 제곱부터 지우기 시작한다.  
            for (j = i * i; j <= n; j += i)
                arr[j] = 1; // 소수가 아니므로 1값 할당. 
        }

    }

    for(i = 2; i <= n; i++){ // 소수로 남겨진 것들의 개수를 센다  
        if(arr[i] == 0) answer++;
    }

    return answer;
}

도움이 되셨다면 '공감'을 눌러주세요 :)

쇠막대기

문제링크

스택/큐 를 주제로 많은 사람들이 풀어보는 쇠막대기 문제다. (프로그래머스 level 2)

리뷰

괄호가 레이저 또는 막대를 표현한다.

그래서 여는 괄호와 닫는 괄호의 짝이 맞고 반드시 여는 괄호부터 시작된다.

여는괄호와 닫는괄호가 연속한 것을 레이저로 인식하도록 했다. 그래서 open_flag를 두었다.

레이저가 아니고서야 닫는괄호가 나오면 막대의 끝인 것이다.

레이저가 끝나면 스택에 있는 여는괄호 수 만큼 더해준다.

막대가 끝나면 막대하나가 끝난 거니까 +1 해준다.

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


int solution(string arrangement) {

    int answer = 0;
    int i, len = 0;
    stack<char> st;
    bool open_flag = true;

    len = arrangement.size();

    for(i=0; i<len; i++){
        // printf("%c\n", arrangement[i]);
        char pa = arrangement[i];

        if(pa == '(') { // 여는 괄호라면  
            st.push(pa);
            open_flag = true;

        }else{ // ')' 닫는 괄호라면  
            st.pop();
            if(open_flag){ // 레이저  
                answer += st.size();
            }else{
                answer++;
            }
            open_flag = false;


        }
    }

    return answer;
}

리뷰

문자열 내림차순으로 배치하기 프로그래머스 level 1 문제

C++에서 제공하는 퀵소트로 구현된 오름차순 정렬 sort() 함수를 썼다.

#include <algorithm>
void sort(T start, T end, Compare comp)

세번째에 기준 인자, 함수를 줄 수 있다.

내림차순은 greater<자료형>() 오름차순은 less<자료형>()

• sort(s.begin(), s.end()); // 기본은 오름차순 정렬
• sort(s.begin(), s.end(), greater<자료형>());
• sort(s.begin(), s.end(), less<자료형>());

헤더파일을 inlude 하고 greater, less, plus minus 를 사용할 수 있다.

코드

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;


string solution(string s) {

    sort(s.begin(), s.end(), greater<char>());
    return s;

}

int main(void)
{
    string input = "Zbcdefg";    
    string answer = "";

    answer = solution(input);

    // string 클래스를 char* 형태로 변환할 때는 c_str() 
    printf("%s", answer.c_str());
    // 출력내용 : gfedcbZ 

    return 0;
}

H-index

문제링크
프로그래머스 level2 문제다.

1시간 끙끙대다가 다른분들의 풀이법을 읽어봤다.
[0] 인경우 0이고, [7]인경우 1이었다.
[30, 19, 9, 1] 인 경우에도 답은 3이었다. 테스트케이스를 여러개 보니까 조금 감이 왔다.

참고링크

리뷰

문제에 나와있는 테스트케이스에서
[3, 0, 9, 2, 6] 이라면, 답은 3이라고 생각했다.
하지만, 다른분들의 풀이법을 읽어보니 인용수 배열중에 답이 꼭 있는것이 아니었다.
그리고 정렬을 하면 수월했다.
정렬 해두고, 현재 인덱스보다 작아진다면 탈출하면 답이 나온다.

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

// H-index (프로그래머스) 

int solution(vector<int> citations){

    int answer = 0;

    // 정렬 
    sort(citations.begin(), citations.end(), greater<int>()); 

    while(answer < citations.size()){

        if(citations[answer] <= answer){ // 인덱스 보다 작아지는 순간 종료
            break;
        }else{
            answer++;
        }
    }

    return answer;
}