JArchive 프로그래밍 일기

문제

정수 내림차순으로 배치하기 프로그래머스 level1

리뷰

단순하게 숫자 한 자리씩 잘라서 처리해야지 하고 짰다.

1. 정수를 한 자리씩 잘라서 벡터에 넣는다.
2. 정렬한다.
3. 10의 n승으로 바꿔서 더한다.

다른 분의 풀이를 보니 형변환을 하셔서 간단히 푼 코드였다.

정수를 string 으로 형변환

string str = to_string(1234567);

string을 long long 으로 형변환

long long answerll = stoll("1234");

형변환은 PS에서 반드시 알아야 하고 자주 나오는 요소니까 자주 쓰면서 숙지하자!

내 코드

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

long long solution(long long n) {
    long long answer = 0;
    vector<int> v; 

    while (n) {
        v.push_back(n % 10);
        n /= 10;
    }

    sort(v.begin(), v.end());

    for (int i = 0; i < v.size(); i++) {
        answer += ( pow(10, i) * v[i] );
    }

    return answer;
}

다른 사람의 코드

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

long long solution(long long n) {
    long long answer = 0;

    string str = to_string(n);
    sort(str.begin(), str.end(), greater<char>());
    answer = stoll(str);

    return answer;
}

Mini-Max Sum

Algorithm Warmup

코드포스에서 유용한 벡터 함수 포스팅을 봐서 문제에 써먹었다.

배열에서 원소의 값을 처음부터 끝까지 누적해서 더할때 반복문 필요 없이 아래처럼 가능하다.

accumulate() 함수가 있다.

int sum = accumulate(all(), 0LL); 
// 여기서 0LL은 0과는 다르다. 

코드

void miniMaxSum(vector<int> arr) {

    sort(arr.begin(), arr.end());
    long long sum = accumulate(arr.begin(), arr.end(), 0LL);

    cout << sum-arr[arr.size()-1] << ' ' << sum - arr[0];
}

문제

스킬 트리 프로그래머스 level2

리뷰

스킬트리에서 스킬에 포함된 문자만 벡터에 넣는다.

스킬의 인덱스와 스킬트리에서 뽑아낸 인덱스가 일치하는지 확인한다.

예를 들어, 스킬 "CBD" , 스킬트리는 "BACDE" 일 때 아래의 과정을 거친다.

스킬 "CBD" 에서. 차례로 "B", "A", "C" ... 를 찾아본다.

for (int j = 0; j < str.size(); j++) { // 스킬트리 문자열을 순회 
    int idx = skill.find(str[j]); // 스킬에서 문자가 발견되는지(포함되는지)
    if (idx != -1) v.push_back(idx); // 스킬에 없는 문자라면 -1 
}
// 반복문이 끝나면 벡터 v에 저장되는 원소들 {1, 0, 2}

왜냐하면 스킬에서 B를 찾으면 idx == 1

스킬에서 A를 찾으면, 없으니까 idx == -1 (push 안 한다)

스킬에서 C를 찾으면, idx == 0

스킬에서 D를 찾으면 idx == 2

스킬의 인덱스와 벡터에 들어간 인덱스가 일치하는지 확인한다.

for (int k = 0; k < v.size(); k++) { // 벡터 v의 크기 만큼 순회
    // 스킬의 인덱스와 벡터의 인덱스가 일치하는지 확인 
    if (v[k] != k) {
        flag = false; break;
    }
} 

코드

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

int solution(string skill, vector<string> skill_trees) {

    int skill_len = skill.length(); // 스킬 문자열의 길이 
    int answer = 0;

    for (int i = 0; i < skill_trees.size(); i++) { // 스킬트리들의 개수 만큼 반복  
        string str = skill_trees[i]; // 스킬트리 하나. 
        vector<int> v;

        for (int j = 0; j < str.size(); j++) { // 스킬트리 문자열을 순회 

            int idx = skill.find(str[j]); // 스킬에서 문자가 발견되는지(포함되는지)
             if (idx != -1) v.push_back(idx); // 스킬에 없는 문자라면 -1 
        }

        bool flag = true;

        for (int k = 0; k < v.size(); k++) { 
            // 스킬의 인덱스와 벡터의 인덱스가 일치하는지 확인 
            if (v[k] != k) {
                flag = false; break;
            }
        }

        if (flag) answer++;
    }

    return answer;
}

참고할 만한 코드

'스킬'에 포함되지 않은 알파벳을 전부 지운다. erase() 이용.

