programmers.co.kr/learn/courses/30/lessons/77484

 

코딩테스트 연습 - 로또의 최고 순위와 최저 순위

로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호

programmers.co.kr

<풀이>

1. 민우의 로또 번호와, 당첨 로또 번호를 입력받는다.

2. 민우의 로또 번호가 될 수 있는 최고 순위와 최저 순위를 반환한다.

 

<해법>

1. 최고 순위와 최저 순위를 계산하는 방법.

=>

최고 순위 : 보이는 숫자의 맞은 갯수 + 낙서된 숫자가 다 맞은 경우

최저 순위 : 보이는 숫자만 다 맞은 경우

각각 경우에 맞게 맞은 갯수를 센 다음에 순위를 계산합니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
//순위 계산 함수
int ranking(int count) {
    switch (count) {
    case 6:
        return 1;
    case 5:
        return 2;
    case 4:
        return 3;
    case 3:
        return 4;
    case 2:
        return 5;
    default:
        return 6;
    } 
}
 
vector<int> solution(vector<int> lottos, vector<int> win_nums) {
 
    //선언
    int hitCount, zeroCount;
    vector<int> answer;
 
    //초기화
    hitCount = 0, zeroCount = 0;
 
    /* 해법 */
    //1. 맞힌 갯수와 낙서된 갯수 찾기
    for (int i = 0; i < lottos.size(); i++) {
        if (lottos[i] == 0) {
            zeroCount++;
        }
        else {
            for (int j = 0; j < win_nums.size(); j++) {
                if (lottos[i] == win_nums[j]) {
                    hitCount++;
                    break;
                }
            }
        }
    }
 
    //2. 최고 순위, 최저 순위 계산
    int bestRank = ranking(hitCount + zeroCount);
    int worstRank = ranking(hitCount);
 
    //결과 저장
    answer.push_back(bestRank);
    answer.push_back(worstRank);
 
    //결과 반환
    return answer;
 
}
 

 

구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 다단계 칫솔 판매  (0) 2021.05.04
[C++] 프로그래머스 - 행렬 테두리 회전하기  (0) 2021.05.04
[C++] 프로그래머스 - 파일명 정렬  (0) 2021.04.23
[C++] 프로그래머스 - 순위 검색  (0) 2021.02.02
[C++] 프로그래머스 - 합승 택시 요금  (0) 2021.01.31

programmers.co.kr/learn/courses/30/lessons/17686

 

코딩테스트 연습 - [3차] 파일명 정렬

파일명 정렬 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램

programmers.co.kr

<풀이>

1. 파일명들을 입력받는다.

2. 주어진 파일들을 정해진 규칙으로 정렬하여 반환한다.

 

<해법>

1. 파일들을 정해진 규칙에 따라 정렬하는 방법

=> 가장 먼저 주어진 파일들을 HEAD, NUMBER, TAIL을 분류해서 새로운 구조체의 형식으로 만듭니다. 이 후, 주어진 규칙에 따라 정렬하는 기준을 만들고 정렬합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
//구조 : 파일 이름(index, head, number)
struct fileName {
    int index;
    string head;
    int number;
};
 
vector<fileName> v;
 
//fileName 구조체 정렬 기준
bool compare(const fileName& f1, const fileName& f2) {
    if (f1.head == f2.head) {
        if (f1.number == f2.number) {
            return f1.index < f2.index;
        }
        else {
            return f1.number < f2.number;
        }
    }
    else {
        return f1.head < f2.head;
    }
}
 
//해당 문자가 숫자인지 판단하는 함수
bool isNumber(char c) {
    if (c >= '0' && c <= '9') {
        return true;
    }
    return false;
}
 
