개발자 김수진

[문제]

programmers.co.kr/learn/courses/30/lessons/42839

[풀이]

에라토스테네스의 체 , next_permutation, set를 모두 공부할 수 있는 문제

에라토스테네스의 체는 어떤 수가 소수인지 아닌지 판별할 때 사용된다. 

1. 소수를 판별할 만큼 배열을 할당하고 배열을 자기 자신으로 초기화한다.

2. 2부터 자기 자신에 해당하는 것을 제외하고 배수들은 모두 0으로 바꿔서 소수에서 제외시킨다. 

#define MAX 10000

int arr[MAX]={0,};

void Eratos(int num)
{
    for(int i=1;i<=num;i++)
        arr[i] = i;
    
    for(int i=2 ; i<=num;i++){
        for(int j=2*i;j<=num;j+=i ){
            arr[i]=0;
        }
    }
    
    for(int i=2;i<=num;i++){
        if(arr[i]!=0)
            printf("%d",i);
    }
}

 next_permutation은 헤더에 algorithm을 추가하면 사용할 수 있는 STL이다.

벡터나 배열로 사용이 가능하며 가능한 모든 조합을 구할 수 있다.

단, 사용하기 전에 벡터나 배열이 오름차순으로 정렬되어 있어야 된다.

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

using namespace std;

int main(void)
{
    vector <int> v;
    
    for(int i=5;i>=2;i--)   v.push_back(i);
    sort(v.begin(),v.end());
    do{
        for(int i=0;i<v.size();i++) cout << v[i];
        cout << endl;
    }while(next_permutation(v.begin(), v.end()));
    
    return  0;
}

아래 사진과 같이 벡터의 모든 조합을 구할 수 있다.

set은 중복이 허용되지 않고 자동으로 오름차순 정렬이 된다.

======================================================

문제 풀이

1. input으로 주어진 numbers를 내림차순으로 정렬하여 number로 만들 수 있는 숫자 중에서 가장 큰 수를 구한다.

2. 에라토스테네스의 체를 사용해 가장 큰 수 까지 소수인지 아닌지를 판별

3. 다시 numbers를 오름차순으로 정렬하여 next_permutation을 사용해 가능한 모든 조합을 구한다.

이 때 해당 숫자가 소수이고 set에 존재하지 않는다면  set에 insert

[코드]

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

using namespace std;

vector <int> v;
int IsPrime[10000000]={0,};
int cnt=0;

bool comp(int a, int b)
{
    if(a > b )  return true;
    return false;
}

void Eratos(int num)
{
    IsPrime[0] = 0;
    IsPrime[1] = 0;
    
    for(int i=2 ; i <= num ; i++)
    {
        IsPrime[i] = i;
    }
    
    for(int i=2;i<=num;i++)
    {
        if(IsPrime[i] == 0) continue;
        
        for(int j=2*i ; j<=num; j+=i){
            IsPrime[j]=0;
        }
    }
}

int solution(string numbers) {
    int answer = 0;
    set <int> s;
    
    sort(numbers.begin(), numbers.end(),comp);
    int num = stoi(numbers);

    Eratos(num);
    
    sort(numbers.begin(), numbers.end());
    
    do{
        for(int i=1;i<=numbers.size();i++)
        {
            string tmp1 = numbers.substr(0,i);
            num = stoi(tmp1);
            
            if(IsPrime[num]!= 0 )    s.insert(num);
        }
    }while(next_permutation(numbers.begin(),numbers.end()));

    return s.size();
}

[문제]

programmers.co.kr/learn/courses/30/lessons/42883

[풀이]

input으로 숫자 number와 number에서 제외할 숫자의 개수인 k가 주어진다.

number에서 k개의 숫자를 제거하여 만들 수 있는 최댓 값을 구하면 된다.

처음에는 DFS를 사용하여 모든 경우에 대해 다 확인해봤는데 생각해보니 number의 길이가 1부터 1,000,000까지이다.

그래서 다른 방법을 생각해보니 number의 시작부터 큰 수를 골라 총 number.size()-k의 숫자를 골라서 answer로 return 하면 된다. 

1. number의 처음부터 'k+선택된 숫자의 수'까지 중에서 가장 큰 수를 선택한다.

2. 선택한 수의 다음 index부터 'k+선택된 숫자의 수'까지 중에서 가장 큰 수를 선택한다.

위의 과정을 'number.size() - k' 번 반복한다. 

