프로그래머스 42841 - 숫자 야구

문제 링크

접근 및 생각

• baseball을 보고 answer의 후보를 찾는 방법이 힘들어, 그냥 100부터 999까지 탐색해서 주어진 baseball에 알맞은 숫자를 찾는 방법으로 코드를 작성했다.

• baseball에 적절한 숫자인지 판단해주는 함수 check

     // cmp는 비교할 숫자
    bool check(vector<vector<int>> baseball, int cmp){
        for(int i = 0; i < baseball.size(); i++){
            // temp는 baseball에서 주어진 숫자
            int S = 0, B = 0, temp = baseball[i][0];
  
            // 스트라이크 판별
            if((cmp / 100) == (temp / 100))             S++;
            if(((cmp / 10) % 10) == ((temp / 10) % 10)) S++;
            if((cmp % 10) == (temp % 10))               S++;
  
            // 볼 판별
            if((temp / 100) == ((cmp / 10) % 10) || (temp / 100) == (cmp % 10))         B++;
            if(((temp / 10) % 10) == (cmp / 100) || ((temp / 10) % 10) == (cmp % 10))   B++;
            if((temp % 10) == (cmp / 100) || (temp % 10) == ((cmp / 10) % 10))          B++;
  
            // baseball에 적절하지 않은 것이 하나라도 있으면, return false
            if(S != baseball[i][1] || B != baseball[i][2])  return false;
        }
        // baseball에 모두 적절하므로 return true
        return true;
    }

• 100부터 999까지의 탐색 방식을 조금 특이하게 했다.

    int answer = 0;
  
    // i는 100의 자리, j는 10의 자리, k는 1의 자리
    for(int i = 1; i <= 9; i++){
        for(int j = 1; j <= 9; j++){
            for(int k = 1; k <= 9; k++){
                // 야구게임 조건 상 각 자리의 숫자가 겹치면 안된다.
                if(i == j || j == k || k == i)  continue;
  
                int cmp = 100 * i + 10 * j + k;
                if(check(baseball, cmp))  answer++;
            }
        }
    }
    return answer;

코드

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

bool check(vector<vector<int>> baseball, int cmp){
    for(int i = 0; i < baseball.size(); i++){
        int S = 0, B = 0, temp = baseball[i][0];

        if((cmp / 100) == (temp / 100))             S++;
        if(((cmp / 10) % 10) == ((temp / 10) % 10)) S++;
        if((cmp % 10) == (temp % 10))               S++;
        if((temp / 100) == ((cmp / 10) % 10) || (temp / 100) == (cmp % 10))         B++;
        if(((temp / 10) % 10) == (cmp / 100) || ((temp / 10) % 10) == (cmp % 10))   B++;
        if((temp % 10) == (cmp / 100) || (temp % 10) == ((cmp / 10) % 10))          B++;

        if(S != baseball[i][1] || B != baseball[i][2])  return false;
    }
    return true;
}

int solution(vector<vector<int>> baseball) {
    int answer = 0;
    for(int i = 1; i <= 9; i++){
        for(int j = 1; j <= 9; j++){
            for(int k = 1; k <= 9; k++){
                if(i == j || j == k || k == i)  continue;
                int cmp = 100 * i + 10 * j + k;
                if(check(baseball, cmp))  answer++;
            }
        }
    }
    return answer;
}

채점 결과

프로그래머스 42893 - 소수 찾기

문제 링크

생각 및 접근

