[~0718] 알고리즘

  어쩌다 보니 '프로그래머스'에서 잠시 코딩 테스트 연습을 했었다. 짧은 시간 동안 우다다다 풀은 것이라 조금 난잡하지만 이왕 풀어본 거 이곳에 정리해두기로 했다.

 

  이하의 문제들은 거의 대부분 코딩테스트 고득점 Kit 속 문제들이다.

---

기능개발

 

  반복문을 돌면서 진도를 나타내는 progresses 벡터에 작업 속도를 더한다. 배포는 progresses에 들어있는 순서대로 진행되기 때문에, 큐의 front 역할을 할 변수 i를 두어 다음에 배포될 기능이 몇 개인지 확인한다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    
    int i = 0, numOfPro = 0;
    
    while (numOfPro != progresses.size())
    {
        for (int j = i; j < progresses.size(); j++)
        {
            progresses[j] += speeds[j];
        }
        
        int num = 0;
        //배포
        for (; i < progresses.size(); i++)
        {
            if (progresses[i] >= 100)
            {
                num++;
            }
            else if (progresses[i] < 100) break;
        }
        
        if (num != 0) answer.push_back(num);
        
        numOfPro += num;        
    }
    
    return answer;
}

 

 

주식가격

 

  모든 가격들이 어느 시점부터 떨어지는지를 확인하기 위해 2중 for문을 사용하여 탐색했다. 비교를 수행하다가 가격이 떨어지면 얼마만큼 가격이 떨어지지 않고 유지되었는지를 벡터에 넣어 기록.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    
    for (int i = 0; i < prices.size(); i++)
    {
        int num = 0;
        for (int j = i + 1; j < prices.size(); j++)
        {            
            if (prices[i] <= prices[j]) num++;
            else
            {
                num++;
                break;
            }
        }
        answer.push_back(num);
    }
    
    return answer;
}

 

 

K번째 수

 

  문제를 해결하기 위해선

1. 주어진 array를 자른다.
2. 잘라낸 배열을 오름차순으로 정렬한다.
3. 정렬한 배열 속에서 K번째 수를 찾는다.

를 수행해야 한다. 해당 조건들이 들어있는 commands 배열에서 배열을 자를 구간을 받고, for문을 통해 잘린 배열을 구한다. 잘라낸 배열을 sort로 정렬한 후 K번째 수를 찾으면 끝.

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

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    vector<int> arr;
    
    for (int i = 0; i < commands.size(); i++)
    {
        vector<int> arr;
        for (int j = commands[i][0]; j <= commands[i][1]; j++)
        {
            arr.push_back(array[j - 1]);
        }
     
        sort(arr.begin(), arr.end());
        answer.push_back(arr[commands[i][2] - 1]);        
    }    
    
    return answer;
}

 

 

H-Index

 

  코딩보다 문제 이해... 가 더 어려웠던 문제(ㅜㅠ). H-index에 대한 설명이 문제 지문으로는 충분하지 않기 때문에 꼭 링크된 위키피디아 문서를 읽어봐야 한다... 일단 어떻게든 이해하면 구현 자체는 간단하다.

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

using namespace std;

bool decrease(int a, int b) {
    return b < a;
}

int solution(vector<int> citations) {
    int answer = 0;
    
    sort(citations.begin(), citations.end(), decrease); //정렬
    
    for (int i = 0; i < citations.size(); i++)
    {
        if (citations[i] >= i + 1)
            answer++;
        else break;
    }
    
    return answer;
}

 

 

카펫

 

  완전탐색 문제. 크게 생각할 필요 없이 노란색 격자의 수를 기준으로 반복문을 돌며 가능한 가로와 세로 길이를 구한다. 카펫의 가로 길이가 세로 길이와 같거나 길다는 조건도 고려.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    //i는 세로 길이
    //무조건 가로로 긴 직사각형이거나 정사각형
    for (int i = 1; i <= yellow; i++)
    {
        if (yellow % i == 0)
        {
            int num = yellow / i; //가로길이
            if (num < i) break;
            
            int num2 = (num + 2) * 2 + (i * 2);
            
            if (num2 == brown)
            {
                answer.push_back(num + 2);
                answer.push_back(i + 2);
            }
        }
    }
    
    return answer;
}

 

 

타겟 넘버

 

  평범하게 DFS로 푼 문제. 그래서일까 코드도 딱히 특별한 점은 없다(...).

#include <string>
#include <vector>

using namespace std;

int answer = 0;

void DFS(vector<int> numbers, int idx, int sum, int target);

