JArchive 프로그래밍 일기

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

에라토스테네스의 체 방식을 써야 효율성케이스까지 패스할 수 있는 문제다. (프로그래머스 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;
}

오늘 한 일 

용역 일 본격시작하기 전에, C를 다시 보고 있다. 

헷갈리는 함수들이랑 잊어버린 문법들이 왜이렇게 많은건지. 

다시 정리하고 나니깐 보람있었다. 

오늘 한 일 

알고리즘 문제 5개를 풀었다.

조합을 이용한 문제가 있었는데, 옛 기억이 나서 풀 수 있었다. 순열, 조합 문제를 복습해야겠다. 

요즘 github에 커밋하고 푸시하는 재미가 쏠쏠하다. 

스터디를 해서 그런 것 같다. 역시 코딩은 같이 해야 재미가 난다. 

간간히 C++ 을 배우고 있는데 진도 빼는데 속도를 올려야겠다. 

오늘 한 일 

알고리즘 문제 3문제를 풀었다. 

용역 프로젝트의 코드를 분석하기 시작했다. 

안드로이드가 RFID로 보내주는 데이터를 읽어서 메모리의 값을 변경하는 부분을 주로 봤다. 

역시 다른 사람의 코드를 읽는 것은 정말 쉬운 일이 아니다. 분량을 보니 며칠 걸릴 것 같다. 

화이팅 !!!