• 문제부터 소수 찾기. 그렇다면 소수를 체크하는 함수를 작성해야 했다.

    bool chkPrime(int a){
        if(a == 0 || a == 1)  return false;
        for(int i = 2; i <= sqrt(a); i++){
            if(a % i == 0)  return false;
        }
        return true;
    }

  • 함수를 더 최적화하기 위해서 i를 sqrt(a)까지 돌게 했다.

    • 왜? (출처 : Coding Monster님의 OpenTutorials )

        양의 정수 n, a, b에 대해 n = a * b (단, a <= b) 라고 해봅시다. 그러면 a와 b는 n의 약수가 됨을 알 수 있습니다. 
      
        a와 b의 값을 생각해봅시다. a의 최소값은 1이 되며, 이 때 b는 n이 됩니다.
        위의 식이 성립하기 위해서는 a가 점점 커질수록 b는 작아져야 하는 반비례 관계임을 알 수 있습니다. 
      
        위의 식 n=a*b에서 약수 a가 존재하면, 곱해서 n이 되는 짝 b가 항상 존재합니다.
        즉, 모든 약수는 곱해서 n이 되는 쌍이 존재하며, (a, b) 꼴 쌍에서 a <= b라고 할 경우 a의 최대값은 sqrt(n)가 됩니다. 
      
        그 이유는 a <= b 가 성립하는 상태에서 a가 가장 커질 수 있는 경우는 a == b인 경우이고, 이는 n = a * a 꼴이 됩니다.

• string numbers의 숫자들을 하나씩 분리해서 다시 붙이는 작업을 해주어야 하는데, 이를 next_permutation으로 해결하였다. next_permutation를 통해서 나온 배열을 i = 1 .. numbers.size()까지 돌면서 substr 함수를 이용해 0번부터 i개의 string을 잘라낸다. 잘라낸 string을 소수 체크를 하고, 미리 선언해둔 map<int, int> m에 추가시킨다.

  • next_permutation란? 링크
    • 배열을 보고, 조합에 의한 순서대로 순회한다. 내림차순으로 정렬이 될 때까지 반복한다.
  • next_permutation를 사용할 때
    • 배열은 오름차순으로 정렬되어 있어야 한다.

코드

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

bool chkPrime(int a){
    if(a == 0 || a == 1)  return false;
    for(int i = 2; i <= sqrt(a); i++){
        if(a % i == 0)  return false;
    }
    return true;
}

int solution(string numbers) {
    int answer = 0, size = numbers.size();
    map<int, int> m;
    sort(numbers.begin(), numbers.end());

    do{
        for(int i = 1; i <= size; i++){
            string _temp = numbers.substr(0, i);
            int temp = stoi(_temp);
            if(m[temp] == 0 && chkPrime(temp)){
                m[temp]++;
            }    
        }
    }while(next_permutation(numbers.begin(), numbers.end()));

    for(auto k : m){
        if(k.second != 0)
            answer++;
    }
    return answer;
}

채점 결과

프로그래머스 42840 - 모의고사

문제 링크

생각 및 접근

• 문제 갯수만큼 for문을 돌면서, 각 학생의 찍은 답이 정답이라면, 정답 갯수를 늘려주기로 했다.

    for(int i = 0; i < answers.size(); i++){
        if(answers[i] == (std1[i % 5]))   score[1]++;
        if(answers[i] == (std2[i % 8]))   score[2]++;
        if(answers[i] == (std3[i % 10]))  score[3]++;
    }

• answers 순회를 마치고, 학생들 중에서 가장 높은 점수를 기록하고, 그 점수를 얻은 학생을 answer에 push_back 한다.

    int max = *max_element(score + 1, score + 4);
    for(int i = 1; i <= 3; i++){
        if(max == score[i]) answer.push_back(i);
    }

코드

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

vector<int> answer;
int score[4];
int std1[5] = {1, 2, 3, 4, 5};
int std2[8] = {2, 1, 2, 3, 2, 4, 2, 5};
int std3[10] = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};

vector<int> solution(vector<int> answers) {
    for(int i = 0; i < answers.size(); i++){
        if(answers[i] == (std1[i % 5]))   score[1]++;
        if(answers[i] == (std2[i % 8]))   score[2]++;
        if(answers[i] == (std3[i % 10]))  score[3]++;
    }

    int max = *max_element(score + 1, score + 4);
    for(int i = 1; i <= 3; i++){
        if(max == score[i]) answer.push_back(i);
    }

    return answer;
}

채점 결과

프로그래머스 42898 - 등굣길

문제 링크

생각 및 접근

