JArchive 프로그래밍 일기

Staircase

HackerRank Algorithm Warmup

계단처럼 '#'을 찍는 문제다. 별찍기 문제랑 비슷하다.

line 0 : ' ' space 3개 + '#' 1개

line 1 : ' ' space 2개 + '#' 2개

line 2 : ' ' space 1개 + '#' 3개

내코드는 for문을 3개 써서 풀었는데. 다른 분 코드가 인상깊어서 덧붙인다.

내 코드

void staircase(int n) {

    int len = n;

    for (int i = len-1; i >=0; i--) {

        for (int j = 0; j < i; j++) {
            cout << ' ';
        }

        for (int k = 0; k < len - i; k++) {
            cout << '#';
        }
        cout << '\n';
    }

}

다른 분 코드

void staircase(int n) {
    for(int i = 1 ; i <= n ; i++){
        string h(i, '#');
        string s(n-i, ' ');
        cout << s << h <<'\n';
 }

문제

정수 제곱근 판별 프로그래머스 level1

리뷰

양의 정수 x의 제곱이 아니라면, sqrt() 결과가 실수가 된다.

따라서 정수로 나오는지 실수로 나오는지 구분해야 한다.

// 제곱근을 long long 으로 형변환 한 것과 비교  
sqrt(n) - (long long)sqrt(n)

제곱할 때는 pow() , 제곱근 구하는 sqrt() 가 있다.

pow 도 자료형에 따라 몇 개 더 있으니 정리했다.

#include <cmath>

// x의 y승을 계산하는 pow() 

double pow(double x, double y); // 밑수x, 멱수y 순으로 매개변수 넣기 
float powf(float x, float y);
long double powl(long double x, long double y);

/*
float 4bytes, double 8bytes, long double 8bytes 
*/

내 코드

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

long long solution(long long n) {
    long long answer = -1;  // 양의 정수 x의 제곱이 아니라면 -1 

    if ( (sqrt(n) - (long long)sqrt(n)) == 0) {
        answer = pow(sqrt(n) + 1, 2);
    }

    return answer;
}

다른 사람의 코드

#include <string>
#include <vector>
#include <math.h>
using namespace std;

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

    return powl(answer, 2) == n ? powl(answer + 1, 2) : -1;
}

문제

정수 내림차순으로 배치하기 프로그래머스 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;
}

문제

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;
}