문제

차분하게 문자열을 다루는 문제

1. 다트게임 결과는 문자열로 주어집니다. (예: 1S2D*3T )

2. 게임 횟수 총 3번

3. 각 게임에서 얻을 수 있는 점수 0 ~ 10점 (10은 길이가 2인 문자열임을 주의)

4. S, D, T (1제곱, 2제곱, 3제곱)
   게임당 한개씩만 나옵니다.

5. ' * '

• 첫번째 게임인 경우 - 현재 점수 * 2
• 두번째, 세번째 게임인 경우 - 현재와 바로 전 점수 * 2

6. ' # '

• 현재 점수 * -1

7. • 와 , 와 # 는 중첩 가능

8. *, # 는 둘 중 하나만 존재, 없을 수도 있습니다.

3번의 게임에서 얻은 점수 합을 출력하세요.

문제링크

---

1. 첫인상

그렇게 어려워 보이지는 않습니다.

구현 문제의 경우 저는 다음과 같이 합니다.

1) 차분하게 문제를 정리

다시 문제 확인 안 할 정도로, 빼먹은 조건이 없는지 검토

위의 문제의 란에 적은 내용이 손으로 정리한 내용입니다.

2) 프로세스 정리

1. 길이 3인 int 배열을 만든다. (어떤 자료구조 사용할지 생각)
2. 각 숫자마다 수식 계산 -> if else 로직
3. 결과 합산
4. 출력

2. 시간 복잡도

길이 n인 문자열에 각 수식 계산
O(n) 3(최대 3 거듭 제곱) = O(n) 상수생략

문자열 최대 길이 9
1억에 1초 걸리기 때문에 시간안에 충분히 풀 수 있습니다.

3. 코드

1) c++

#include <string>
#define max_int 4
using namespace std;

/*
    시간 복잡도: O(n)
    공간 복잡도: O(n)
    사용한 알고리즘: 거듭제곱
    사용한 자료구조: 배열
 */

/*
   거듭 제곱
   3제곱 까지 이기 때문에
   num * num * num 해도 되고
   반복문 써도 되고
   분할해서 DP 써도 되고
 */
int pow(int num, char c){
    int result = num;
    int a = 0;
    if(c == 'S') a = 1;
    else if(c == 'D') a = 2;
    else a = 3;

    for(int i=2; i<=a; i++) {
        result = result * num;
    }

    return result;
}

int solution(string dartResult) {
    // 1. 입력 및 초기화
    int answer = 0;
    int idx = 0, a[max_int] = {0, 0, 0, 0};
    int size = (int)dartResult.size();

    // 2. 로직 수행
    for(int i=0; i < size; i++){
        char cur = dartResult[i];

        // 1) 거듭 제곱 진행합니다.
        if(cur == 'S' || cur == 'D' || cur == 'T'){
            a[idx] = pow(a[idx], cur);
        }
        // 2) 2배를 해줍니다.
        else if(cur == '*'){
            /*
                첫번째 게임인 경우 - 현재 점수 * 2
                두번째, 세번째 게임인 경우 - 현재와 바로 전 점수 * 2
             */
            int start_idx = idx == 1 ? 1 : idx - 1;

            for(int i=start_idx; i<=idx; i++){
                a[i] = a[i] * 2;
            }
        }
        // 3) 현재 점수를 -1배 합니다.
        else if(cur == '#'){
            a[idx] = a[idx] * -1;
        }
        // 4) 현재 숫자를 검사합니다.
        else{
            // 아스키코드에서 숫자를 추출합니다.
            int num = cur - '0';

            // 만약 10인경우 (길이 2인 문자열)
            if(cur == '1'){
                if(i < size - 1 && dartResult[i + 1] == '0') {
                    num = 10;
                }
            }

            idx++;
            a[idx] =  num;
            if(num == 10) i += 1;
        }
    }

    // 3. 결과 합산
    for(int i=1; i<=3; i++) {
        answer += a[i];
    }

    // 4. 출력
    return answer;
}

2) java

/*
    시간 복잡도: O(n)
    공간 복잡도: O(n)
    사용한 알고리즘: 거듭제곱
    사용한 자료구조: 배열
 */

class Solution {
    /*
    거듭 제곱
    3제곱 까지 이기 때문에
    num * num * num 해도 되고
    반복문 써도 되고
    분할해서 DP 써도 되고
    */    
    public int pow(int num, char c){
        int result = num;
        int a = 0;
        if(c == 'S') a = 1;
        else if(c == 'D') a = 2;
        else a = 3;

        for(int i=2; i<=a; i++) {
            result = result * num;
        }

        return result;
    }

