프로그래머스 43163 - 단어 변환

문제 링크

생각 및 접근

• BFS는 최단거리를 보장한다. 이 문제는 begin에서 target으로 변환 가능한 최소 경로를 구하는 것이므로, BFS로 접근하려고 했다.
• BFS는 코드로 구현할 때 다음과 같은 요소를 고려하여야 한다.
  • queue의 데이터 타입
  • queue의 초깃값
  • q.front() 원소가 답이 될 수 있는지, 혹은 정보 update가 가능한지 check 이후 행동
  • 읽어온 원소로부터 queue에 push할 수 있는 원소를 push 하기

queue의 데이터 타입

• BFS를 하면서 탐색한 횟수 int, 현재 변환된 상태 string을 pair로 선언하였다.

    queue< pair<string, int> > q;

  queue의 초깃값

  q.push(make_pair(begin, 0));

q.front() 원소가 답이 될 수 있는지, 혹은 정보 update가 가능한지 check 이후 행동

• string temp = q.front().first가 target과 같다면, 최소 경로를 찾은 것이므로 return q.front().second;

읽어온 원소로부터 queue에 push할 수 있는 원소를 push 하기

• words를 모두 순회하여 아래 조건에 해당하는 원소를 push하고, visit를 체크.
  • 아직 방문하지 않았고, visit\[i\]
  • temp와 words[i]를 비교해서 변환이 가능하다면 chk1diff(temp, words[i])

      bool chk1diff(string a, string b){
          int cnt = 0;
          for(int i = 0; i < a.length(); i++){
              if(a[i] != b[i]) cnt++;
          }
          if(cnt == 1)    return true;
          return false;
      }

코드

#include <bits/stdc++.h>
using namespace std;

bool chk1diff(string a, string b){
    int cnt = 0;
    for(int i = 0; i < a.length(); i++){
        if(a[i] != b[i]) cnt++;
    }
    if(cnt == 1)    return true;
    return false;
}

int answer = 0, visit[50];
queue< pair<string, int> > q;

int solution(string begin, string target, vector<string> words) {
    q.push(make_pair(begin, 0));
    while(!q.empty()){
        string temp = q.front().first;
        int cnt = q.front().second;
        q.pop();

        if(temp == target){
            return cnt;
        }

        for(int i = 0; i < words.size(); i++){
            if(visit[i] != 0) continue;
            else{
                if(chk1diff(temp, words[i])){
                    visit[i] = 1;
                    q.push(make_pair(words[i], cnt + 1));
                }
            }
        }
    }
    return 0;
}

채점 결과

프로그래머스 43162 - 네트워크

문제 링크

접근 및 생각

사족

• 프로그래머스의 대부분 풀이들은 DFS 방식이였지만, 내가 이 문제를 처음 접근할 때 BFS 방식이 먼저 떠올라서 BFS 방식으로 풀게 되었다.

본론

• BFS에 관한 내용은 (링크)를 참조
• BFS는 큐를 활용하는 탐색 방식으로, 코드로 구현할 때 다음과 같은 요소를 고려하여야 한다.
  • queue의 데이터 타입
  • queue의 초깃값
  • q.front() 원소가 답이 될 수 있는지, 혹은 정보 update가 가능한지 check 이후 행동
  • 읽어온 원소로부터 queue에 push할 수 있는 원소를 push 하기

queue의 데이터 타입

• queue가 기억해야 할 것은 computers의 index 값이므로 queue<int> q;

queue의 초깃값

• 일단 computers의 0번 index부터 탐색할 것이므로 q.push(0); visit[0] = answer;
• 그리고 computers의 index를 탐색했는 지 기억하기 위해 int visit[200]; 선언

읽어온 원소로부터 queue에 push할 수 있는 원소를 push 하기

• computers[q.front()][i = 0..n] 을 탐색해서,
  • q.front()와 연결되어 있고, (computers[i][temp] == 1)
  • 아직 방문하지 않았다면, (visit[i] == 0)
    q.push();

q.front() 원소가 답이 될 수 있는지, 혹은 정보 update가 가능한지 check 이후 행동

• 정보 update가 가능한 시점
  • 더이상 탐색할 수 있는 원소가 없는 경우 한 네트워크를 다 찾은 것이므로, (if(q.empty()))
  • 다른 네트워크를 찾아야 한다.

      for(int i = 0; i < n; i++){
          if(visit[i] == 0){
              q.push(i);
              visit[i] = ++answer;
              break;
          }
      }

  • 위 과정을 거쳐도 추가된 원소가 없다면 (즉, 모든 컴퓨터를 탐색했다면) , return answer

코드

#include <bits/stdc++.h>
using namespace std;

queue<int> q;
int visit[200], answer = 1;

int solution(int n, vector<vector<int>> computers) {    
    q.push(0);
    visit[0] = answer;
    while(-1){
        if(q.empty()){
            for(int i = 0; i < n; i++){
                if(visit[i] == 0){
                    q.push(i);
                    visit[i] = ++answer;
                    break;
                }
            }
            if(q.empty())   return answer;
        }

        int temp = q.front();
        q.pop();

        for(int i = 0; i < n; i++){
            if(i == temp) continue;
            else if(computers[i][temp] == 1 && visit[i] == 0){
                q.push(i);
                visit[i] = answer;
            }
        }
    }
}

