728x90
반응형

문제:

풀이방법:

 연산자를 계산하는 방법으로 주로 스택을 사용하기 때문에 스택을 사용하고, 수식의 갯수가 3개이므로 최대 6가지 조합이 가능하기 때문에 브루트 포스 방법을 사용해서 모든 케이스에 대해 계산을 하고 그 중 최대값을 찾는 방법을 사용한다.

 우선 정규표현식과 itertools의 permutations을 사용해서 입력받은 expression에 대해서 숫자와 수식을 분리해내고, 연산자들의 우선순위를 만든다.

 생성된 우선순위별로 숫자와 연산자들을 스택에 넣고, 연산자가 현재 해당하는 우선순위의 연산자라면 숫자 스택에서 두 개를 빼고, 연산자 스택에서 하나를 빼서 연산을 하고 다시 숫자 스택에 넣도록 한다.

 이 과정을 우선순위와 연산자별로 계속 반복해서 하고 이 중 max 값을 찾아서 반환하도록 한다.

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
def calculate(a,b,op):
    if op=="+":
        return a+b
    elif op=="*":
        return a*b
    else:
        return a-b
 
def solution(expression):
    import re
    from itertools import permutations
    prior = list(permutations(["+","*","-"],3))
    digit = re.compile("[0-9]+")
    operator = re.compile("[^0-9]")
    numbers = list(map(int,digit.findall(expression)))
    oper = list(operator.findall(expression))
    
    answer = 0
    for pr in prior:
        number = numbers
        ope = oper
        for i in range(3):
            stack = [number[0]]
            stack_op = []
            count = 1
            while count < len(number):
                stack.append(number[count])
                stack_op.append(ope[count-1])
                count+=1
                if stack_op[-1]==pr[i]:
                    b = stack.pop(-1)
                    a = stack.pop(-1)
                    op = stack_op.pop(-1)
                    
                    stack.append(calculate(a,b,op))
            number = stack
            ope = stack_op
        answer = max(answer,abs(number[0]))   
    return answer
 cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/67257

 

코딩테스트 연습 - 수식 최대화

IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 �

programmers.co.kr

 

728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[Programmers]2020 카카오 인턴십. 보석 쇼핑  (0) 2020.07.16
[BOJ]2164. 카드2  (0) 2020.07.14
[Programmers]2020 카카오 인턴십. 키패드 누르기  (0) 2020.07.07
[BOJ]1543. 문서 검색  (0) 2020.07.02
[BOJ]5525. IOIOI  (0) 2020.06.30
728x90
반응형

문제:

풀이방법:

규칙 중 4를 구현하는 것이 핵심인 문제다.

 solution함수는 1,4,7 입력이 들어온다면 왼쪽 엄지손가락을 사용하고, 해당 번호로 left를 이동시키고, 3,6,9가 들어온다면 오른쪽 엄지손가락을 사용하고 right를 이동시킨다. 이제 2,5,8,0이 들어오는 경우 leftDistance와 rightDistance를 사용해서 거리를 계산한다. 더 작은 쪽의 엄지손가락으로 이동을 하고, 만약 같다면 hand의 우선순위에 따라 움직이도록 한다.

 leftDistance는 입력을 해야하는 숫자가 2,5,8,0일 때, 왼쪽 엄지손가락과 거리를 계산하는 함수다.

만약 이전 왼쪽 엄지 손가락이 2,5,8이고 입력해야 할 숫자가 0이라면 각 케이스마다 거리를 return 하게 만들고, 나머지는 두 수의 차를 3으로 나눈 몫을 반환하도록 한다. 왼쪽 엄지 손가락이 1,4,7에 있다면 이를 가운데 키패드로 옮겨주고 leftDistance로 재귀적으로 거리를 계산하도록 만든다. 이제 나머지 케이스인 0에 있거나, 초기 상태인 *에 있던 경우에 대해서만 거리를 계산해주면 된다.

 rightDistance로 leftDistance와 비슷하게 계산을 하도록 한다.

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
def leftDistance(num,left):
    if left in [2,5,8]:
        if num == 0:
            if left ==2:
                return 3
            elif left == 5:
                return 2
            else:
                return 1
        return abs(left-num)//3
    elif left in [1,4,7]:
        return leftDistance(num,left+1)+1
    else:
        if left == -1:
            if num == 2:
                return 4
            elif num == 5:
                return 3
            elif num == 8:
                return 2
            else:
                return 1
        if num == 0:
            return 0
        elif num == 8:
            return 1
        elif num == 5:
            return 2
        else:
            return 3
        
def rightDistance(num,right):
    if right in [2,5,8]:
        if num == 0:
            if right ==2:
                return 3
            elif right == 5:
                return 2
            else:
                return 1
        return abs(right-num)//3
    elif right in [3,6,9]:
        return rightDistance(num,right-1)+1
    else:
        if right == -1:
            if num == 2:
                return 4
            elif num == 5:
                return 3
            elif num == 8:
                return 2
            else:
                return 1
        if num == 0:
            return 0
        elif num == 8:
            return 1
        elif num == 5:
            return 2
        else:
            return 3
def solution(numbers,hand):
    answer = ""
    left, right = -1, -1
    for num in numbers:
        if num in [1,4,7]:
            left = num
            answer += "L"
        elif num in [3,6,9]:
            right = num
            answer += "R"
        else:
            center_l = leftDistance(num,left)
            center_r = rightDistance(num,right)
            distance = center_l-center_r
            if distance > 0:
                right = num
                answer += "R"
            elif distance < 0:
                left = num
                answer += "L"
            else:
                if hand =="right":
                    right = num
                    answer+= "R"
                else:
                    left = num
                    answer += "L"
    return answer
 cs

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/67256

 

코딩테스트 연습 - 키패드 누르기

[1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL"

programmers.co.kr

 

728x90
반응형
저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]2164. 카드2  (0) 2020.07.14
[Programmers]2020 카카오 인턴십. 수식 최대화  (0) 2020.07.09
[BOJ]1543. 문서 검색  (0) 2020.07.02
[BOJ]5525. IOIOI  (0) 2020.06.30
[BOJ]11652. 카드  (0) 2020.06.25

+ Recent posts

티스토리툴바