vector<string> solution(vector<string> files) {
    
    vector<string> answer;
 
    //모든 파일 탐색
    for (int i = 0; i < files.size(); i++) {
 
        //1. 소문자 변환
        string fileString = "";
        for (int j = 0; j < files[i].length(); j++) {
            fileString += tolower(files[i][j]);
        }
 
        //HEAD, NUMBER 초기화
        string HEAD = "";
        string NUMBER = "";
        int pointer = 0;
 
        //2-1. HEAD 분할
        while (pointer >= fileString.length()) {
          
            //숫자가 나오면 반복문 종료
            if (isNumber(fileString[pointer])) {
                break;
            }
 
            HEAD += fileString[pointer];
            ++pointer;
        }
 
        //2-2. NUMBER 분할
        while (pointer >= fileString.length()) {
 
            //숫자가 아닌것이 나오면 반복문 종료
            if (!isNumber(fileString[pointer])) {
                break;
            }
 
            NUMBER += fileString[pointer];
            ++pointer;
        }
 
        //구조체 생성
        fileName f;
        f.index = i;
        f.head = HEAD;
        f.number = stoi(NUMBER);
        
        //3. 벡터에 구조체 저장
        v.push_back(f);
    }
 
    //4. 정렬
    sort(v.begin(), v.end(), compare);
 
    //결과 저장
    for (int i = 0; i < v.size(); i++) {
        answer.push_back(files[v[i].index]);
    }
 
    //반환
    return answer;
}

 

문자열과 구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 행렬 테두리 회전하기  (0) 2021.05.04
[C++] 프로그래머스 - 로또의 최고 순위와 최저 순위  (0) 2021.05.04
[C++] 프로그래머스 - 순위 검색  (0) 2021.02.02
[C++] 프로그래머스 - 합승 택시 요금  (0) 2021.01.31
[C++] 프로그래머스 - 메뉴 리뉴얼  (0) 2021.01.31

www.acmicpc.net/problem/2011

 

2011번: 암호코드

나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다.

www.acmicpc.net

<풀이>

1. 암호코드를 입력받는다.

2. 암호코드가 해석될 수 있는 가짓수를 구하고 출력한다.

 

<해법>

DP 문제라는 것을 쉽게 생각할 수 있습니다. 

DP 문제를 접근하는 방식으로 Top-down, Bottom-up 방식 이렇게 두 가지가 있는데, 두 방법을 모두 사용해서 풀어보겠습니다.

DP의 핵심은 "점화식 도출" 입니다.

Top-down, Bottom-up 방식의 점화식에 약간의 차이가 있습니다.

 

1. Top-down

"점화식 : D[i] = D[i+1] + D[i+2], D[i] = i번째 <부터> 해석될 수 있는 암호의 수"

예를 들어, 123456 이라는 암호가 있습니다.

이 암호를 해독할 때, 첫 번째 수는 1 / 23456 과 12 / 3456 이렇게 두 가지로 해석할 수 있습니다.

따라서, ["1"부터 해석될 수 있는 암호의 수 = "23456" 암호 해석 수 + "3456" 암호 해석 수] 라고 생각할 수 있습니다.

저는 아래와 같이 구현하였습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <string>
#include <string.h>
#define MAX 5001
#define divider 1000000
 
using namespace std;
 
string code;
int cache[MAX];
int answer;
 
//알파벳으로 바뀔 수 있는지 확인
bool canChangeAlpha(string s) {
    int number = stoi(s);
 
    if (number >= 10 && number <= 26) {
        return true;
    }
    return false;
}
 
int countDecode(int index) {
 
    int& ret = cache[index];
 
    if (ret != -1) {
        return ret;
    }
 
    ret = 0;
 
    //현재 index부터 두 글자 떼어내기
    string cur = code.substr(index, 2);
 
    //첫 글자가 '0'인 경우 -> 암호 불가
    if (cur[0] == '0') {
        return ret = 0;
    }
 
    //떼어낸 글자의 길이가 0 or 1인 경우 -> 종료 조건
    if (cur.length() == 0 || cur.length() == 1) {
        return ret = 1;
    }
 
    /*
    점화식 : D[i] = D[i+1] + D[i+2]
    ------------------------
    D[i] : i번째 <부터> 해석될 수 있는 암호의 수
    */
    ret += countDecode(index + 1);
    ret += canChangeAlpha(cur) ? countDecode(index + 2) : 0;
 
    return ret % divider;
}
 
