[프로그래머스] 순위 검색

2021 카카오 코딩 테스트 문제입니다.

 

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

문제 확인

 

prefix sum을 이용한 간단한 구현 문제입니다.

 

풀이

 

query 에서 - 를 빠르게 처리하기 위해 경우의 수를 나누어 ary[4][3][3][3][100001]으로 선언하게 되면 메모리 초과가 나기 때문에 ary[3][2][2][2][100001] 와 쿼리를 따로 처리해 주거나 vector, map 컨테이너를 활용해서 풀어야 합니다.

 

들어오는 info를 처리해주며 해당 score의 점수를 더해둡니다.

모든 info가 처리가 되면 score에 저장된 점수들을 prefix sum을 통해 한 번의 접근으로 점수 정보를 얻을 수 있도록 합니다.

예를 들어 100점 2명, 150점 1명, 300점 3명이 있다고 한다면 prefix sum 배열은 다음과 같이 됩니다.

prefix sum이 완성되면 query에서 150점 이상인 사람을 구해야 한다면 단순히 ary[a][b][c][d][150] 을 통해 구할 수 있습니다.

 

코드

#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    int ary[3][2][2][2][100001] = { 0 };
    for (auto &str : info) {
        int a, b, c, d, score;
        int i = 0;
        if (str[i] == 'c') a = 0;
        else if (str[i] == 'j')a = 1;
        else a = 2;
 
        while (str[i] != ' ')i++;
        b = str[++i] != 'b' ? 1 : 0;
 
        while (str[i] != ' ')i++;
        c = str[++i] != 'j' ? 1 : 0;
 
        while (str[i] != ' ')i++;
        d = str[++i] != 'c' ? 1 : 0;
 
        while (str[i] != ' ')i++;
        score = stoi(str.substr(++i));
        ary[a][b][c][d][score]++;
    }
    for (int a = 0; a < 3; a++)
        for (int b = 0; b < 2; b++)
            for (int c = 0; c < 2; c++)
                for (int d = 0; d < 2; d++)
                    for (int i = 100000; i > 1; --i)
                        ary[a][b][c][d][i - 1] += ary[a][b][c][d][i];
    for (auto &str : query) {
        int a, b, c, d, score;
        int count = 0, i = 0;
 
        if (str[i] == '-') a = -1;
        else if (str[i] == 'c') a = 0;
        else if (str[i] == 'j')a = 1;
        else a = 2;
 
        while (str[i] != ' ')i++;
        i += 5;
        if (str[i] == '-') b = -1;
        else if (str[i] == 'b') b = 0;
        else b = 1;
 
        while (str[i] != ' ')i++;
        i += 5;
        if (str[i] == '-') c = -1;
        else if (str[i] == 'j') c = 0;
        else c = 1;
 
        while (str[i] != ' ')i++;
        i += 5;
        if (str[i] == '-') d = -1;
        else if (str[i] == 'c') d = 0;
        else d = 1;
 
        while (str[i] != ' ')i++;
        score = stoi(str.substr(++i));
 
        for (int q = (a == -1) ? 0 : a; q <= ((a == -1) ? 2 : a); q++)
            for (int w = (b == -1) ? 0 : b; w <= ((b == -1) ? 1 : b); w++)
                for (int e = (c == -1) ? 0 : c; e <= ((c == -1) ? 1 : c); e++)
                    for (int r = (d == -1) ? 0 : d; r <= ((d == -1) ? 1 : d); r++)
                        count += ary[q][w][e][r][score];
 
 
        answer.push_back(count);
    }
    return answer;
}
 
 

 

정확성 테스트

테스트 1 〉	통과 (6.89ms, 12.8MB)
테스트 2 〉	통과 (6.03ms, 12.8MB)
테스트 3 〉	통과 (6.41ms, 12.8MB)
테스트 4 〉	통과 (6.52ms, 13.2MB)
테스트 5 〉	통과 (6.83ms, 13.2MB)
테스트 6 〉	통과 (6.89ms, 12.9MB)
테스트 7 〉	통과 (6.88ms, 13.4MB)
테스트 8 〉	통과 (7.01ms, 13.5MB)
테스트 9 〉	통과 (7.28ms, 13.5MB)
테스트 10 〉	통과 (7.38ms, 13.6MB)
테스트 11 〉	통과 (6.54ms, 13.1MB)
테스트 12 〉	통과 (6.50ms, 13.1MB)
테스트 13 〉	통과 (7.70ms, 13.5MB)
테스트 14 〉	통과 (6.54ms, 13.1MB)
테스트 15 〉	통과 (6.92ms, 13.2MB)
테스트 16 〉	통과 (6.47ms, 13.1MB)
테스트 17 〉	통과 (6.65ms, 13.2MB)
테스트 18 〉	통과 (6.94ms, 13MB)

효율성 테스트

테스트 1 〉	통과 (61.26ms, 52.4MB)
테스트 2 〉	통과 (63.54ms, 53.1MB)
테스트 3 〉	통과 (66.54ms, 52.2MB)
테스트 4 〉	통과 (63.43ms, 52.3MB)

채점 결과

정확성: 40.0

효율성: 60.0

합계: 100.0 / 100.0