    public int solution(String dartResult) {
        // 1. 입력 및 초기화
        int answer = 0;
        int idx = 0, a[] = new int[4];
        int size = (int)dartResult.length();

        // 2. 로직 수행
        for(int i=0; i < size; i++){
            char cur = dartResult.charAt(i);

            // 1) 거듭 제곱 진행합니다.
            if(cur == 'S' || cur == 'D' || cur == 'T'){
                a[idx] = pow(a[idx], cur);
            }
            // 2) 2배를 해줍니다.
            else if(cur == '*'){
                /*
                    첫번째 게임인 경우 - 현재 점수 * 2
                    두번째, 세번째 게임인 경우 - 현재와 바로 전 점수 * 2
                 */
                int start_idx = idx == 1 ? 1 : idx - 1;

                for(int j=start_idx; j<=idx; j++){
                    a[j] = a[j] * 2;
                }
            }
            // 3) 현재 점수를 -1배 합니다.
            else if(cur == '#'){
                a[idx] = a[idx] * -1;
            }
            // 4) 현재 숫자를 검사합니다.
            else{
                // 아스키코드에서 숫자를 추출합니다.
                int num = cur - '0';

                // 만약 10인경우 (길이 2인 문자열)
                if(cur == '1'){
                    if(i < size - 1 && dartResult.charAt(i+1) == '0') {
                        num = 10;
                    }
                }

                idx++;
                a[idx] =  num;
                if(num == 10) i += 1;
            }
        }

        // 3. 결과 합산
        for(int i=1; i<=3; i++) {
            answer += a[i];
        }

        // 4. 출력
        return answer;
    }
}

3) python3

'''
    시간 복잡도: O(n)
    공간 복잡도: O(n)
    사용한 알고리즘: 거듭제곱
    사용한 자료구조: 배열
'''

'''
   거듭 제곱
   3제곱 까지 이기 때문에
   num * num * num 해도 되고
   반복문 써도 되고
   분할해서 DP 써도 되고
'''

def pow(num, c):
    result = num
    a = 0
    
    if c == 'S': a = 1
    elif c == 'D': a = 2
    else: a = 3

    for i in range(2, a+1):
        result = result * num

    return result


def solution(dartResult):
    # 1. 입력 및 초기화
    answer = 0
    idx = 0
    a = [0 for _ in range(4)]
    size = len(dartResult)

    # 2. 로직 수행
    i = 0
    while i < size:
        cur = dartResult[i]

        # 1) 거듭 제곱 진행합니다.
        if cur == 'S' or cur == 'D' or cur == 'T':
            a[idx] = pow(a[idx], cur)
        # 2) 2배를 해줍니다.
        elif cur == '*':
            '''
                첫번째 게임인 경우 - 현재 점수 * 2
                두번째, 세번째 게임인 경우 - 현재와 바로 전 점수 * 2
            '''
    
            start_idx = 0
            if idx == 1: start_idx = 1
            else: start_idx = idx - 1

            for j in range(start_idx, idx + 1):
                a[j] *= 2
                
        # 3) 현재 점수를 -1배 합니다.
        elif cur == '#':
            a[idx] = a[idx] * -1
                
        # 4) 현재 숫자를 검사합니다.
        else:
            # 아스키코드에서 숫자를 추출합니다.
            num = ord(cur) - ord('0')

            # 만약 10인경우 (길이 2인 문자열)
            if cur == '1':
                if i < size - 1 and dartResult[i + 1] == '0':
                    num = 10

            idx += 1
            a[idx] =  num
            if num == 10: 
                i = i + 1

        i = i + 1                

    # 3. 결과 합산
    for i in range(1, 4):
        answer += a[i]

    # 4. 출력
    return answer

4) javascript

/*
    시간 복잡도: O(n)
    공간 복잡도: O(n)
    사용한 알고리즘: 거듭제곱
    사용한 자료구조: 배열
 */

/*
   거듭 제곱
   3제곱 까지 이기 때문에
   num * num * num 해도 되고
   반복문 써도 되고
   분할해서 DP 써도 되고
 */

function pow(num, c){
    let result = num;
    let a = 0;
    if(c == 'S') a = 1;
    else if(c == 'D') a = 2;
    else a = 3;

    for(let i=2; i<=a; i++) {
        result = result * num;
    }

    return result;
}

function solution(dartResult) {
    // 1. 입력 및 초기화
    let answer = 0;
    let idx = 0;
    let a = [0, 0, 0, 0];
    let size = dartResult.length;

    // 2. 로직 수행
    for(let i=0; i < size; i++){
        let cur = dartResult[i];

        // 1) 거듭 제곱 진행합니다.
        if(cur == 'S' || cur == 'D' || cur == 'T'){
            a[idx] = pow(a[idx], cur);
        }
        // 2) 2배를 해줍니다.
        else if(cur == '*'){
            /*
                첫번째 게임인 경우 - 현재 점수 * 2
                두번째, 세번째 게임인 경우 - 현재와 바로 전 점수 * 2
             */
            let start_idx = idx == 1 ? 1 : idx - 1;

            for(let j=start_idx; j<=idx; j++){
                a[j] = a[j] * 2;
            }
        }
        // 3) 현재 점수를 -1배 합니다.
        else if(cur == '#'){
            a[idx] = a[idx] * -1;
        }
        // 4) 현재 숫자를 검사합니다.
        else{
            // 아스키코드에서 숫자를 추출합니다.
            let num = cur - '0';

            // 만약 10인경우 (길이 2인 문자열)
            if(cur == '1'){
                if(i < size - 1 && dartResult[i + 1] == '0') {
                    num = 10;
                }
            }

            idx++;
            a[idx] =  num;
            if(num == 10) i += 1;
        }
    }

    // 3. 결과 합산
    for(let i=1; i<=3; i++) {
        answer += a[i];
    }

    // 4. 출력
    return answer;
}