/*
스킬이 "CBD" 라면,  
"BACDE"--> "AE" 
"AECB" --> "CB" 
"CBADF"--> "CBD"
*/

제거 후의 문자열의 길이 만큼 '스킬' 알파벳을 확인한다.

"CB"가 결과물인 경우, 스킬도 "CB"까지만 확인한다. 일치한다면 '가능한 스킬트리'다.

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

int solution(string skill, vector<string> skill_trees) {
    int skill_len = skill.length();
    int answer = 0;

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

        // 스킬 순서에 포함되지 않는 스킬들 제거.
        for (int j = 0; j < skill_trees[i].size(); j++) {

            if (skill.find(skill_trees[i][j]) == string::npos) {

                skill_trees[i].erase(j, 1); // j인덱스부터 1개 제거.
                // erase 함수가 실행되면 배열의 뒷 요소들이 자동으로 한칸씩 당겨짐.
                // j 인덱스 감소시켜야 모든 원소를 빠짐없이 확인 가능.
                j--;
            }    
        }
        // 스킬순서 문자열 에서 skill_trees[i] 문자열 길이만큼 잘라낸다 
        string temp = skill.substr(0, skill_trees[i].size()); 

        if (skill_trees[i] == temp) {
            answer++;
        }        
    }

    return answer;
}

iPhone 11pro를 구입해 SKT를 1년 이용했다. (아이폰 공기계는 카드 무이자 할부로 구매)

카드 사용 내역 6개월 치를 찬찬히 보다가 4만원어치 통신비가 사용량에 비해 아깝다는 생각이 들었다.

( 3개월 평균 사용량이  음성 250분, 데이터 2.5GB~3GB )

마침 가입비를 면제하는 이벤트를 하길래,  헬로모바일로 바꿨다. 후기글도 2천개정도 써있는데 전반적으로 좋았다. 

알뜰폰 장단점 

단점

* 이통3사 (KT SKT LG) 의 여러 혜택이 없다. (영화, 뮤지컬, 음악 어플 할인, 특정 프렌차이즈 관련 할인 및 적립)

* 고객센터 전화 연결이 어렵다고 들었음. 

* TV+인터넷+모바일요금 결합 할인이 없다. 

* 가입 과정이 온라인만 가능하니까 어르신들은 불편하실 수도 있다. 

장점

* 통신비가 매우 저렴하다. 

* 통화품질 차이가 안느껴진다. 품질 좋다. 

* 새 폰에서 개통이 불가하다.

(공기계 사서 알뜰폰으로 바로 가입이 안된다. 하루라도 이통3사를 쓰긴 써야 알뜰폰 통신사로 넘어갈 수 있다. 어이없는 부분... )

* 내 사용량에 맞는 요금제가 다양하다. 엄청 적게 사용하는 경우 엄청 저렴한 요금제를 선택하면 된다. 

* 참고) 한국정보통신진흥협회가 16개 알뜰폰 통신사 상품을 비교해주는  알뜰폰허브 에서 자신의 사용량에 맞는 알뜰폰 요금제를 조회할 수 있다. 

SKT에서 납부한 요금 vs 헬로모바일 요금 

매달 2만원 정도 아끼게 됬으니까.  일년에 24만원 아끼는거다. 캬컄!! 개이득

SKT T플랜 안심2.5GB 은  매달 42,550원을 납부했다.  

T플랜 안심2.5GB 통신요금은 35,368원이다.

( 부가세 포함 43,000원.  - 선택약정 할인 25%  7,587원 할인)  

FLO 음악어플 (SKT니까 약간할인받아서) 7,182원씩 같이 냈다. 

알뜰폰 통신사 요금제가 왜 저렴할까? 

메이저 통신3사의 통신망을 빌려서 재판매를 한다.

망을 빌려쓰는 거니까 통신망을 새로 증설, 유지보수 하는 비용 자체가 없다! 그래서 저렴한 가격에 이용할 수 있는 것이다.

메이저 통신3사의 망을 쓰는거니까 통화, 데이터 품질이 동일하다. 

알뜰폰 개통 과정 

1.  CU편의점에서 LG헬로모바일 LTE후불 유심을 8800원에 구매했다. 

개통 방법은 3가지다.  상담사와 함꼐하는 온라인신청, 전화개통. 그리고 본인이 유심 구매하고 온라인으로 셀프개통.

유의사항에 보면, 내국인 전용 상품이라고 써있다. 

2. 헬로모바일 홈페이지에서 요금제를 선택하고 편의점에서 산 유심카드 일련번호를 입력한다. 

