[Pro] 계산 게임
문제
일렬로 놓인 카드들을 관리하면서 연속된 카드 4장의 점수를 계산하여 특정 점수(4장 카드 점수의 합을 20으로 나눈 나머지)가 나오는 구간을 찾아야 한다. 초기에는 카드 5장이 있으며, 이후 카드 5장을 기존 카드 리스트의 왼쪽 또는 오른쪽에 추가할 수 있다.
일반 카드에는 숫자가 적혀 있으며, -1은 조커 카드이다. 조커 카드의 값은 게임 도중 변경될 수 있다.
구현해야 하는 API는 다음과 같다.
void init(int mJoker, int mNumbers[5]);
void putCards(int mDir, int mNumbers[5]);
int findNumber(int mNum, int mNth, int ret[4]);
void changeJoker(int mValue);init
void init(int mJoker, int mNumbers[5]);게임을 초기화합니다.
- 현재 조커의 점수를
mJoker로 설정합니다. mNumbers[5]의 카드 5장을 최초 카드로 배치합니다.- 이전 테스트에서 사용한 모든 정보를 초기화합니다.
조커 점수는 mJoker % 20만 영향을 줍니다.
putCards
void putCards(int mDir, int mNumbers[5]);새로운 카드 5장을 추가합니다.
mDir == 0 : 현재 카드의 왼쪽에 추가
mDir == 1 : 현재 카드의 오른쪽에 추가예를 들어 현재 카드가
6 7 8 9 10이고
mNumbers = [1, 2, 3, 4, 5]라면,
mDir == 0
1 2 3 4 5 6 7 8 9 10mDir == 1
6 7 8 9 10 1 2 3 4 5이 됩니다.
findNumber
int findNumber(int mNum, int mNth, int ret[4]);현재 카드들을 왼쪽부터 확인했을 때,
점수가
mNum인 연속한 4장의 카드 중mNth번째 구간
을 찾습니다.
예를 들어 구간별 점수가
시작 위치 : 0 1 2 3 4 5
점수 : 9 10 10 13 9 13이고
findNumber(13, 2, ret);가 호출되면 두 번째 13인 시작 위치 5의 카드 4장을 찾아 ret에 저장합니다.
찾았다면
ret[0]
ret[1]
ret[2]
ret[3]에 해당 카드 4장을 넣고 1을 반환합니다.
존재하지 않으면 0을 반환합니다.
ret에는 카드의 실제 값이 저장되므로 조커 카드라면 -1이 그대로 반환됩니다.
changeJoker
void changeJoker(int mValue);현재 조커 카드의 점수를 변경합니다.
joker = mValue % 20;이후 findNumber()의 구간 점수 계산에는 변경된 조커 점수가 적용됩니다.
기존 카드의 배치 자체는 바뀌지 않습니다.
제약 사항은 다음과 같다.
- 각 테스트 케이스 시작 시
init()함수가 호출된다. - 각 테스트 케이스에서
putCards()함수의 호출 횟수는 10,000회 이하이다. - 각 테스트 케이스에서 전체 함수의 총 호출 횟수는 15,000회 이하이다.
- 주어지는 카드 5장 내에 포함된 조커 카드 개수의 제한은 없다.
설명
카드들은 양 끝 왼쪽, 오른쪽에만 연속적으로 삽입되므로 deque를 생각할 수 있다.
조건에 맞는 카드를 탐색할 때는 모든 연속된 4장의 카드를 순차적으로 탐색하면 이다. 조건에 맞는 카드를 탐색하는 메서드는 최대 5,000번 호출 가능하며, 카드 수는 50,000개까지 추가될 수 있다. 따라서 최악의 경우 50,000 * 5,000 = 250,000,000번의 탐색을 하게 된다.
매 탐색마다 연속된 4장의 카드를 계산할 필요는 없다. 카드가 추가될 때 각 구간의 점수를 미리 계산한다면 findNumber()가 호출될 때 카드의 합을 다시 구할 필요가 없다.
또한 카드가 추가되어도 기존에 존재하던 카드 구간의 합은 변하지 않으므로 새롭게 추가된 구간의 합만 구하면 된다.
deque<int> scores;
다만 여전히 findNumber() 가 호출되면 구간 합을 저장한 배열을 순회해야 하므로 인 것은 변하지 않는다.
특정 구간 합 값이 존재하는 인덱스를 저장하면 구간 합을 저장한 배열을 순회하지 않고 위치를 찾을 수 있다.
deque<int> idxList[20];예를 들어 idxList[7] = [0, 2, 5] 일 때, findNumber(7, 2, ret); 가 들어온다면 전체 구간을 순회하지 않고 idxList[7][1]; 로 두 번째 구간의 시작 위치를 찾을 수 있다.
단, 조커 값은 동적으로 변경되므로, 구간 합을 저장할 때 모든 조커 값에 대해 점수를 계산한다.
deque<int> idxList[20][20]; // 조커 값, 구간 합 점수예를 들어 현재 조커 값이 7이고, findNumber(19, 2, ret);가 들어왔을 때 idxList[7][19][1]를 살펴보면 된다.
코드
#include <deque>
using namespace std;
#define MAX_CARD 50000
int joker;
int beginIdx, endIdx;
int cards[MAX_CARD * 2 + 5];
// idxList[joker][score] = 해당 조건을 만족하는 4장 구간의 시작 인덱스
deque<int> idxList[20][20];
void updateIdx(int idx, int dir) {
int sum = 0;
int jokerCnt = 0;
for (int i = 0; i < 4; i++) {
if (cards[idx + i] == -1)
jokerCnt++;
else
sum += cards[idx + i];
}
// 조커 값 0~19에 대해 미리 등록한다.
for (int j = 0; j < 20; j++) {
int score = (sum + jokerCnt * j) % 20;
if (dir == 0)
idxList[j][score].push_front(idx);
else
idxList[j][score].push_back(idx);
}
}
void init(int mJoker, int mNumbers[5]) {
joker = mJoker % 20;
beginIdx = endIdx = MAX_CARD;
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 20; j++) {
idxList[i][j].clear();
}
}
for (int i = 0; i < 5; i++) {
cards[endIdx++] = mNumbers[i];
}
// 초기 5장에서 가능한 4장 구간은 2개
updateIdx(beginIdx, 1);
updateIdx(beginIdx + 1, 1);
}
void putCards(int mDir, int mNumbers[5]) {
if (mDir == 0) {
beginIdx -= 5;
for (int i = 0; i < 5; i++) {
cards[beginIdx + i] = mNumbers[i];
}
// 왼쪽에 새로 생긴 5개 구간
for (int i = 4; i >= 0; i--) {
updateIdx(beginIdx + i, 0);
}
}
else {
int start = endIdx - 3;
for (int i = 0; i < 5; i++) {
cards[endIdx + i] = mNumbers[i];
}
endIdx += 5;
// 오른쪽에 새로 생긴 5개 구간
for (int i = 0; i < 5; i++) {
updateIdx(start + i, 1);
}
}
}
int findNumber(int mNum, int mNth, int ret[4]) {
deque<int>& list = idxList[joker][mNum];
if (mNth > list.size())
return 0;
int idx = list[mNth - 1];
for (int i = 0; i < 4; i++) {
ret[i] = cards[idx + i];
}
return 1;
}
void changeJoker(int mValue) {
joker = mValue % 20;
}시간복잡도
init()에서 , 나머지 메서드는 이다.
공간복잡도
카드를 저장하는 곳에서 이다.