• 초중고 시절 많이 했던 최단거리 구하기 문제를 코딩으로 구현하게 될 줄 몰랐다.
• 최단거리 문제에 대한 정보는 깔끔수학님의 블로그를 참고하자.
• 인덱스 생각 때문에 애먹었는데, 좌표와 행렬 표현의 이질적인 부분 때문이다.

  • 

  • 행렬로 생각하면 집이 [1][1], 학교는 [3][4]여야 하는데,
  • 좌표로 따지면 집이 (1, 1)이라고 하면, 학교의 좌표는 (4, 3)이다.
  • 좌표로 표현한 것들을 행렬로 바꾸려면 x와 y값을 뒤집어주어야 한다!
  • 어떻게 할까 고민하다가, 행렬을 기준으로 생각해서, 좌표인 것들을 뒤집어주기로 했다.
• 좌표를 행렬로 바꾸기
  • 행렬 dp에서 PUDDLE를 넣을 때,

      for(auto k : puddles)   dp[k[1]][k[0]] = PUDDLE;

    와 같이 하였다.
  • 행렬 dp의 첫번째 인덱스의 끝은 m, 행렬 dp의 두번째 인덱스의 끝은 n으로 하였다.
  • solution 함수의 반환값 또한 dp[n][m]
• dp의 초깃값 잡기

    for(auto k : puddles)   dp[k[1]][k[0]] = PUDDLE;
    for(int i = 1; i <= m; i++){
        if(dp[1][i] == PUDDLE)  break;
        dp[1][i] = 1;
    }
    for(int i = 1; i <= n; i ++){
        if(dp[i][1] == PUDDLE)  break;
        dp[i][1] = 1;
    }

• dp 계산

    for(int i = 2; i <= n; i++){
        for(int j = 2; j <= m; j++){
            if(dp[i][j] == PUDDLE)  continue;
            if(dp[i - 1][j] != PUDDLE)  dp[i][j] += dp[i - 1][j];
            if(dp[i][j - 1] != PUDDLE)  dp[i][j] += dp[i][j - 1];
            dp[i][j] %= 1000000007;
        }
    }

코드

#include <bits/stdc++.h>
#define PUDDLE -1
using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    vector< vector<int> > dp(n + 1, vector<int>(m + 1, 0));
    for(auto k : puddles)   dp[k[1]][k[0]] = PUDDLE;
    for(int i = 1; i <= m; i++){
        if(dp[1][i] == PUDDLE)  break;
        dp[1][i] = 1;
    }
    for(int i = 1; i <= n; i ++){
        if(dp[i][1] == PUDDLE)  break;
        dp[i][1] = 1;
    }

    for(int i = 2; i <= n; i++){
        for(int j = 2; j <= m; j++){
            if(dp[i][j] == PUDDLE)  continue;
            if(dp[i - 1][j] != PUDDLE)  dp[i][j] += dp[i - 1][j];
            if(dp[i][j - 1] != PUDDLE)  dp[i][j] += dp[i][j - 1];
            dp[i][j] %= 1000000007;
        }
    }

    return dp[n][m];
}

채점 결과

프로그래머스 43105 - 정수 삼각형

문제 링크

생각 및 접근

• 정수 삼각형을 배열 형태로 숫자를 작성해보면 다음과 같다.
  

  

• 삼각형의 맨 윗 층부터 내려오면서, vector<vector<int>> t에 t[i][j]까지 검사했을 때, 최댓값이 들어오게끔 DP 방식 코드를 짜고자 했다.
• 검사하는 방식은 이렇다.
  

  

  • 화살표를 하나만 받는 원소와 화살표를 두 개 받는 원소를 나눴다.
    • 화살표 하나만 받는 원소 : 각 층의 양 끝
    • 화살표 두 개 받는 원소 : 양 끝을 제외한 나머지
      • max 함수를 사용해서 두 가지중 큰 것을 t[i][j]에 더해주면 된다.

코드

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

int solution(vector<vector<int>> t) {
    for(int i = 1; i < t.size(); i++){
        for(int j = 0; j < t[i].size(); j++){
            if(j == 0)                      t[i][j] += t[i - 1][j];
            else if(j == t[i].size() - 1)   t[i][j] += t[i - 1][j - 1];
            else                            t[i][j] += max(t[i - 1][j - 1], t[i - 1][j]);
        }
    }

    int answer = -1;
    for(auto d : t[t.size() - 1]){
        if(d > answer)  answer = d;
    }
    return answer;
}

