다트게임

Posted on Edited on In , ,

문제정의

다트게임을 해서 총 몇점을 득점했는지 계산하는 문제이다. 점수는 0~10점이며 옵션에 따라 점수가 바뀔 수 있다. S는 해당 점수의 1제곱, D는 제곱, T는 세제곱을 하는 것이며, 은 이전 점수와 해당 점수의 2배(만약에 이전 점수가 없으면 해당 점수만 2배 한다.)이다. #은 해당 점수를 빼는 것이다. 과 #은 중첩될 수 있다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.util.*;

public class DartGame {

    //프로그래머스 문제풀이 level1 다트 게임
    public static void main(String[] args)
    {
        String dartResult = "1S2D*3T";
        int answer = 0;
        char[] arr = dartResult.toCharArray();
        Stack<Integer> s = new Stack<Integer>();
        for(int i = 0; i < arr.length; i++)
        {  
            if(Character.isDigit(arr[i]))
            {
                int n = Integer.parseInt(String.valueOf(arr[i]));
                if(Character.isDigit(arr[i+1]))
                {
                    n = 10;
                    i++;
                }
                if(arr[i+1] == 'S')
                    s.push(Integer.parseInt(String.valueOf(n)));
                else if(arr[i+1] == 'D')
                    s.push((int)Math.pow(n, 2));
                else
                    s.push((int)Math.pow(n, 3));
            }
            else if(arr[i] == '*')
            {
                if(s.size() == 1)
                {
                    int n = Integer.parseInt(String.valueOf(s.peek()));
                    s.pop();
                    s.push(n*2);
                }
                else
                {
                    int n1 = Integer.parseInt(String.valueOf(s.peek()));
                    s.pop();
                    int n2 = Integer.parseInt(String.valueOf(s.peek()));
                    s.pop();
                    s.push(n2*2);
                    s.push(n1*2);
                }
            }
            else if(arr[i] == '#')
            {
                int n = Integer.parseInt(String.valueOf(s.peek()));
                s.pop();
                s.push(n*(-1));
            }
            
        }
        while(!s.empty())
        {
            answer += s.peek();
            s.pop();
        }
        System.out.print(answer);
    }
    
}

부분부분 살펴보자. 일단 스트링을 문자배열로 쪼갠다음 이 문자를 하나씩 보면서 계산할 것이다. *옵션을 계산하기 위해 스택도 함께 선언하였다. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if(Character.isDigit(arr[i]))
{
    int n = Integer.parseInt(String.valueOf(arr[i]));
    if(Character.isDigit(arr[i+1]))
    {
        n = 10;
        i++;
    }
    if(arr[i+1] == 'S')
        s.push(Integer.parseInt(String.valueOf(n)));
    else if(arr[i+1] == 'D')
        s.push((int)Math.pow(n, 2));
    else
        s.push((int)Math.pow(n, 3));
}
에 대해서 처리해주는 부분이다. 일단 들어온 문자가 숫자인지 확인한다. 이때 10에 대한 처리를 따로 한다. 똑같은 1이 들어와도 1일 수도 있고, 10일 수도 있기 때문이다. 이를 알기 위해 다음 문자도 숫자인지 확인하고 숫자라면 n에 10을 대입한다. 그리고 S,D,T에 따른 제곱처리를 하고 스택에 쌓는다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
else if(arr[i] == '*')
{
    if(s.size() == 1)
    {
        int n = Integer.parseInt(String.valueOf(s.peek()));
        s.pop();
        s.push(n*2);
    }
    else
    {
        int n1 = Integer.parseInt(String.valueOf(s.peek()));
        s.pop();
        int n2 = Integer.parseInt(String.valueOf(s.peek()));
        s.pop();
        s.push(n2*2);
        s.push(n1*2);
    }
}

숫자와 S,D,T에 대한 처리를 모두 했으니, 다음은 에 대해서 처리하자. 은 이전 점수와 현재 점수를 2배 처리하는 것이다. 이전 점수가 없을 수도 있으니 스택의 사이즈에 따라 달리한다.

1
2
3
4
5
6
else if(arr[i] == '#')
{
    int n = Integer.parseInt(String.valueOf(s.peek()));
    s.pop();
    s.push(n*(-1));
}

#인경우 스택의 top원소를 빼내어 -1을 곱한 뒤, 다시 집어넣는다. 이 과정을 dartResult가 끝날 때 까지 하므로 여기서의 시간복잡도는 dartResult의 길이를 n이라 할 때, \(O(n)\)이다. 

1
2
3
4
5
while(!s.empty())
{
    answer += s.peek();
    s.pop();
}
다트 게임의 점수를 모두 합산하면 정답이다. 이 부분도 \(O(n)\)이다. 따라서 최종 시간복잡도는 \(O(n)\)이다.

테스트



프로그래머스 마지막 level1을 풀었다. 그래도 올해가 끝나기 전에 풀어서 기쁘다. 앞으로는 더 어려운 문제들이 있겠지만 포기하지말고 끝까지 풀어보자. 물러서지 말자!