int main() {
 
    //초기화
    code = "";
    memset(cache, -1, sizeof(cache));
    answer = 0;
 
    //입력
    cin >> code;
 
    //해법
    answer = countDecode(0);
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}
 

 

2. Bottou-up

"점화식 : D[i] = D[i-1] + D[i-2], D[i] = i번째 <까지> 해석될 수 있는 암호의 수"

위와 똑같이 123456 암호를 예시로 들겠습니다.

이 암호의 마지막 수는 12345 / 6 과 1234 / 56 이렇게 두 가지로 해석할 수 있습니다. (두 번째 경우는 사실 안됩니다.)

따라서, ["6"까지 해석될 수 있는 암호의 수 = "12345" 암호 해석 수 + "1234" 암호 해석 수] 라고 생각할 수 있습니다.

저는 아래와 같이 구현하였습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <string>
#include <string.h>
#define MAX 5001
#define divider 1000000
 
using namespace std;
 
string code;
int cache[MAX];
int answer;
 
bool isZero(char c) {
    if (c == '0') {
        return true;
    }
    return false;
}
 
bool canChangeAlpha(string s) {
    int number = stoi(s);
 
    if (number >= 10 && number <= 26) {
        return true;
    }
    return false;
}
 
int countDecode(string s) {
 
    if (s[0] == '0') {
        return 0;
    }
 
    /*
    점화식 : D[i] = D[i-1] + D[i-2]
    ------------------------
    D[i] : i번째 <까지> 해석될 수 있는 암호의 수
    */
    cache[0] = cache[1] = 1;
    for (int i = 2; i <= s.length(); i++) {
        cache[i] = isZero(s[i-1]) ? 0 : cache[i - 1];
        cache[i] += canChangeAlpha(s.substr(i - 2, 2)) ? cache[i - 2] : 0;
        cache[i] %= divider;
    }
 
    return cache[s.length()];
}
 
int main() {
 
    //초기화
    code = "";
    memset(cache, -1, sizeof(cache));
    answer = 0;
 
    //입력
    cin >> code;
 
    //해법
    answer = countDecode(code);
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}
 

Top-down과 Bottom-up 사이의 접근 방식 차이가 느껴지셨으면 좋겠습니다.

 

사실 위 문제는 DP를 떠올리는 것보다 예외 처리를 하는 것이 더 까다롭게 느껴졌습니다. 저가 문제를 풀면서 겪었던 예외는

 

1. 숫자가 '0'으로 시작하는 경우

2. 숫자 두개로 해석할 때의 범위는, 10 이상 26 이하

3. 계산을 진행하면서 100,0000으로 나누어 주어야 함

 

이렇게 3가지 였습니다. 많은 도움이 되었으면 좋겠습니다.

 

DP에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 16637 - 괄호 추가하기  (0) 2022.12.21
[C++] 백준 13460 - 구슬 탈출2  (1) 2022.12.21
[C++] 백준 2156 - 포도주 시식  (0) 2021.01.25
[C++] 백준 1074 - Z  (0) 2021.01.18
[C++] 백준 1780 - 종이의 개수  (0) 2021.01.14

programmers.co.kr/learn/courses/30/lessons/72412

 

코딩테스트 연습 - 순위 검색