The 착한 데이터 유심 3.6GB 으로 가입했다.  (데이터 3.6GB + 통화 무제한)

3. 헬로모바일 유심 끼우고, 전원을 1~2번 껐다 켰다 한다. 

4. '셀프개통' 서비스를 선택해서 바로 개통한다. 

온라인으로 가입신청을 정상적으로 했다면, 셀프개통 하라고 URL 포함된 문자가 하나 온다.

본인인증을 위해 주민등록증, 요금결제에 필요한 신용카드가 필요하다. 

편의점에서 유심 사오고 거의 20분만에(?) 개통했다.

통화도 LTE로 동영상도 틀어봤다. 품질 차이 못느끼겠고 똑같다. ㅋㅋ 

가끔 사용량 조회 하려고 헬로모바일 어플 설치해서 로그인 해뒀다. 

무튼 뿌듯.

문제

BFS 스페셜 저지

리뷰

입력으로 정점의 순서가 주어진다.

그 순서가 BFS로 탐색할 때 나올 수 있는 방문 순서인가를 확인하는 문제다.

순서가 올바르지 않다는 것은, 접근해서는 안되는 차례에 방문했다는 것이다.

시작점은 반드시 1이어야한다.

큐에 넣는 순서는 input list 에 맞춰서 BFS를 진행해야 한다.

코드

#include <iostream>
#include <algorithm> 
#include <vector>
#include <queue>
#include <set>
using namespace std;

// BFS 스페셜 저지 (BOJ 16940) 

int N; // 정점 개수 
vector<int> B[100001]; // 인접리스트 
int visited[100001]; // 방문 체크 
queue<int> q, input_q;

int BFS(){

    while(!q.empty()){
        int current = q.front(); 
        q.pop();

        set<int> s; // 중복제외하고 정점 번호 저장할 set  

        for(int i : B[current]){ // 현재 노드의 인접 정점들이 있는지 확인   
            if(visited[i]) continue; // 이미 방문한것 제외
            visited[i] = true; // 방문표시  
            s.insert(i); // 방문 해야할 것들 set에 저장  
        }

        // input_q 순서 따라가기
        for(int i = 0; i < (int)s.size(); i++){
            if(input_q.empty()) return false; // 방문 할 정점 없음 종료  

            int candidate = input_q.front(); // 지금 방문할 순서의 정점
            input_q.pop();

            // 후보가 set에 없다면, 지금 방문할 순서의 정점이 현재정점과 인접하지 않으므로 종료.  
            if(s.find(candidate) == s.end()) return false;
            else q.push(candidate);
        }
    }

    return true;        
}

bool solve(){

    int first = input_q.front(); 
    input_q.pop();
    if(first != 1) return false; // 시작 정점은 1이어야 한다  

    visited[first] = true;

    q.push(first); // 방문했으니까 큐에 넣는다 

    bool answer = BFS(); // BFS 탐색 시작  

    return answer;
}

void input(){ // 문제의 입력받는다  

    cin >> N; // 정점 개수  
    int a=0, b=0; 

    for(int i = 1; i < N; i++){ // N-1개의 인접리스트 정보   
        cin >> a >> b;
        B[a].push_back(b);
        B[b].push_back(a);
    }

    for(int i = 0; i < N; i++){ // 주어진 방문 순서를 전부 큐에 넣는다  
        cin >> a;
        input_q.push(a);
    }
}

int main() {    

     input();
     bool answer = solve();  
     cout << answer;

    return 0;
} 

문제

카펫 프로그래머스 level2

리뷰

완전탐색 카테고리의 문제.

카펫의 갈색 격자의 수, 노랑 격자의 수가 주어진다. 카펫의 가로 길이, 세로 길이를 맞춰야 한다.

brown + yellow 를 합치면 카펫의 면적을 알 수 있다.

가로 X 세로 == 면적 이 된다.

예를 들어, 면적이 12라면, 12의 제곱근(면적의 제곱근) 부터 3까지 탐색하면 세로의 길이를 얻을 수 있다.

세로가 3 이상이 되어야 brown이 yellow를 한 줄이라도 둘러쌀 수 있다.

세로가 2라면, yellow 격자는 생길 수 없기 때문이다.

long long sum = brown + yellow; // 면적 
long long hori = 3;  // 세로
long long ver = 1;   // 가로 
int limit =  sqrt(sum); // 면적의 제곱근 

for(hori = 3; hori <= limit; hori++){ // 세로 hori 구하기 

    if( sum % hori == 0){ // 면적과 나누어 떨어지는 세로 길이 발견.
        ver = sum/hori;  // 가로 길이가 정해짐.

    }
}