채점 결과

프로그래머스 43165 - 타겟 넘버

문제 링크

생각 및 접근

• 문제를 보자마자 아주 전형적인 DFS 문제구나. 라고 딱 떠올랐다.
  • DFS에 대한 설명은 (링크)를 참조.
• DFS의 포인트는
  • DFS 함수의 파라미터로 무엇을 넘기고 넣을 것인가 ,
  • DFS의 초깃값을 어떻게 잡을 것인가 ,
  • 언제 DFS를 멈추게 할 것인가 ,
  • DFS 함수 내에서 새 DFS 함수를 호출할 때 문제의 조건에 맞게 적절히 호출하는가
    로 나눠볼 수 있겠다.

DFS 함수의 파라미터로 무엇을 넘기고 넣을 것인가

• DFS 탐색할 때 depth == numbers.size()까지 탐색해야 하므로 파라미터 level을 넘길 것이다.
• DFS 탐색할 때 (DFS 결과 총 합) == target이 되면 answer++해주어야 하므로 DFS 결과 총 합을 나타내는 파라미터 result를 넘길 것이다.

DFS의 초깃값을 어떻게 잡을 것인가

dfs(0, 0);

언제 DFS를 멈추게 할 것인가

if(level == nums.size()){
    // ...
}

DFS 함수 내에서 새 DFS 함수를 호출할 때 문제의 조건에 맞게 적절히 호출하는가

// + 하는 경우
dfs(level + 1, result + nums[level]);
// - 하는 경우
dfs(level + 1, result - nums[level]);

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> nums;
int answer = 0, tar;

void dfs(int level, int result){
    if(level == nums.size()){
        if(result == tar){
            answer++;
        }
    }
    else{
        dfs(level + 1, result + nums[level]);
        dfs(level + 1, result - nums[level]);
    }
}

int solution(vector<int> numbers, int target) {
    tar = target;
    nums = numbers;

    dfs(0, 0);
    return answer;
}

채점 결과

프로그래머스 42747 - H-Index

문제 링크

생각과 접근

// 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고,
// 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

• 일단 위 H-Index에 대해 잘 이해해야 했고, 어떤 방식으로 탐색하면 효율적인지 생각했다.
• h번 이상 인용된 논문이 h편 이상 에 주목하여,
  • h를 어떻게 찾을까. h번 이상 인용된 논문 의 h 를 찾기보단 h편 이상 의 h 를 찾는 것에 중점을 두었다. 전자를 찾으려면 탐색 류의 알고리즘을 사용해야 될 것 같은데, 그러기엔 너무 까다롭게 접근하는 듯 했다. 후자를 찾으려면 인용 횟수가 많은 논문부터 탐색하면 쉽게 찾을 수 있을 것 같았다.
  • 문제에서 주어지는 citations를 내림차순으로 정렬하여 인용 횟수가 많은 논문부터 탐색하기로 하였다.
• 인용 횟수가 많은 논문을 탐색하면서, answer를 하나씩 늘려간다. 그러다 answer보다 더 낮은 인용 횟수를 가진 논문이 나오면, 그 answer를 반환하면 된다.

코드

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> citations) {
    int answer = 0;

    sort(citations.rbegin(), citations.rend());
    for(auto c : citations){
        if(answer + 1 > c)  break;
        answer++;
    }
    return answer;
}

채점 결과

프로그래머스 42746 - 가장 큰 수

문제 링크

생각과 접근

• 이어 붙여서 가장 큰 수를 만드는 문제다.
• 어떤 기준으로 string을 sort해야 이어 붙여서 가장 큰 수를 만들 수 있을까?
  • 실제로 이어 붙여서 비교해보면 된다.

      bool compare(string a, string b){
          return a + b > b + a;
      }

  • 처음 보는 compare 함수 형태라 당황했지만, 꼭 기억해야 하는 compare함수라고 생각된다.

코드

#include <bits/stdc++.h>
using namespace std;

bool compare(string a, string b){
    return a + b > b + a;
}

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> v;

    for(int i = 0 ; i < numbers.size(); i++){
        v.push_back(to_string(numbers[i]));
    }
    sort(v.begin(), v.end(), compare);

    for(int i = 0; i < v.size(); i++){
        if(answer.empty() && v[i] == "0"){
            answer = "0";
            break;
        }
        answer.append(v[i]);
    }
    return answer;
}

채점 결과

프로그래머스 42748 - K번째수

문제 링크

생각 및 접근

• index와 실제 배열에 저장되는 index가 1씩 차이나서 귀찮았던 문제.
• vector temp를 선언해서 array를 새로 담고, commands에서 시키는 대로 원하는 구간을 sort 후, 원하는 답을 answer에 push_back하면 끝나는 문제

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> temp;
    vector<int> answer;

    for(int i = 0; i < commands.size(); i++){
        temp = array;
        sort(temp.begin() + commands[i][0] - 1, temp.begin() + commands[i][1]);
        answer.push_back(temp[(commands[i][0] - 1) + (commands[i][2] - 1)]);
    }

    return answer;
}