["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"] ["java and backend and junior and pizza 100","pyt

programmers.co.kr

<풀이>

1. 지원서 정보와 해당 쿼리를 입력받는다.

2. 해당 쿼리에 맞는 지원자의 수를 벡터에 담아 반환한다.

 

<해법>

1. "효율성 테스트"가 있는 문제의 마음가짐

=> 이 문제는 효율성 테스트가 있는 문제입니다. 따라서, 쿼리 하나씩 모든 지원서 정보를 찾으면서 풀이를 할 경우 시간복잡도가 50,000 x 100,000 이므로 문제를 통과할 수 없습니다. 그렇다면 이 때 '지원서 정보를 잘 정리해야겠다.' 라는 생각을 해야합니다. 더 나아가서, 어떤 자료구조와 알고리즘을 사용해야 할 지 생각해야합니다. "효율성 테스트"가 있는 문제는 단순히 구현을 묻는 문제가 아닙니다. 문제에 맞는 자료구조와 알고리즘을 떠올릴 수 있는지가 문제의 핵심입니다.

 

2. 지원서 정보를 정리하는 방법

=> '지원서 정보를 잘 정리해야겠다.' 는 생각까지 하였습니다. 하지만, 물음에 쉽게 답이 나오지 않습니다. 마땅한 정렬방법이 없기 때문입니다. 이 때, 생각을 전환하여 '쿼리에 맞는 지원서를 정리할 수 있을까?'라는 생각을 할 수 있어야합니다. 해당 지원서 정보가 가능한 모든 쿼리들에 저장해놓는 방식입니다. 

위와 같이 정리를 해놓고, 해당 쿼리마다 만족되는 점수들의 개수를 구합니다. 만족되는 점수들의 개수를 구할 때, 점수들을 정렬해놓고 이분탐색을 이용하면 더 빠르게 찾을 수 있습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <algorithm>
 
using namespace std;
 
map<string, vector<int>> m;
 
void infoIntoMap(string info) {
 
    string infoArr[4][2] = {
        {"-"},
        {"-"},
        {"-"},
        {"-"}
    };
    int infoScore = 0;
 
    //info 띄어쓰기 분리
    istringstream iss(info);
    iss >> infoArr[0][1] >> infoArr[1][1] >> infoArr[2][1] >> infoArr[3][1] >> infoScore;
 
    //info가 해당될 수 있는 모든 쿼리 만들기
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                for (int l = 0; l < 2; l++) {
                    //map의 key
                    string infoString = infoArr[0][i] + infoArr[1][j] 
                                          + infoArr[2][k] + infoArr[3][l];     
                    
                    //map에 저장
                    m[infoString].push_back(infoScore);
                }
            }
        }
    }
}
 
int findQueryFromMap(string query) {
 
    int output = 0;
 
    string queryArr[4];
    int queryScore = 0;
 
    //query 띄어쓰기 분리
    string trash = "";
    istringstream iss(query);
    iss >> queryArr[0] >> trash >> queryArr[1] >> trash 
        >> queryArr[2] >> trash >> queryArr[3] >> queryScore;
 
    //map의 key만들기
    string queryString = "";
    for (int i = 0; i < 4; i++) {
        queryString += queryArr[i];
    }
 
    //findScores = map의 value
    vector<int> findScores = m[queryString];
 
    //해당 백터에서 queryScore의 lower_bound를 찾고 개수 계산
    output = findScores.end() - lower_bound(findScores.begin(), findScores.end(), queryScore);
 
    //개수 반환
    return output;
}
 
vector<int> solution(vector<string> info, vector<string> query) {
 
    vector<int> answer;
 
    //주어진 info를 map에 담기
    for (int i = 0; i < info.size(); i++) {
        infoIntoMap(info[i]);
    }
 
    //map에 저장되어 있는 점수들 정렬
    for (auto& instance : m) {
        sort(instance.second.begin(), instance.second.end());
    }
 
    //query를 분리해서 answer에 저장
    for (int i = 0; i < query.size(); i++) {
        answer.push_back(findQueryFromMap(query[i]));
    }
 
    //반환
    return answer;
}
 

 

문제 해결 능력에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 로또의 최고 순위와 최저 순위  (0) 2021.05.04
[C++] 프로그래머스 - 파일명 정렬  (0) 2021.04.23
[C++] 프로그래머스 - 합승 택시 요금  (0) 2021.01.31
[C++] 프로그래머스 - 메뉴 리뉴얼  (0) 2021.01.31
[C++] 프로그래머스 - 신규 아이디 추천  (0) 2021.01.31

