728x90
SMALL
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr

from itertools import permutations
def solution(expression):
answer = 0
operators = ['+', '-', '*']
nums, ops = [], []
num = ''
for char in expression:
if char.isdigit():
num += char
else:
nums.append(int(num))
num = ""
ops.append(char)
nums.append(int(num))
for op_order in permutations(operators):
temp_nums = nums[:]
temp_ops = ops[:]
for op in op_order:
idx = 0
while idx < len(temp_ops):
if temp_ops[idx] == op:
if op == '+':
temp_nums[idx] += temp_nums[idx+1]
elif op == '-':
temp_nums[idx] -= temp_nums[idx+1]
else:
temp_nums[idx] *= temp_nums[idx+1]
temp_nums.pop(idx+1)
temp_ops.pop(idx)
else:
idx += 1
answer = max(answer, abs(temp_nums[0]))
return answer
- 우선순위 조합을 활용하여 수식의 최댓값을 반환해주는 문제였습니다.
왜 이렇게 풀었을까?
- 처음에 접근할 때에는 stack을 이용하여 풀까 하다가 숫자와 연산자의 구분이 필요한 시점에서 stack이 그다지 효율적으로 동작하지 않게 되어, 먼저 수식에서 숫자와 연산자를 각각 리스트에 담아준 뒤 시작을 해보았습니다.
- 조합이 그리 많지 않아 일일이 조합을 명시한 뒤 풀어도 되었겠지만, 코드의 간결성을 위해 permutations를 사용하여 조합을 계산했습니다.
- temp_ops는 연산이 진행되면 그 길이가 동적으로 변하기 때문에 이를 처리하기 위해 while문의 조건을 idx < len(temp_ops)로 설정함으로써 그 길이에 맞추어 연산이 진행되게끔 했습니다.
- 시간 초과가 날까 싶어 계속 반신반의하며 코드를 작성하였는데 통과를 하게 되어 다행이고, 추후에 더 효율적인 방법을 탐구해볼 예정입니다.
728x90
LIST
'알고리즘 문제 풀이 > 프로그래머스 (Level 2)' 카테고리의 다른 글
| 📗 테이블 해시 함수 (1) | 2024.09.27 |
|---|---|
| 📗 줄 서는 방법 (2) | 2024.09.25 |
| 📗 미로 탈출 (0) | 2024.09.20 |
| 📗 무인도 여행 (3) | 2024.09.11 |
| 📗 호텔 대실 (0) | 2024.09.10 |