문제 주소입니다.
programmers.co.kr/learn/courses/30/lessons/67257
코딩테스트 연습 - 수식 최대화
IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 �
programmers.co.kr
목차
1. 문제 설명
2. 문제 해석
3. 소스 코드
4. 결과
1. 문제 설명
|
IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 예를 들어, 참가자 중 네오가 아래와 같은 수식을 전달받았다고 가정합니다. "100-200*300-500+20" 일반적으로 수학 및 전산학에서 약속된 연산자 우선순위에 따르면 더하기와 빼기는 서로 동등하며 곱하기는 더하기, 빼기에 비해 우선순위가 높아 * > +,- 로 우선순위가 정의되어 있습니다. |
문제
| 참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해주세요. |
제한사항
|
예시
| expression | result |
| "100-200*300-500+20" | 60420 |
| "50*6-3*2" | 300 |
2. 문제풀이
| 코드가 조금길어서 보기가 힘들수도 있습니다. 하나하나 풀이 해보겠습니다. 순서는 아래와 같습니다. 1. 숫자와 수식 분리하기 2. 수식의 우선순위 정하기 3. 우선순위에 따른 결과 계산하기 1. 들어온 expression 변수에서 숫자와 수식을 분리해야 합니다. 저같은 경우는 수식과 변수를 저장하는 리스트를 만들었습니다. 그리고 문자열을 반복문으로 돌면서 수식이 나온다면 이전까지의 값을 숫자리스트에 넣고 현재 나온 수식을 수식 리스트에 넣었습니다. 수식을 넣으면 다음 잘라야 하는부분은 수식 뒷부분이므로 인덱스를 조절해줘야 합니다. 마지막으로 반복문이 끝나면 제일 마지막 숫자가 들어가있지 않으므로 마지막 숫자를 넣어줍니다. 2. 수식의 우선순위를 구해야 합니다. 이거는 3! = 6 이어서 직접 하나하나 리스트에 타이핑해서 넣으셔도 무관합니다. 저는 오랜만에 dfs 연습도 해볼겸 만들어 보았습니다. 수식과 방문여부를 체크하는 변수를 넣고 깊이우선탐색을 이용하여 경우의 수를 만듭니다. make_priority 함수를 보시면 감이오실것 같습니다. 3. 구해진 우선순위들을 이용하여 식 판단하기 위에서 구해진 값들은 priority리스트에 리스트 형식으로 들어가있습니다. 따라서 반복문을 이용하여 priority변수안에잇는 수식의 우선순의를 꺼냅니다. 이제 각각의 수식들을 반복문을 이용하여 꺼내서 내가 가지고있는 수식과 비교합니다.  위의 사진을 보시면 위에가 숫자리스트이고 아래가 수식 리스트입니다. 빠르게 공식을 유추해 본다면 0번째 수식이 계산되기 위해서는 0번째 숫자와 0+1번째 숫자가 필요합니다. 따라서 우선순위수식과 현재 수식이 일치한다면(현재 위치가 i라고 할때) i번째와 i+1번째 숫자를 이용하여 계산하여 i번째에 넣어주고 i+1번째의 숫자는 계산되었으므로 제거합니다. i번째 수식또한 마찬가지로 제거합니다. 그리고 수식의 길이가 줄어들었으므로 i를 감소시킵니다.(인덱스 초과 방지) 일치하던 일치하지 않던 i는 1번씩 증가시켜줍니다. 마지막으로 모든 수식의 계산이 끝나면 숫자를 가지고있는 변수의 0번째 인덱스에 결과가 저장되어 있습니다. 따라서 그 숫자에 절대값을 씌워서 answer와 비교하여 큰값을 answer에 넣어주면 끝입니다. |
3. 소스코드
|
# 기본수식
basic_formula = ['+', '-', '*']
# 간단한 계산을 해주는 함수
def calculator(a, b, p):
if p == '*':
return a * b
if p == '+':
return a + b
return a - b
def make_priority(index, priority, visited, temp):
# 마지막까지 왔다면 수식 추가
if index == 3:
priority.append(temp[:])
return
# 반복문을 돌면서 추가
for i in range(3):
if visited[i] == 0:
visited[i] = 1
temp.append(basic_formula[i])
make_priority(index+1, priority, visited, temp)
temp.pop()
visited[i] = 0
def solution(expression):
answer = 0
# 끊은 데이터를 저장하기 위한 변수
numbers = []
formula = []
# 어디를 끊었는지 기억하기 위한 변수
slice_index = 0
# 들어온 수식을 돌면서 슬라이싱
for i in range(len(expression)):
# 수식이 나온다면
if expression[i] in basic_formula:
# 숫자부분을 슬라이싱하여 numbers에 추가
numbers.append(int(expression[slice_index:i]))
# 수식부분을 formula변수에 추가
formula.append(expression[i])
# 다음시작은 i 뒤부터
slice_index = i+1
# 제일 마지막은 수식이 없으므로 따로 처리
numbers.append(int(expression[slice_index:]))
# 수식 우선순위 구하기
priority = []
# dfs형식을 이용하기 위해 방문여부 체크
visited = [0, 0, 0]
# 수식 우선순위 구하기
make_priority(0, priority, visited, [])
# 총 가지수가 6번이므로 3번 반복
for pri in priority:
temp_numbers = numbers[:]
temp_formula = formula[:]
# 수식은 3가지이므로 3번 반복
for p in pri:
i = 0
# i가 수식의 길이보다 짧을때까지 반복
while(i < len(temp_formula)):
# 우선순위 수식과 같다면
if temp_formula[i] == p:
# 번호를 추출
a = temp_numbers[i]
# 계산하면 사라지므로 pop
b = temp_numbers.pop(i+1)
# 계산한 값을 넣어주기
temp_numbers[i] = calculator(a, b, p)
# 사용한 수식 제거
temp_formula.pop(i)
# 수식을 제거했으므로 인덱스 감소
i -= 1
# 인덱스 증가
i+= 1
# 남아있는 값이 최대값보다 크다면 갱신
if abs(temp_numbers[0]) > answer:
answer = abs(temp_numbers[0])
return answer
if __name__ == "__main__":
expression_list = ["100-200*300-500+20", "50*6-3*2"]
result_list = [60420, 300]
length = len(result_list)
for i in range(length):
answer = solution(expression_list[i])
if answer == result_list[i]:
print('{}번 정답입니다.'.format(i+1))
else:
print('{}번 실패입니다.'.format(i+1))
print('{} != {}'.format(answer, result_list[i]))
|
4. 결과
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
| 키패드 누르기 Python(2020카카오 인턴십)[프로그래머스] (0) | 2020.09.05 |
|---|---|
| DATETIME에서 DATE로 형변환 MYSQL(프로그래머스) (0) | 2020.07.30 |
| 오랜 기간 보호한 동물(2) MYSQL(프로그래머스) (0) | 2020.07.29 |
| 중성화 여부 파악하기 MYSQL(프로그래머스) (0) | 2020.07.28 |
| 이름에 el이 들어가는 동물 찾기 MySQL(프로그래머스) (0) | 2020.07.27 |
댓글