https://school.programmers.co.kr/learn/courses/30/lessons/118666

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

<풀이>

1. 질문지와 선택지를 입력받는다.

2. 질문지와 선택지에 따라서 성격유형 점수를 계산한다.

3. 계산된 점수에 따라서 성격유형을 반환한다.

 

<해법>

1. '성격 유형 점수판' 만들기

=> 이 문제는 결국 '성격 유형 점수판'을 구현하는 것이 관건입니다. 저는 map 자료구조를 사용해서 구현하였습니다.

 

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
#include <string>
#include <vector>
#include <map>
#include <iostream>
 
using namespace std;
 
string solution(vector<string> survey, vector<int> choices) {
 
    //선언
    string answer;      //--> 출력 정답
    char c[4][2] = {    //--> 성격유형 지표
        {'R', 'T'},
        {'C', 'F'},
        {'J', 'M'},
        {'A', 'N'},
    };      
    map<char, int> m;   //--> 성격유형 점수판
    
    //초기화
    answer = "";
 
    /* 해법 */
    for (int i = 0; i < survey.size(); i++) {
 
        //1. 점수 계산
        //해당 성격유형 점수 더해주기
        if (choices[i] < 4) {
            m[survey[i][0]] += (4 - choices[i]);
        }
        else {
            m[survey[i][1]] += (choices[i] - 4);
        }
    }
 
    //2. 성격유형 모음
    for (int i = 0; i < 4; i++) {
        if (m[c[i][0]] >= m[c[i][1]]) {
            answer += c[i][0];
        }
        else {
            answer += c[i][1];
        }
    }
 
    //반환
    return answer;
}

 

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

저작자표시

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

[C++] 프로그래머스 - 코딩 테스트 공부  (0) 2022.08.24
[C++] 프로그래머스 - 두 큐 합 같게 만들기  (0) 2022.08.24
[C++] 프로그래머스 - 호텔 방 배정  (0) 2021.05.05
[C++] 프로그래머스 - 징검다리 건너기  (0) 2021.05.04
[C++] 프로그래머스 - 다단계 칫솔 판매  (0) 2021.05.04

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

 

코딩테스트 연습 - 호텔 방 배정

 

programmers.co.kr

<풀이>

1. 고객이 원하는 방 정보를 입력받는다.

2. 규칙에 따라 방을 배정하고, 배정된 방을 반환한다.

 

<해법>

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

=> 단순히 구현을 요구하는 문제가 아님을 깨달아야 합니다. 문제를 읽으면서, 어떤 알고리즘 또는 자료구조를 사용할지 생각해야합니다. 저는 어떤 방에 대한 다음 방의 정보를 저장하는 방법을 생각했고, 이 때 map자료구조를 사용하였습니다.

 

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
#include <iostream>
#include <string>
#include <vector>
#include <map>
 
using namespace std;
 
//Key: 방 번호, Value: 다음방 번호
map<long long, long long> m;
 
//어떤 방의 다음 방을 갱신하는 함수
long long findNextRoom(long long roomNum) {
    if (m[roomNum] == 0) {
        return roomNum;
    }
 
    return m[roomNum] = findNextRoom(m[roomNum]);
}
 
vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
 
    /* 해법 */
    //어떤 방의 다음 방을 계속해서 갱신
    for (int i = 0; i < room_number.size(); i++) {
 
        if (m[room_number[i]] == 0) {
            answer.push_back(room_number[i]);
            m[room_number[i]] = findNextRoom(room_number[i] + 1);
        }
        else {
            long long foundRoom = findNextRoom(room_number[i]);
            answer.push_back(foundRoom);
            m[foundRoom] = findNextRoom(foundRoom + 1);
        }
    }
 
    //결과 반환
    return answer;
}
 

 

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

저작자표시

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

[C++] 프로그래머스 - 두 큐 합 같게 만들기  (0) 2022.08.24
[C++] 프로그래머스 - 성격 유형 검사하기  (0) 2022.08.24
[C++] 프로그래머스 - 징검다리 건너기  (0) 2021.05.04
[C++] 프로그래머스 - 다단계 칫솔 판매  (0) 2021.05.04
[C++] 프로그래머스 - 행렬 테두리 회전하기  (0) 2021.05.04

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

 

코딩테스트 연습 - 징검다리 건너기

[2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3

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
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
//해당 사람의 수가 징검다리를 건널 수 있는지 확인하는 함수
bool canCross(vector<int> stones, int peopleCnt, int k) {
 
    int stoneCnt = 0;
    for (int i = 0; i < stones.size(); i++) {
        if (stones[i] - peopleCnt < 0) {
            stoneCnt++;
            if (stoneCnt >= k) {
                return false;
            }
        }
        else {
            stoneCnt = 0;
        }
    }
    return true;
}
 
int solution(vector<int> stones, int k) {
    int answer = 0;
 
    /* 해법 */
    //건널 수 있는 사람의 수를 이분탐색
    int start = 0;
    int end = *max_element(stones.begin(), stones.end());
 
    while (start <= end) {
        int mid = (start + end) / 2;
 
        //mid수의 사람이 건널 수 있는지 확인
        if (canCross(stones, mid, k)) {
            answer = mid;
            start = mid + 1;
        }
        else {
            end = mid - 1;
        }
    }
 
    //결과 반환
    return answer;
}
 

 

이분탐색에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] 프로그래머스 - 성격 유형 검사하기  (0) 2022.08.24
[C++] 프로그래머스 - 호텔 방 배정  (0) 2021.05.05
[C++] 프로그래머스 - 다단계 칫솔 판매  (0) 2021.05.04
[C++] 프로그래머스 - 행렬 테두리 회전하기  (0) 2021.05.04
[C++] 프로그래머스 - 로또의 최고 순위와 최저 순위  (0) 2021.05.04

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

 