예를 들어  number= "1234568"이고 k=3인 경우 

총 4개의 숫자를 선택해야 하므로 , 0~3+0 범위 내에서 가장 큰 수를 택해야 된다. 

범위 내에서 가장 큰 수 4를 택하고 , 4~4+1 범위 내에서 가장 큰 수를 택해야 된다. 

이런 식으로 반복하여 4568이라는 가장 큰 수를 구할 수 있게 된다.

[코드]

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    
    int tmp = number.size()-k;
    int idx =0;
    int tmp_idx=0;
    
    for(int i=0;i<tmp; i++)
    {
        int _max = number[idx]-'0';
        tmp_idx = idx;
        
        for(int j=idx; j<=k+i ; j++)
        {
            if(number[j]-'0' > _max ){
                _max =number[j]-'0'; 
                tmp_idx = j;
            }  
        }
        idx = tmp_idx+1;
        answer += to_string(_max);       
    }
    return answer;
}

[문제]

programmers.co.kr/learn/courses/30/lessons/49994#

[풀이]

입력으로 움직이는 방향이 주어지고 이에 알맞게 움직이면 된다.

걸어간 길의 길이를 출력하면 된다.

단, 이미 지나왔던 경로는 포함하지 않는다.

또한 범위를 벗어나는 경우 움직이지 않는다.

따라서 좌표와 방향을 가지고 visited 배열을 사용해 이미 방문한 길은 포함하지 않도록 하였다.

문제에서 범위가 -5부터 5까지인데 배열은 index가 0부터 가능하므로

(0,0) ~ (10, 10)으로 변경했다.

[코드]

#include <string>

#define MAX 11

using namespace std;

int solution(string dirs) {
    
    int answer = 0;
    int visited[MAX][MAX][4]={0,};
    
    int x=5;
    int y=5;

    int _size = dirs.size();
    
    for(int i=0;i<_size;i++)
    {
        int dir=0;
        int nx=x;
        int ny=y;
        
        switch(dirs[i])
        {
            case 'U':
                ny +=1;
                dir =0;
                break;
            case 'D':
                ny -=1;
                dir=1;
                break;
            case 'R':
                nx +=1;
                dir=2;
                break;
            case 'L':
                nx -=1;
                dir=3;
                break;
        }
        if(nx<0 || ny<0 || nx >10 || ny>10) continue;
        
        if(visited[x][y][dir]==0){
            answer+=1;
            visited[x][y][dir] =1;
            
            if(dir==0)  dir=1;
            else if (dir==1)    dir=0;
            else if(dir==2) dir=3;
            else if(dir==3) dir=2;
            
            visited[nx][ny][dir]=1;
        }
        x=nx;
        y=ny;
    }
    return answer;
}

[문제]

https://programmers.co.kr/learn/courses/30/lessons/59410

[풀이]

sql 문제로 IFNULL을 사용해 이름이 NULL이면 "No name"으로 채워줬다.

또한 ANIMAL_ID를 기준으로 오름차순으로 정렬 

IFNULL(필드명, "대체할 값") : 필드가 Null이면 대체할 값으로 채운다.

[코드]

SELECT ANIMAL_TYPE,IFNULL(NAME, "No name") ,SEX_UPON_INTAKE from ANIMAL_INS
order by ANIMAL_ID ASC

[문제]

https://programmers.co.kr/learn/courses/30/lessons/42884

[풀이]

차량 이동경로를 sort 함수를 사용해 오름차순으로 정렬한다.

첫번째 이동경로의 진출 지점을  CCTV의 위치로 초기화

두번째 이동경로부터 마지막 이동경로까지 

현재 이동경로의 진출 지점이 CCTV의 위치보다 앞에 있는 경우 => CCTV의 위치만 update

현재 이동경로의 진입 지점이 CCTV의 위치보다 뒤에 있는 경우 => CCTV의 위치 update, CCTV 설치 갯수 1 증가.

[코드]

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

using namespace std;

int solution(vector<vector<int>> routes) {
    int answer = 1;
    sort(routes.begin(), routes.end());
    
    int pos = routes[0][1];
    
    for(int i=1;i<routes.size();i++){
        if(routes[i][1] < pos)  pos = routes[i][1];
        else if(routes[i][0] > pos){
            answer++;
            pos = routes[i][0];
        }
    }
    return answer;
}

진짜 간단하게 풀 수 있는 문제인데 처음에 너무 복잡하게 생각했다.