programmers.co.kr/learn/courses/30/lessons/72413

 

코딩테스트 연습 - 합승 택시 요금

6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4

programmers.co.kr

<풀이>

1. 적절한 지점까지 합승을 하여, 택시 요금이 최소가 되는 택시 요금을 구한다.

2. 최소 택시 요금을 반환한다.

 

<해법>

택시 합승은 다음과 같이 이루어집니다.

s에서 어떤 지점까지는 합승을 하고, 그 지점에서 각자 택시를 타고 가는 것입니다.

이 때 알아야 하는 것은 s에서 어떤 지점까지 가는 최소 요금, 어떤 지점에서 각자 도착지점까지 가는 최소 요금 이렇게 두 가지 입니다.

여기서 모든 정점 간의 최소거리를 계산하는 플로이드 알고리즘을 떠올릴 수 있습니다. 

따라서, 플로이드 알고리즘을 이용하여 모든 정점 간의 최소 거리를 구하고, 각각 지점까지 합승했을 때의 택시요금을 구한 후, 그 중 최소요금을 반환합니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <string>
#include <vector>
#include <string.h>
#include <algorithm>
#define INF 123456789
 
using namespace std;
 
int W[201][201]; //주어진 그래프
int D[201][201]; //플로이드 알고리즘을 거친 후, 최단거리 배열
 
//플로이드 알고리즘
void floyd(int n) {
 
    //초기화
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            D[i][j] = W[i][j];
        }
    }
 
    //플로이드 핵심
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
            }
        }
    }
    
}
 
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
 
    int answer = INF;
 
    //초기화
    memset(W, INF, sizeof(W));
    for (int i = 1; i <= n; i++) {
        //1번지점 -> 1번지점으로 가는 경우 -> 0원
        W[i][i] = 0;
    }
 
    //그래프 그리기
    for (int i = 0; i < fares.size(); i++) {
        int first = fares[i][0];
        int second = fares[i][1];
        int fare = fares[i][2];
 
        W[first][second] = fare;
        W[second][first] = fare;
    }
 
    //플로이드 알고리즘
    floyd(n);
 
    //정답 갱신
    for (int i = 1; i <= n; i++) {
        /*
        D[s][i] + D[i][a] + D[i][b]
        : s부터 i까지는 같이가고, i부터는 각자 가는 경우의 택시요금
        */
        answer = min(answer, D[s][i] + D[i][a] + D[i][b]);
    }
 
    //반환
    return answer;
}
 

 

플로이드 알고리즘에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 파일명 정렬  (0) 2021.04.23
[C++] 프로그래머스 - 순위 검색  (0) 2021.02.02
[C++] 프로그래머스 - 메뉴 리뉴얼  (0) 2021.01.31
[C++] 프로그래머스 - 신규 아이디 추천  (0) 2021.01.31
[C++] 프로그래머스 - 압축  (0) 2021.01.19

programmers.co.kr/learn/courses/30/lessons/72411

 

코딩테스트 연습 - 메뉴 리뉴얼

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서

programmers.co.kr

<풀이>

1. 주어진 메뉴의 개수만큼 가장 많이 선택된 메뉴 조합을 구한다.

2. 메뉴 조합을 사전순으로 정렬하고 반환한다.

 

<해법>

1. 주문한 메뉴 조합에서 코스 개수에 따른 조합 개수 구하는 방법

=> 주문한 메뉴 조합이 "ABCDE"이고 만들려고하는 코스 개수가 "2"개라면 만들 수 있는 모든 코스는 AB, AC, AD, AE, BC, BD, ... 이 있습니다. 이렇게 만들어진 코스 이름과 코스 개수를 저장해두어야 합니다. 따라서, 저는 map을 사용하여 만들어진 코스 이름과 코스 개수를 저장해두었습니다.

예를 들어, 메뉴조합은 "ABCDE, AB, CDE"이고 코스개수는 "2"개 라고 한다면