채점 결과

프로그래머스 43104 - 타일 장식물

문제 링크

생각 및 접근

• 우선, 정사각형의 갯수에 따라 정사각형의 길이가 얼마나 길어지는지 살펴보아야 한다.

  • 1, 1, 2, 3, 5, 8, ...
  • 누가 봐도 이건 피보나치 수열이다.

• 문제에서 N이 주어지면, 일단 피보나치 수열을 통해 정사각형 길이를 구하고, 그 값을 토대로 직사각형의 길이를 구하면 된다.
  

  

• 직사각형 길이는 점화식으로 나타내면 length(n) = 4 * square(n) + 2 * square(n - 1)이 된다.

코드

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

long long tiles[81];

long long dp(int N){
    if(N == 1 || N == 2)    return tiles[N] = 1;
    else if(tiles[N] == 0)  return tiles[N] = dp(N - 1) + dp(N - 2);
    else                    return tiles[N];
}

long long solution(int N) {
    return 4 * dp(N) + 2 * dp(N - 1);
}

채점 결과

프로그래머스 42895 - N으로 표현

문제 링크
멍토 님의 IT블로그 게시글을 참고하였습니다.

생각 및 접근

• 문제 분야는 DP에 있었지만, 문제 접근은 DFS밖에 떠오르지 않았다.
• DFS로 접근하려고 했지만, dfs로 탐색해야 될 것이 너무 많았다. 예로 들어, 숫자를 합쳐서 계산하는 경우 모두를 dfs로 고려하려고 하니 쉽지 않았다.
• 구글링을 통해 멍토 님의 IT블로그를 참조하여 문제를 풀고, 이해할 수 있었다.
• DFS의 포인트는
  • DFS 함수의 파라미터로 무엇을 넘기고 넣을 것인가 ,
  • DFS의 초깃값을 어떻게 잡을 것인가 ,
  • 언제 DFS를 멈추게 할 것인가 ,
  • DFS 함수 내에서 새 DFS 함수를 호출할 때 문제의 조건에 맞게 적절히 호출하는가

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

• 숫자를 몇 개 사용했는지 세는 int count와 count까지 오면서 계산한 int currentNumber를 넘긴다.

    void dfs(int count, int currentNumber);

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

```
dfs(0, 0);
```

언제 DFS를 멈추게 할 것인가

• count가 8보다 크면 답으로 인정하지 않고, 탐색을 멈춰야 한다.

    if(count >= 9)  return;

• currentNumber == num이라면, 정답을 찾은 것이므로 탐색을 멈추고, answer를 업데이트한다.

    if(currentNumber == num){
        answer = min(answer, count);
        return;
    }

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

• 수많은 DFS를 반복문에 의해 처리된다.

  int tempNumber = 0;
  for(int i = 0; i + count < 9; i++){
    tempNumber = tempNumber * 10 + n;
    dfs(count + 1 + i, currentNumber + tempNumber);
    dfs(count + 1 + i, currentNumber - tempNumber);
    dfs(count + 1 + i, currentNumber * tempNumber);
    dfs(count + 1 + i, currentNumber / tempNumber);
  }

• i의 역할

  • n을 i번 붙여낸다. 즉, "nnn... n" (n이 i번) 라는 형태이다.

• i + count < 9

  • count가 9가 넘으면 더이상 DFS를 하지 않으니, 굳이 DFS를 하지 않고 for문 선에서 잘라낸다.

• dfs(count + 1 + i, currentNumber ? tempNumber);

  • n을 i번 붙인만큼, n을 i번 사용한 것이므로 count + 1 + i
  • ?는 사칙연산

코드

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

int n, num, answer = 9;