채점 결과

프로그래머스 42587 - 프린터

문제 링크

생각과 접근

사족

• 문제 이해를 잘 해야 삽질하지 않는다는 교훈을 얻은 문제.

    // 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
    // 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
    // 3. 그렇지 않으면 J를 인쇄합니다.

• 처음 잘못 이해했을 때 2번 조건에서 J보다 중요도가 높은 문서가 존재하면, 그 문서를 인쇄하는 것으로 이해해서 삽질을 했다.

본론

• queue< pair<int, int> > q;
  • 큐를 사용해서 문제를 풀었다.
  • 큐를 pair를 이용해서 왼쪽에는 index, 오른쪽에는 priorities[index]를 저장하였다.
• 무한루프
  • J에 해당하는 것 q.front() 을 pop한다. (편의상 J라고 부르겠음.)
  • J를 제외한 큐를 순회해서 J의 우선순위보다 높은 원소를 찾는다.
    • 우선순위가 높은 원소가 없다면, J를 인쇄해야 한다.
      • 문제의 답은 location에 해당하는 문서의 인쇄 순서를 찾는 것이므로, J의 인덱스와 location이 일치하는지 확인한다.
        • 일치한다면, 답을 찾은 것이므로 return answer;
        • 일치하지 않는다면, 아무것도 하지 않는다. (이미 J는 pop 되었기 때문에 추가적인 작업이 필요하지 않는다.)
    • 우선순위가 높은 원소가 있다면, J를 큐의 가장 마지막에 넣어야 한다.
      • 우선순위가 높은 원소가 있다는 것을 flag에 저장하였음
      • 큐 순회가 끝나고 나면 J를 push한다.

코드

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;

    queue< pair<int, int> > q;
    for(int i = 0; i < priorities.size(); i++){
        q.push(make_pair(i, priorities[i]));
    }

    while(-1){
        bool flag = true;
        int idx = q.front().first;
        int pri = q.front().second;
        q.pop();

        int size = q.size();
        for(int i = 0; i < size; i++){
            int _idx = q.front().first;
            int _pri = q.front().second;
            q.pop();

            if(pri < _pri){
                flag = false;
            }
            q.push(make_pair(_idx, _pri));
        }

        if(flag == false){
            q.push(make_pair(idx, pri));
        }
        else{
            answer++;
            if(idx == location){
                return answer;
            }
        }
    }
}

채점 결과

프로그래머스 42583 - 다리를 지나는 트럭

문제 링크

생각 및 접근

• 문제의 접근은 이렇게 했습니다.
  • 시간을 1초씩 늘려가는 while문을 돌려야겠다.
  • while문을 돌면서 다리 위를 건너는 트럭의 남은 다리 길이를 1씩 줄여야겠다.
  • 다리 위를 건너는 트럭을 큐에 저장해야겠다.
• queue< pair<int, int> > crossing
  • 다리 위를 지나가는 트럭을 저장하는 큐에는 트럭의 무게와 트럭의 남은 다리 길이를 저장해야 했습니다.
  • pair의 왼쪽은 트럭의 무게를, pair의 오른쪽은 트럭의 남은 다리 길이를 저장했습니다.
  • 큐를 순회하면서, 길이를 하나씩 줄여줍니다. 길이가 1이였다면, 그 트럭은 다리를 지난 트럭이 되므로 다리 위 전체 트럭의 무게를 저장하고 있던 onWeight에서 트럭의 무게를 빼줍니다.
• 트럭을 큐에 넣는 조건
  • 대기하고 있는 트럭이 있고,
  • 대기하고 있는 트럭의 무게 + onWeight가 다리 최대 무게를 넘지 않아야 합니다.
• 무한루프를 빠져나오는 조건
  • 더이상 대기하고 있는 트럭이 없고,
  • 다리를 지나고 있는 트럭 또한 없으면 됩니다.
• 시간을 저장하는 변수 answer
  • while문이 끝나기 전에 answer++; 해줍니다.

코드

#include <bits/stdc++.h>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0, onWeight = 0, waitingIndex = 0;
    queue< pair<int, int> > crossing;

    while(-1){
        int crossingNum = crossing.size();

        for(int i = 0; i < crossingNum; i++){
            int wei = crossing.front().first;
            int len = crossing.front().second;
            crossing.pop();

            if(len <= 1){
                onWeight -= wei;
                continue;
            }
            crossing.push(make_pair(wei, len - 1));
        }

        if(waitingIndex < truck_weights.size() && onWeight + truck_weights[waitingIndex] <= weight){
            crossing.push(make_pair(truck_weights[waitingIndex], bridge_length));
            onWeight += truck_weights[waitingIndex];
            waitingIndex++;
        }

        answer++;

        if(waitingIndex >= truck_weights.size() && crossing.empty())
            break;
    }    
    return answer;
}

채점 결과