Codility:Lesson5(Prefix Sums) - GenomicRangeQuery

안녕하세요~

디벨로퍼입니다~~

 

오늘은 GenomicRangeQuery 문제 풀이하도록 하겠습니다.

문제풀이 하실분들은 아래 링크 참조해주세요.

 

========================================================================

https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/

GenomicRangeQuery coding task - Learn to Code - Codility

========================================================================

 

문제는 아래와 같습니다.

주어진 string의 범위 중, 가장 작은 숫자를 찾는 문제입니다.

 

P, Q 두 벡터에 숫자가 들어가 있습니다. 

숫자가 의미하는 정보는 

P 벡터는 시작 index, Q 벡터는 마지막 index 입니다.

 

P, Q의 각 벡터의 처음 원소부터 마지막 원소까지 모두 순회했을 때,

가장 작은 값을 찾는 문제입니다.

 

P, Q 벡터의 길이는 최대 5만, 주어진 스트링은 10만이므로

O(N*M)이라면 Timeout이 될거라고 생각했습니다.

 

아래는 처음 제출한 코드입니다.

 

// you can use includes, for example:
// #include <algorithm>
#include <string>
#include <iostream>
#include <climits>
//#define DEBUG
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

void getMin(char &c, int &min)
{
    int val = -1;
    #ifdef DEBUG
    std::cout << "character : " << c << ", min : " << min << std::endl;
    #endif
    if(c == 'A') val = 1;
    else if(c == 'C') val = 2;
    else if(c == 'G') val = 3;
    else val = 4;
    if(min > val) min = val;
}

vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
    // write your code in C++14 (g++ 6.2.0)
    vector<int> res;
    int min;
    vector<int>::iterator pIter, qIter;
    int start, end;
    for(pIter = P.begin(), qIter = Q.begin(); pIter != P.end(), qIter != Q.end(); ++pIter, ++qIter)
    {
        min = INT_MAX;
        start = *pIter, end = *qIter;
        #ifdef DEBUG
        std::cout << "start : " << start << " end : " << end << std::endl;
        #endif
        for(int idx = start; idx <= end; ++idx)
        {
            getMin(S[idx], min);
        }
        res.push_back(min);
    }
    return res;
}

O(N*M) 이라서 당연히 결과는 TLE가 나왔습니다.

 

이해가 힘들어 구글의 힘을 빌려버렸습니다.

#include <algorithm>

bool compare(pair<int, int> a, pair<int, int> b) {
	if (a.first == b.first)
		return a.second < b.second;
	else
		return a.first < b.first;
}

vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
	vector<int> ans;

	vector<pair<int, int>> v;

	for (int i = 0; i < S.size(); i++) {
		int ch;
		if (S[i] == 'A')
			ch = 1;
		else if (S[i] == 'C')
			ch = 2;
		else if (S[i] == 'G')
			ch = 3;
		else
			ch = 4;
		v.push_back(make_pair(ch, i));
	}

	sort(v.begin(), v.end(), compare);
	
	for (int i = 0; i < P.size(); i++) {
		for (int j = 0; j < v.size(); j++) {
			if (P[i] <= v[j].second && v[j].second <= Q[i]) {
				ans.push_back(v[j].first);
				break;
			}
		}
	}

	return ans;
}

 

제가 봤던 예시입니다.

주어진 스트링의 원소값과 인덱스를 pair로 벡터에 넣어 

1. 값 / 2. 인덱스 값

으로 정렬합니다.

그리고 주어진 P, Q 벡터의 사이즈만큼 순회하면서

인덱스값이 P, Q 사이에 포함되면 정렬이 되었으므로 가장 작은 값이라고 판단하고 결과에 넣어줍니다.