문제

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

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

  2. 게임 횟수 총 3번

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

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

  5. ' * '

  • 첫번째 게임인 경우 - 현재 점수 * 2
  • 두번째, 세번째 게임인 경우 - 현재와 바로 전 점수 * 2
  1. ' # '
  • 현재 점수 * -1
    • , 와 # 는 중첩 가능
  1. *, # 는 둘 중 하나만 존재, 없을 수도 있습니다.

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;
}
profile
callmeskye

0개의 댓글