void dfs(int count, int currentNumber){
    if(count >= 9)  return;
    if(currentNumber == num){
        answer = min(answer, count);
        return;
    }

    int tempNumber = 0;
    for(int i = 0; i + count < 9; i++){
        tempNumber = tempNumber * 10 + n;
        dfs(count + 1 + i, currentNumber + tempNumber);
        dfs(count + 1 + i, currentNumber - tempNumber);
        dfs(count + 1 + i, currentNumber * tempNumber);
        dfs(count + 1 + i, currentNumber / tempNumber);
    }
}

int solution(int N, int number) {
    n = N;
    num = number;
    dfs(0, 0);
    if(answer == 9) return -1;
    return answer;
}

채점 결과

프로그래머스 43164 - 여행경로

문제 링크

접근 및 생각

• 문제는 DFS 방식으로 풀이하였다. 왜냐하면 알파벳 순서에 대한 처리가 필요했기 때문이다.
  • DFS에 대한 설명은 (링크)를 참조.
  • DFS란 깊이 우선 탐색으로써 일단 깊게 들어가서 leaf node에 닿아, 탐색한 경로가 답에 걸맞기만 하면 그걸 쓰면 된다.
  • 이 점을 사용해서, 미리 tickets를 알파벳 순서로 배열을 한 뒤에 DFS하기로 했다_ .
  • 미리 tickets를 알파벳 순서로 배열을 한 뒤에 DFS를 하면, 제일 빨리 찾은 답이 알파벳 순서가 맞는 답일 것이다.
  • tickets를 나열하는 cmp 함수

      // 티켓의 시작 주소 오름차순이 1순위, 티켓의 도착 주소 오름차순이 2순위
      bool cmp(vector<string> a, vector<string> b){
          if(a[0] == b[0]){
              return a[1] < b[1];
          }
          return a[0] < b[0];
      }

• DFS의 포인트는
  • DFS 함수의 파라미터로 무엇을 넘기고 넣을 것인가 ,
  • DFS의 초깃값을 어떻게 잡을 것인가 ,
  • 언제 DFS를 멈추게 할 것인가 ,
  • DFS 함수 내에서 새 DFS 함수를 호출할 때 문제의 조건에 맞게 적절히 호출하는가

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

• 여러 경우의 수가 있겠지만, 필자는 이제까지 이동한 경로를 넣었다.

    void dfs(vector<string> path);

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

• 시작 도시는 ICN이다.

    dfs({"ICN"});

언제 DFS를 멈추게 할 것인가

• 반환되는 벡터의 크기는 늘 tickets 벡터 크기 + 1이므로, path 벡터 크기가 tickets 벡터 크기 + 1 이라면 DFS를 멈춘다.

    if(path.size() == t.size() + 1){
        if(answer.empty()){
            answer = path;
        }
    }

• 또한, 가장 먼저 찾은 경로를 answer로 쓸 것이기 때문에 다음과 같은 코드를 추가하였다.

    if(!answer.empty()) return;

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

• 아직 사용하지 않은 티켓이고, path의 마지막 원소가 티켓의 시작 주소라면, 그 티켓을 탐색할 수 있다.

    for(int i = 0; i < t.size(); i++){
        if(used[i] == 0 && temp == t[i][0]){
            used[i] = 1;
            path.push_back(t[i][1]);
            dfs(path);
            used[i] = 0;
            path.pop_back();
        }
    }

코드

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

vector<vector<string>> t;
vector<int> used;
vector<string> answer;

bool cmp(vector<string> a, vector<string> b){
    if(a[0] == b[0]){
        return a[1] < b[1];
    }
    return a[0] < b[0];
}

void dfs(vector<string> path){
    if(!answer.empty()) return;

    string temp = path[path.size() - 1];
    if(path.size() == t.size() + 1){
        if(answer.empty()){
            answer = path;
        }
    }
    else{
        for(int i = 0; i < t.size(); i++){
            if(used[i] == 0 && temp == t[i][0]){
                used[i] = 1;
                path.push_back(t[i][1]);
                dfs(path);
                used[i] = 0;
                path.pop_back();
            }
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {
    t = tickets;
    used.assign(t.size(), 0);
    sort(t.begin(), t.end(), cmp);
    dfs({"ICN"});
    return answer;
}

채점 결과