문제
다트게임 - 2018 KAKAO BLIND RECRUITMENT
- 다트 게임은 총 3번의 기회로 구성된다.
- 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.
- 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수1 , 점수2 , 점수3 )으로 계산된- 다.
- 옵션으로 스타상() , 아차상(#)이 존재하며 스타상() 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다.
- 출력 : 0~10의 정수와 문자 S, D, T, *, #로 구성된 문자열이 입력될 시 총점수를 반환하는 함수를 작성하라.
- 입력 형식
점수|보너스|[옵션]으로 이루어진 문자열 3세트.
Fact
- 점수는 0~10이므로, 한자리 혹은 두자리일 수 있다.
- 옵션은 주어질 수도 아닐 수도 있으므로, 이를 확인해야 한다.
- 스타상은 해당 기회의 점수와 이전 기회의 점수를 2배로 만드므로, 각 기회의 점수들을 따로 저장해두어야 한다.
Solution 2 - 정규식 사용
다른 사람들의 풀이를 확인하니 정규식을 사용한 풀이들을 확인할 수 있었다. 정규식 풀이가 더 간단하고, 간결해보여서 정규식으로도 문제를 해결해보았다.
접근
- 점수 | 보너스 | [옵션]의 문자열 3세트를 파싱한다.
- 각 문자열 별로 점수, 보너스, 옵션을 파싱한다.
- 두 번째에서 얻은 정보로, 각 게임마다의 점수를 계산한다.
복잡도
- 공간 복잡도 : O(1)
- 입력의 길이와 상관없이 3번의 게임에 관한 점수를 저장하는 배열이 필요하다.
- 시간 복잡도 : O(N)
- 문자열의 처음부터 끝까지 1번 순회하게 된다.
코드
const N_GAME = 3;
const scoreRegex = /\d{1,2}/;
const bonusRegex = /[SDT]/;
const optionRegex = /[#*]/;
const getInfo = (string, regex) => string.match(regex);
const getScore = (string) => +getInfo(string, scoreRegex)[0];
const getBonus = (string) => getInfo(string, bonusRegex)[0];
const getOption = (string) => {
const option = getInfo(string, optionRegex);
return option ? option[0] : undefined;
};
const calcBonusScore = (score, bonus) => {
const powMap = {
S: 1,
D: 2,
T: 3,
};
return score ** powMap[bonus];
};
const solution = (dartResult) => {
const gameScore = [];
const gameInfo = dartResult.match(/(\d{1,2})([SDT])([*#])?/g);
gameInfo.forEach((game, i) => {
const score = getScore(game);
const bonus = getBonus(game);
const option = getOption(game);
const bonusScore = calcBonusScore(score, bonus);
if (option === "#") {
gameScore.push(bonusScore * -1);
} else if (option === "*") {
if (i !== 0) {
gameScore[i - 1] *= 2;
}
gameScore.push(bonusScore * 2);
} else {
gameScore.push(bonusScore);
}
});
const result = gameScore.reduce((sum, score) => sum + score, 0);
return result;
};
Solution 1 - 문자열 처음부터 끝까지 확인
접근
- 문자열의 첫 번째부터 마지막까지 확인하며 점수, 보너스, 옵션을 확인한다.
- 점수 parsing
(a). 현재 index부터 'S', 'D', 'T'가 존재하는지 확인하고, 그 중 가장 작은 index를 가져온다.
(b). 현재 index부터 (a)에서 찾은 index까지 substring으로 나눈 후, 숫자로 만들어서 반환한다. - 보너스 parsing
(a) 점수 parsing (a)에서 찾은 index가 bonus가 있는 index이다.
(b) 보너스를 key로 두고 해당 bonus에 대한 점수를 계산해주는 함수를 value로 두는 객체를 만든다.
(c) 보너스로 (b)에서 적합한 함수를 찾은 후, 인자에 점수 넣어서, 해당 보너스를 적용한 점수를 가져온다. - 옵션 파싱
(a) 보너스 다음 index가 '*', '#'이라면 옵션에 맞는 점수를 계산한다.
복잡도
- 공간 복잡도 : O(1)
- 입력의 길이와 상관없이 상수의 배열이 필요하다.
- 시간 복잡도 : O(N)
- 문자열의 처음부터 끝까지 1번 순회하게 된다.
알게된 점
- 종이에 코드를 작성할 때, 주어지는 input의 이름을 그대로 사용하자. 종이에 임의로 쓴 변수명을 따라 쓰다가 오류가 발생하게 된다.
- Array.filter는 주어진 조건이 일치하는 배열의 element만을 가져온다.
- Array.reduce에서 아무런 값도 반환하지 않으면, accumulator는 undefined가 된다.
-> 이전 accumulator를 반환하고 싶을 경우, 반드시 return accumulator를 하자.
코드
const NOT_FOUND = -1;
const NOT_DETERMINED = -1;
const getScore = (startIdx, input) => {
const bonus = ["S", "D", "T"];
const bonusIdx = new Array(bonus.length).fill().reduce((result, _, i) => {
const idx = input.indexOf(bonus[i], startIdx);
if (idx !== NOT_FOUND) {
if (result === NOT_DETERMINED) {
return idx;
}
return Math.min(result, idx);
}
return result;
}, NOT_DETERMINED);
return [+input.substring(startIdx, bonusIdx), bonusIdx];
};
const calcBonusScore = (score, bonus) => {
const bonusCalcMap = {
S: (score) => score,
D: (score) => score ** 2,
T: (score) => score ** 3,
};
return bonusCalcMap[bonus](score);
};
function solution(dartResult) {
const gameScore = [];
let i = 0;
while (i < dartResult.length) {
const [score, bonusIdx] = getScore(i, dartResult);
const bonusScore = calcBonusScore(score, dartResult[bonusIdx]);
const optIdx = bonusIdx + 1;
if (dartResult[optIdx] === "*") {
if (gameScore.length !== 0) {
gameScore[gameScore.length - 1] *= 2;
}
gameScore.push(bonusScore * 2);
i = optIdx + 1;
} else if (dartResult[optIdx] === "#") {
gameScore.push(bonusScore * -1);
i = optIdx + 1;
} else {
gameScore.push(bonusScore);
i = bonusIdx + 1;
}
}
const answer = gameScore.reduce((sum, score) => sum + score, 0);
return answer;
}