ABCDE -> AB, AC, AD, AE, BC, BD, ...

AB -> AB

CDE -> CD, CE, DE

메뉴조합은 위와 같이 나타낼 수 있습니다.

이를 map에 [AB : 2], [AC : 1], [AD: 1] 방식으로 저장합니다.

 

2. 가장 많이 함께 주문된 메뉴 구성 구하는 방법

=> 메뉴 구성과 개수를 map에 저장해두었습니다. map에 있는 개수를 기준으로 정렬하여야 하므로, map에 있는 데이터를 vector로 옮기고 정렬을 진행하였습니다. 이 후, 가장 많이 함께 구성된 메뉴를 answer에 넣어줍니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
 
using namespace std;
 
map<string, int> m;
 
bool cmp(pair<string, int> a, pair<string, int> b) {
    return a.second > b.second;
}
 
void findAllCourse(string order, int size, string s, int index) {
 
    //종료조건
    if (s.length() == size) {
        map<string, int>::iterator iter;
 
        iter = m.find(s);
 
        //맵에 코스가 이미 존재하는 경우 -> 개수 + 1
        if (iter != m.end()) {
            iter->second++;
        }
        //맵에 코스가 존재하지 않는 경우 -> 맵에 삽입
        else {
            m.insert(pair<string, int>(s, 1));
        }
 
        return;
    }
 
    for (int i = index; i < order.length(); i++) {
        findAllCourse(order, size, s + order[i], i + 1);
    }
}
 
vector<string> solution(vector<string> orders, vector<int> course) {
 
    vector<string> answer;
 
    //코스 크기 만큼 모두 해보기
    for (int i = 0; i < course.size(); i++) {
 
        m.clear();
 
        for (int j = 0; j < orders.size(); j++) {
 
            //메뉴 정렬(ex. CBA -> ABC)
            sort(orders[j].begin(), orders[j].end());
 
            //주문한 조합에서 코스 개수만큼 골라서, 모든 조합 만들기 -> 맵에 저장
            if (course[i] <= orders[j].length()) {
                findAllCourse(orders[j], course[i], "", 0);
            }
        }
 
        //map -> vector 옮기기
        vector<pair<string, int>> v(m.begin(), m.end());
 
        //만들어진 조합 개수에 따라 정렬
        sort(v.begin(), v.end(), cmp);
 
        if (!v.empty()) {
            //최대 개수 크기만큼 정답에 저장
            int biggest = v[0].second;
 
            //최소 2명 이상 손님으로부터 주문된 조합이어야 하므로
            if (biggest >= 2) {
                for (int i = 0; i < v.size(); i++) {
                    if (v[i].second == biggest) {
                        answer.push_back(v[i].first);
                    }
                    else {
                        break;
                    }
                }
            }
        }
    }
 
    //정렬
    sort(answer.begin(), answer.end());
 
    //반환
    return answer;
}
 

 

브루트포스에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 순위 검색  (0) 2021.02.02
[C++] 프로그래머스 - 합승 택시 요금  (0) 2021.01.31
[C++] 프로그래머스 - 신규 아이디 추천  (0) 2021.01.31
[C++] 프로그래머스 - 압축  (0) 2021.01.19
[C++] 프로그래머스 - 방금그곡  (0) 2021.01.19

programmers.co.kr/learn/courses/30/lessons/72410

 

코딩테스트 연습 - 신규 아이디 추천

카카오에 입사한 신입 개발자 네오는 카카오계정개발팀에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. 네오에게 주어진 첫 업무는 새로 가

programmers.co.kr

<풀이>

1. 새로 가입하는 유저의 아이디를 '7단계의 처리과정'을 거쳐 추천 아이디를 생성한다.

2. 추천 아이디를 반환한다.

 

<해법>

문제를 푸는데 특별한 아이디어가 필요하지 않습니다. '7단계 처리과정'을 정확하게 구현하는 것이 문제의 핵심입니다. 문자열 관련 문제이므로, 문자열 처리 함수를 사용하면 보다 쉽게 구현할 수 있습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <string>
#include <vector>
 