코딩테스트 연습 - 다단계 칫솔 판매

민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후,

programmers.co.kr

<풀이>

1. 다단계 조직도와 판매 정보를 입력받는다.

2. 판매 이익을 자신의 추천인과 재분배하고, 각 사람들의 이익을 반환한다.

 

<해법>

1. 다단계 조직도를 정리하는 방법

=> 사람마다 자신의 추천인을 저장해놓습니다. map자료구조를 사용하여 key, value를 각각 이름으로 해놓을 수도 있습니다. 저는 실행시간 단축을 위해, 각 사람마다 인덱스(번호)를 부여하였고, 추천인 배열을 만들어서 사람의 인덱스에 추천인의 인덱스를 저장해놓는 방식으로 구현하였습니다.

 

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
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <string.h>
 
using namespace std;
 
map<string, int> m;
int parent[10000];
int profits[10000];
 
//이익 분배 함수
void divideProfit(int index, int profit) {
 
    //종료조건 : 민호까지 왔을 경우
    if (index == -1) {
        return;
    }
 
    //이익 분배
    int stolen = profit / 10;
    int myProfit = profit - stolen;
    profits[index] += myProfit;
 
    //종료조건 : 더 이상 나눌 이익이 없을 경우
    if (stolen == 0) {
        return;
    }
 
    //재귀
    divideProfit(parent[index], stolen);
}
 
vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;
 
    //초기화
    memset(parent, 0, sizeof(parent));
    memset(profits, 0, sizeof(profits));
 
 
    /* 해법 */
    //1. 맵 자료구조에 {'이름' : 'index'} 저장
    for (int i = 0; i < enroll.size(); i++) {
        m[enroll[i]] = i;
    }
 
    //2. 각 index마다 추천인 index 저장
    for (int i = 0; i < referral.size(); i++) {
        if (referral[i] == "-") {
            parent[i] = -1;
        }
        else {
            parent[i] = m[referral[i]];
        }
    }
 
    //3. 이익분배
    for (int i = 0; i < seller.size(); i++) {
        divideProfit(m[seller[i]], amount[i] * 100);
    }
 
    //결과 저장
    for (int i = 0; i < enroll.size(); i++) {
        answer.push_back(profits[i]);
    }
 
    //결과 반환
    return answer;
}
 

 

자료구조와 재귀함수에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] 프로그래머스 - 호텔 방 배정  (0) 2021.05.05
[C++] 프로그래머스 - 징검다리 건너기  (0) 2021.05.04
[C++] 프로그래머스 - 행렬 테두리 회전하기  (0) 2021.05.04
[C++] 프로그래머스 - 로또의 최고 순위와 최저 순위  (0) 2021.05.04
[C++] 프로그래머스 - 파일명 정렬  (0) 2021.04.23

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

 

코딩테스트 연습 - 행렬 테두리 회전하기

6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3]

programmers.co.kr

<풀이>

1. 주어진 맵과 회전 정보를 입력받는다.

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
#include <iostream>
#include <string>
#include <vector>
#include <string.h>
#include <algorithm>
 
using namespace std;
 
int map[101][101];
int minChanged;
 
//회전 함수
void rotate(int x1, int y1, int x2, int y2) {
 
    int start = map[x1][y1];
 
    for (int i = x1; i < x2; i++) {
        map[i][y1] = map[i + 1][y1];
        minChanged = min(minChanged, map[i][y1]);
    }
 
    for (int i = y1; i < y2; i++) {
        map[x2][i] = map[x2][i + 1];
        minChanged = min(minChanged, map[x2][i]);
    }
 
    for (int i = x2; i > x1; i--) {
        map[i][y2] = map[i - 1][y2];
        minChanged = min(minChanged, map[i][y2]);
    }
 
    for (int i = y2; i > y1 + 1; i--) {
        map[x1][i] = map[x1][i - 1];
        minChanged = min(minChanged, map[x1][i]);
    }
 
    map[x1][y1 + 1] = start;
    minChanged = min(minChanged, map[x1][y1 + 1]);
}
 
vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;
 
    //초기화
    memset(map, 0, sizeof(map));
 
    /* 해법 */
    //1. 맵 그리기
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= columns; j++) {
            map[i][j] = (i - 1) * columns + j;
        }
    }
 
    //2. 쿼리에 따라 맵 회전하기
    for (int i = 0; i < queries.size(); i++) {
 
        minChanged = 10001;
 
        int x1, y1, x2, y2;
        x1 = queries[i][0];
        y1 = queries[i][1];
        x2 = queries[i][2];
        y2 = queries[i][3];
 
        //회전
        rotate(x1,y1,x2,y2);
 
        //결과 저장
        answer.push_back(minChanged);
    }
 
    //결과 반환
    return answer;
}
 

 

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

저작자표시

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

[C++] 프로그래머스 - 징검다리 건너기  (0) 2021.05.04
[C++] 프로그래머스 - 다단계 칫솔 판매  (0) 2021.05.04
[C++] 프로그래머스 - 로또의 최고 순위와 최저 순위  (0) 2021.05.04
[C++] 프로그래머스 - 파일명 정렬  (0) 2021.04.23
[C++] 프로그래머스 - 순위 검색  (0) 2021.02.02

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

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

+ Recent posts

티스토리툴바