int solution(vector<int> numbers, int target) {

    DFS(numbers, 0, 0, target);
    
    return answer;
}

void DFS(vector<int> numbers, int idx, int sum, int target)
{
    if (idx == numbers.size())
    {
        if (sum == target) answer++;
    }
    else
    {
        DFS(numbers, idx + 1, sum + numbers[idx], target);
        DFS(numbers, idx + 1, sum - numbers[idx], target);
    }    
}

 

 

네트워크

 

  앞의 문제와 비슷하지만, 이 문제의 경우 지나온 길을 다시 지나게 하지 않기 위해 방문 여부를 표시하는 visit 벡터를 사용했다.

#include <string>
#include <vector>

using namespace std;
int answer = 0;

void DFS(int n, int idx, vector<bool> &visit, vector<vector<int>> computers);

int solution(int n, vector<vector<int>> computers) {
    vector<bool> visit;
    for (int i = 0; i < n; i++)
    {
        visit.push_back(false);
    }
        
    for (int i = 0; i < n; i++)
    {
        if (!visit[i])
        {
            DFS(n, i, visit, computers);
            answer++;
        }
    }
    
    return answer;
}

void DFS(int n, int idx, vector<bool> &visit, vector<vector<int>> computers)
{
    visit[idx] = true;
    
    for (int i = 0; i < n; i++)
    {
        if (!visit[i] && computers[idx][i] == 1) DFS(n, i, visit, computers);
    }
}

 

 

크레인 인형뽑기 게임

 

  어쩐지 귀여워보이는 문제라(ㅎㅎ) 풀어본 문제. 이건 평소와 달리 Javascript로 풀었다. 문제는 무난한데 내 경우 0도 뽑은 인형 스택에 넣어버림 + 그 0들끼리 같은 인형으로 처리되어서 답이 잘못 나온 해프닝이 있었다. 뽑은 인형이 0인지를 검사하도록 if문을 넣어서 해결.

function solution(board, moves) {
    var answer = 0;
    var stack = [];
    
    for (var i = 0; i < moves.length; i++) {
        var target = moves[i] - 1;
        for (var j = 0; j < board.length; j++) {            
            if (board[j][target] !== 0) {
                stack.push(board[j][target]);
                board[j][target] = 0;
                break;
            }
        }
        
        //같은 인형은 사라짐
        if (stack.length !== 0 && stack[stack.length - 1] === stack[stack.length - 2]) {
            answer += 2;
            stack.pop();
            stack.pop();
        }        
    }    
    return answer;
}

 

 

문자열 압축

 

  문자열을 어떻게 압축해야 최소 길이가 나오는지 구하는 문제. 이 문제 또한 Javascript로 해결하였다. Javascript의 substr 함수를 이용하여 문자열을 자르고, 문자열이 얼마만큼 반복되는지 반복 횟수를 구한다. 반복이 끝나면 반복 횟수와 반복된 문자를 정답이 될 문자열(ansArr) 뒤에 더한다.

 

  문자열인데 변수 이름이 저런 이유는... 처음엔 배열 안에 문자를 넣었기 때문이다. 그런데 답이 제대로 나오지 않아서 그냥 문자열에 더하는 방식으로 변경했다. 이게 훨씬 더 편해서 처음부터 이렇게 하면 좋았을걸... 싶었다.

function solution(s) {
    var answer = s.length;
    
    var sum = 0;
    
    for (var i = 1; i <= (s.length / 2); i++) {
        let ansArr = "";
        let str = s.substr(0, i);
        let num = 1;
        for (var j = i; j < s.length; j += i) {
            if (str === s.substr(j, i)) {
                num++;
            }
            else { //다를 경우 
                if (num !== 1) {
                    ansArr += num.toString();
                }
                ansArr += str;
                num = 1;
            }
            str = s.substr(j, i);
            
        }

        if (num !== 1) {
            ansArr += num.toString();
        }
        ansArr+= str;
        
        sum = ansArr.length;
        
        if (sum < answer) answer = sum;
    }
    
    return answer;
}

---

  프로그래머스를 사욯해보는 건 이번이 처음인데, 개인적으로는 에디터가 백준보다 편해서 좋았다. 다만 문제 수나 전체적인 활성도...? 나 사용도가 백준보다 좀 낮은감이 없지않아 있었던 편. 그렇지만 기업에서 코딩 테스트를 여기에서 진행하기도 하는 만큼 이런저런 문제를 풀어보는 것도 나쁘지 않을 것 같다.