[2018 Kakao Blind Recruitment 1차] Q2. 다트 게임(C++, Python, JAVA)

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

 

알고리즘 분류

Implementation

 

풀이

주어진 조건을 곧이곧대로 구현하면 됩니다. 수는 따로 분리해 배열에 둘 것이고 10에 주의하며 스트링 파싱을 하면 됩니다. 삐끗하면 인덱스가 배열 바깥으로 나갈 수 있음에 주의해야합니다.

 

코드(C++)

#include <bits/stdc++.h>
using namespace std;

int solution(string dartResult) {
    int score[3];
    int idx = 0;
    for(int i = 0; i < 3; i++){
        // 점수
        // 문자열 세트에서 두 번째 글자가 숫자일 경우
        if('0' <= dartResult[idx+1] && dartResult[idx+1] <= '9'){
            score[i] = 10;
            idx += 2;
        }
        else{
            score[i] = dartResult[idx] - '0';
            idx++;
        }
        // 보너스
        if(dartResult[idx] == 'D') score[i] *= score[i];
        else if(dartResult[idx] == 'T') score[i] *= score[i]*score[i];
        idx++;
        // 옵션
        if(idx == dartResult.size() || '0' <= dartResult[idx] && dartResult[idx] <= '9') continue;
        if(dartResult[idx] == '*'){
            score[i] *= 2;
            if(i != 0) score[i-1] *= 2;
        }
        else if score[i] = -score[i];
        idx++;
    }
    return score[0] + score[1] + score[2];
}

 

점수를 저장할 score 배열을 두었습니다. 바깥 for문은 3번의 게임을 나타내고 idx는 dartResult에서 현재 확인중인 글자의 인덱스를 나타냅니다.

 

코드(Python)

def solution(dartResult):
    score = [0, 0, 0]
    for i in range(3):
        # 점수
        if dartResult[1].isdigit():
            score[i] = 10
            dartResult = dartResult[2:]
        else:
            score[i] = int(dartResult[0])
            dartResult = dartResult[1:]
        # 보너스
        if dartResult[0] == 'D': score[i] = score[i] ** 2
        elif dartResult[0] == 'T': score[i] = score[i] ** 3
        dartResult = dartResult[1:]
        # 옵션
        if not dartResult or dartResult[0].isdigit():
            continue
        if dartResult[0] == '*':
            score[i] *= 2
            if i != 0: score[i-1] *= 2
        else: score[i] = -score[i]
        dartResult = dartResult[1:]
    return sum(score)

점수, 보너스, 옵션을 차례대로 계산했고 isdigit 메소드를 활용했습니다.

 

매번 맨 앞 글자를 가지고 분석한 이후에는 dartResult = dartResult[1:] 을 통해 앞 글자를 잘라내었는데 이 명령은 매번 O(N)이 걸리기 때문에 굉장히 비효율적인 코드입니다. 차라리 dartResult를 뒤집어서 리스트로 만든 후 맨 끝 글자부터 보고 pop을 하는게 바람직합니다. 그러나 dartResult의 글자가 매우 작아 시간복잡도가 사실상 상관이 없기 때문에 읽을 때의 편의를 위해 지금처럼 코드를 구성했습니다. dartResult의 길이가 최대 100,000과 같이 컸다면 지금처럼 코드를 짜면 안됩니다.

 

정규표현식을 이용할 수도 있지만 정규표현식을 사용할 경우 시간복잡도의 가늠이 어려워진다는 점을 주의해야 합니다.

 

코드(JAVA)

class Solution {
    public int solution(String dartResult) {
        int[] score = new int[3];
        int idx = 0;
        for(int i = 0; i < 3; i++){
            // 점수
            // 문자열 세트에서 두 번째 글자가 숫자일 경우
            if('0' <= dartResult.charAt(idx+1) && dartResult.charAt(idx+1) <= '9'){
                score[i] = 10;
                idx += 2;
            }
            else{
                score[i] = dartResult.charAt(idx) - '0';
                idx++;
            }
            // 보너스
            if(dartResult.charAt(idx) == 'D') score[i] *= score[i];
            else if(dartResult.charAt(idx) == 'T') score[i] *= score[i]*score[i];
            idx++;
            // 옵션
            if(idx == dartResult.length() || '0' <= dartResult.charAt(idx) && dartResult.charAt(idx) <= '9') continue;
            if(dartResult.charAt(idx) == '*'){
                score[i] *= 2;
                if(i != 0) score[i-1] *= 2;
            }
            else score[i] = -score[i];
            idx++;
        }
        return score[0] + score[1] + score[2];
    }
}

점수를 저장할 score 배열을 두었습니다. 바깥 for문은 3번의 게임을 나타내고 idx는 dartResult에서 현재 확인중인 글자의 인덱스를 나타냅니다.