면적과 나누어 떨어지는 세로 길이를 구했을 때, 아래의 조건을 만족하는지 확인하여 격자의 개수까지 맞춰본다.

(ver-2)*(hori-2) == yellow  

가로 기준으로 봤을 때, brown이 둘러싼 맨 위 한 줄, 맨 아래 한 줄을 빼면 ( hori - 2 ) 가 된다.

세로 기준으로 봤을 때도 맨 왼쪽, 맨 오른쪽 세로줄을 2개 빼면, ( ver - 2 ) 가 된다.

이렇게 격자의 개수를 확인하는 이유는, 특정 면적을 만족시킬 수 있는 가로, 세로의 길이는 여러개가 나올 수 있기 때문이다.

코드

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

vector<int> solution(int brown, int yellow) {
    vector<int> answer;

    long long sum = brown + yellow; // 면적 
    long long hori = 3;  // 세로
    long long ver = 1;   // 가로 
    int limit =  sqrt(sum); // 면적의 제곱근 

    for(hori = 3; hori <= limit; hori++){ // 세로 구하기 

        if( sum % hori == 0){
            ver = sum/hori; 

            if( (ver-2)*(hori-2) == yellow ){
                answer.push_back(ver); // 가로 
                answer.push_back(hori); // 세로 
                break;                
            }

        }
    }

    return answer;
}

문제

소수 찾기 프로그래머스 level2

리뷰

완전탐색 카테고리의 문제다.

에라토스테네스의 체로 소수를 체크해야 하고. 주어진 숫자들로 순열을 만들면 된다.

핵심 코드

bool* prime;

void eratos(int num){ // 에라토스테네스의 체 

    prime = new bool[num+1]; // 배열 크기 할당 

    for(int i = 2; i <= num; i++){
        prime[i] = true; 
    } 
    prime[0] = prime[1] = false;

    for(int i = 2; i * i <= num; i++){

        if(prime[i]){ // 소수라면, 배수를 전부 false
            for(int j = i*i; j <= num; j += i){
                prime[j] = false;
            } 
        }
    }
}

1. 예를 들어 71까지의 소수를 구하려면 72 크기의 배열을 만든다.소수의 배수들은 소수가 아니기 때문이다.
   에라토스테네스 GIF를 참고하자
2. 소수를 만날 때 마다 (인덱스 값이 true 라면, ) 소수의 배수가 되는 인덱스들의 값을 전부 false로 만든다.
3. 구하려는 범위 만큼 bool 배열을 만들고, 배열의 인덱스를 전부 소수라고 생각하여 true로 초기화 한다.

순열 만들기오름차순으로 정렬되어 있다면, 예를 들어 대상 벡터가 [1, 2, 3] 이라면, [3, 2, 1] 이 될 때 까지 순열을 만들어서 리턴해준다.

2. 따라서 반드시 미리 오름차순 정렬이 되어 있어야 한다. [3, 2, 1] 인채로 넣으면 바로 종료된다.
3. #include <algorithm>
next_permutation(v.begin(), v.end())

코드

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


bool* prime;

void eratos(int num){ // 에라토스테네스의 체 

    prime = new bool[num+1]; // 배열 크기 할당 

    for(int i = 2; i <= num; i++){
        prime[i] = true; 
    } 
    prime[0] = prime[1] = false;

    for(int i = 2; i * i <= num; i++){

        if(prime[i]){ // 소수라면, 배수를 전부 false
            for(int j = i*i; j <= num; j += i){
                prime[j] = false;
            } 
        }
    }
}

int solution(string numbers) {

    sort(numbers.begin(), numbers.end(), greater<int>()); 
    // 내림차순 정렬 -> 숫자로 만들 수 있는 가장 큰 수 만들기.

    int maxnum = atoi(numbers.c_str()); // 문자열->숫자

    eratos(maxnum); // 소수 체크

    sort(numbers.begin(), numbers.end()); // 오름차순 정렬 (next_permutation 함수 활용을 위함.)

    set<int> answer_set; // 유효한 숫자를 중복없이 저장하기 위한 set

    do{
        // substr로 1자리 숫자 부터 확인 
        for(int i = 1; i <= numbers.size(); i++){
            int temp_num = stoi( numbers.substr(0, i) );
            if(prime[temp_num]){
                answer_set.insert(temp_num); // set에 넣어서 중복제거 
            }
        } 

    }while( next_permutation(numbers.begin(), numbers.end()) ); 

    return answer_set.size();
}