using namespace std;
 
string solution(string new_id) {
 
    string answer = "";
 
    //step 1
    for (int i = 0; i < new_id.length(); i++) {
        new_id[i] = tolower(new_id[i]);
    }
    
    //step 2
    string str = "";
    for (int i = 0; i < new_id.length(); i++) {
        if ((new_id[i] >= 'a' && new_id[i] <= 'z') || (new_id[i] >= '0' && new_id[i] <= '9') || new_id[i] == '-' || new_id[i] == '_' || new_id[i] == '.') {
            str += new_id[i];
        }
    }
    new_id = str;
 
    //step 3
    while (true) {
        int index = new_id.find("..");
 
        if (index == string::npos) {
            break;
        }
 
        new_id.replace(index, 2, ".");
    }
 
    //step 4
    if (new_id[0] == '.') {
        new_id = new_id.substr(1);
    }
    if (new_id[new_id.length() - 1] == '.') {
        new_id = new_id.substr(0, new_id.length() - 1);
    }
 
    //step 5
    if (new_id == "") {
        new_id = "a";
    }
 
    //step 6
    if (new_id.length() >= 16) {
        new_id = new_id.substr(0, 15);
        if (new_id[14] == '.') {
            new_id = new_id.substr(0, 14);
        }
    }
 
    //step 7
    if (new_id.length() <= 2) {
        char lastChar = new_id[new_id.length() - 1];
        while (true) {
            if (new_id.length() == 3) {
                break;
            }
            new_id += lastChar;
        }
    }
 
    answer = new_id;
 
    return answer;
}
 

 

문자열과 구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 합승 택시 요금  (0) 2021.01.31
[C++] 프로그래머스 - 메뉴 리뉴얼  (0) 2021.01.31
[C++] 프로그래머스 - 압축  (0) 2021.01.19
[C++] 프로그래머스 - 방금그곡  (0) 2021.01.19
[C++] 프로그래머스 - 다트 게임  (0) 2021.01.16

www.acmicpc.net/problem/2156

 

2156번: 포도주 시식

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규

www.acmicpc.net

<풀이>

1. 포도주들을 입력받는다.

2. 최대 2잔까지 연속으로 마시면서, 마실 수 있는 포도주의 최대량을 계산하고 출력한다.

 

<해법>

1. DP 점화식

=> 점화식은 "현재 포도주를 마시거나, 마시지 않는 모든 경우 중 최댓값" 입니다. 모든 경우는 아래 그림과 같이 나타낼 수 있습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <string.h>
#include <algorithm>
#define MAX 10000 + 1
 
using namespace std;
 
int n;
int wine[MAX];
int cache[MAX];
int answer;
 
int main() {
 
    //초기화
    n = 0;
    memset(wine, 0, sizeof(wine));
    memset(cache, 0, sizeof(cache));
    answer = 0;
 
    //입력
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> wine[i];
    }
 
    //해법
    cache[1] = wine[1];
    cache[2] = wine[1] + wine[2];
    for (int i = 3; i <= n; i++) {
        int case1 = cache[i - 3] + wine[i - 1] + wine[i]; //~XOO 와인 마신 경우
        int case2 = cache[i - 2] + wine[i]; //~XO 와인 마신 경우
        int case3 = cache[i - 1]; //~X 와인 마신 경우
 
        cache[i] = max(max(case1, case2), case3);
    }
 
    //결과 갱신
    answer = cache[n];
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}
 

 

DP에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[C++] 백준 13460 - 구슬 탈출2  (1) 2022.12.21
[C++] 백준 2011 - 암호코드  (0) 2021.02.06
[C++] 백준 1074 - Z  (0) 2021.01.18
[C++] 백준 1780 - 종이의 개수  (0) 2021.01.14
[C++] 백준 2447 - 별 찍기 10  (0) 2021.01.14

+ Recent posts

티스토리툴바