https://programmers.co.kr/learn/courses/30/lessons/67257
코딩테스트 연습 - 수식 최대화
IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과
programmers.co.kr
풀이
수식의 분리(숫자와 연산자 배열)
먼저 수식을 숫자와 연산자로 분리합니다. get_numbers_and_exps() 함수는 수식을 받아 숫자 배열과 연산자 배열을 반환합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
def get_numbers_and_exps(expression): # 수식을 숫자와 연산자 배열로 분리
exps = []
numbers = []
# 수식 분석
start_num_idx = 0 # 숫자의 시작을 저장할 index
for i in range(len(expression)):
if not expression[i].isdigit(): # i번째 문자가 연산 문자인 경우
numbers.append(expression[start_num_idx:i]) # start~i-1번째까지 slice하여 숫자 배열에 추가
exps.append(expression[i]) # i번째는 연산문자 배열에 추가
start_num_idx = i + 1 # 다음 숫자 시작 index는 i+1
numbers.append(expression[start_num_idx:]) # for문이 끝나고 난후 마지막 숫자를 숫자 배열에 추가
return numbers, exps
|
cs |
만약 expression[i]가 숫자가 아닌 경우(연산 문자인 경우) 해당 index를 기준으로 숫자와 문자를 구분하여 삽입합니다. 이 때 start_num_idx에 숫자가 몇 번째 인덱스 부터 시작하는지 저장하여 적절하게 숫자를 분할해 줍니다.
expression[start_num_idx:i] <- 연산자 이전의 숫자
expression[i] <- 연산자
연산자 우선순위 연산 결과가 최대가 되는 값 탐색
연산자의 우선순위를 순열을 통해서 탐색합니다. itertools의 permutations 함수와 set 자료구조를 이용합니다. set 자료구조를 이용하여 exps 배열의 연산자 중복을 삭제합니다. 그리고 우선순위가 - -> + -> * 인 경우와 + -> - -> * 인 경우의 결과가 다르기 때문에 순서가 있는 경우의 수인 순열을 통해서 연산자 우선순위를 탐색합니다.
|
1
2
3
4
|
# 순열을 이용하여 모든 경우 탐색
for exp_seq in permutations(list(set(exps))):
# exp_seq에서 우선순위 별로 하나씩 문자를 가져옴
ret = max(ret, calc(numbers.copy(), exps.copy(), exp_seq))
|
cs |
그리고 calc() 함수에서 숫자배열, 연산자 배열, 연산자 우선순위를 이용하여 결과를 계산하고 ret과 비교하여 항상 더 큰 값이 ret에 저장되도록 구성합니다.
|
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
|
def calc(numbers, exps, exp_seq):
for exp in exp_seq:
before_exp_used = False # 이전에 수식어가 계산을 했는지 안했는지 여부 저장
new_nums_tmp = [] # 계산 후의 숫자 저장
for i, num in enumerate(numbers):
if i == len(numbers) - 1: # 마지막 num의 경우
if not before_exp_used: # 이전의 수식어가 사용되지 않았다면
new_nums_tmp.append(num) # 새로운 숫자 배열에 추가
break
if exp == exps[i]: # 현재 우선순위의 연산자를 만난 경우
sub_result = str(eval(numbers[i] + exp + numbers[i + 1])) # i, i+1번째 숫자로 계산
numbers[i + 1] = sub_result # numbers[i+1]에 계산 결과 저장
if before_exp_used: # 이전에 계산을 한 경우(현재 우선순위의 연산자가 연속으로 나온 경우)
new_nums_tmp[-1] = sub_result # 마지막에 저장된 숫자를 갱신함
else:
new_nums_tmp.append(sub_result) # 이전에 계산을 하지 않은 경우 새로운 숫자 배열에 추가
before_exp_used = True
else:
if not before_exp_used: # 이전에 계산을 하지 않은 경우
new_nums_tmp.append(num) # 새로운 숫자배열에 숫자만 추가
before_exp_used = False
numbers = new_nums_tmp.copy() # new_nums로 배열 갱신
exps = [e for e in exps if e != exp] # 이전 연산자를 제외한 연산자만 남도록 갱신
return abs(int(numbers[0])) # 절댓값 반환
|
cs |
- calc() 함수에서는 exp_seq에서 우선순위대로 연산자를 가져옵니다.
- 그리고 numbers 배열과 exps 배열을 확인하여 같은 연산자를 만난 경우 numbers[i]와 numbers[i+1]번째와 계산하여 sub result에 저장합니다.
- 그리고 new_nums_tmp[]에 해당 숫자를 추가하고, numbers[i+1] 또한 sub_result로 바꿔줍니다. (연산자가 중복되는 경우 반영하기 위해)
- numbers를 다 확인하고 나면 numbers를 new_nums_tmp 배열로 교체하고, exps 배열에서 연산이 끝난 연산자를 삭제합니다. 이 때 len(numbers)는 항상 len(exps)+1이 되어야합니다.(연산자 개수 보다 숫자 개수가 하나 더 많아야함)
- 모든 계산이 끝나고나면 numbers에는 숫자 하나가 남아있으며, exps에는 아무 연산자도 남아있지 않으므로 numbers[0]의 절댓값을 반환합니다.
연산 중간 과정을 그림으로 표현하면 다음과 같습니다.
'*' 연산이 우선순위가 높으므로 먼저 계산하고 결과를 이용하여 새로운 new_nums와 new_exps 배열 만들어줍니다. 그리고 numbers와 exps를 위 배열로 교체하여 새로운 숫자와 연산자들로 계산되도록 합니다.
모든 연산자에 대해서 계산이 끝나고 나면 new_nums 배열에 연산 결과가 저장되어 있습니다. 이 값의 절댓값을 반환합니다.
(return abs(int(numbers[0])))
주의해야할 부분은 같은 연산자가 연속으로 나오는 경우 입니다.
연산자가 연속으로 나오는 경우를 방지하여 numbers[i+1]에도 연산 결과를 저장하여 다음 계산시 연산이 완료된 결과를 이용하여 연산하도록 합니다.
또한 두번째 연산이 완료되고나면 new_nums에 새로운 숫자를 추가하는 것이 아니라 마지막에 저장된 숫자를 연산 결과로 바꿔줍니다. (이미 new_nums에 저장된 숫자는 연산에 이용했으므로)
모든 연산자 우선순위 경우에 대하여 위의 작업을 완료하고 나면 최댓값을 알 수 있습니다. 전체 소스코드는 다음과 같습니다.
전체 소스 코드
|
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
|
from itertools import permutations
from copy import deepcopy
def get_numbers_and_exps(expression): # 수식을 숫자와 연산자 배열로 분리
exps = []
numbers = []
# 수식 분석
start_num_idx = 0 # 숫자의 시작을 저장할 index
for i in range(len(expression)):
if not expression[i].isdigit(): # i번째 문자가 연산 문자인 경우
numbers.append(expression[start_num_idx:i]) # start~i-1번째까지 slice하여 숫자 배열에 추가
exps.append(expression[i]) # i번째는 연산문자 배열에 추가
start_num_idx = i + 1 # 다음 숫자 시작 index는 i+1
numbers.append(expression[start_num_idx:]) # for문이 끝나고 난후 마지막 숫자를 숫자 배열에 추가
return numbers, exps
def calc(numbers, exps, exp_seq):
for exp in exp_seq:
before_exp_used = False # 이전에 수식어가 계산을 했는지 안했는지 여부 저장
new_nums_tmp = [] # 계산 후의 숫자 저장
for i, num in enumerate(numbers):
if i == len(numbers) - 1: # 마지막 num의 경우
if not before_exp_used: # 이전의 수식어가 사용되지 않았다면
new_nums_tmp.append(num) # 새로운 숫자 배열에 추가
break
if exp == exps[i]: # 현재 우선순위의 연산자를 만난 경우
sub_result = str(eval(numbers[i] + exp + numbers[i + 1])) # i, i+1번째 숫자로 계산
numbers[i + 1] = sub_result # numbers[i+1]에 계산 결과 저장
if before_exp_used: # 이전에 계산을 한 경우(현재 우선순위의 연산자가 연속으로 나온 경우)
new_nums_tmp[-1] = sub_result # 마지막에 저장된 숫자를 갱신함
else:
new_nums_tmp.append(sub_result) # 이전에 계산을 하지 않은 경우 새로운 숫자 배열에 추가
before_exp_used = True
else:
if not before_exp_used: # 이전에 계산을 하지 않은 경우
new_nums_tmp.append(num) # 새로운 숫자배열에 숫자만 추가
before_exp_used = False
numbers = new_nums_tmp.copy() # new_nums로 배열 갱신
exps = [e for e in exps if e != exp] # 이전 연산자를 제외한 연산자만 남도록 갱신
return abs(int(numbers[0])) # 절댓값 반환
def solution(expression):
ret = 0
numbers, exps = get_numbers_and_exps(expression)
# 순열을 이용하여 모든 경우 탐색
for exp_seq in permutations(list(set(exps))):
# exp_seq에서 우선순위 별로 하나씩 문자를 가져옴
ret = max(ret, calc(numbers.copy(), exps.copy(), exp_seq))
return ret
|
cs |
감사합니다.
'About > Algorithm' 카테고리의 다른 글
| [Programmers] 양과 늑대 (Python 풀이) - 2022 KAKAO BLIND RECRUITMENT (0) | 2022.01.28 |
|---|---|
| [Programmers] 신고 결과 받기 (Python 풀이) - 2022 KAKAO BLIND RECRUITMENT (2) | 2022.01.24 |
| [백준 8972] 미친 아두이노(Python 풀이) (0) | 2022.01.16 |
| [백준 20058] 마법사 상어와 파이어스톰(Python 풀이) (0) | 2022.01.10 |
| [백준 16985] Maaaaaaaaaze(Python 풀이) (0) | 2022.01.05 |
