[Algorithm] 준비운동 PART 2. 약점 체크

준비운동 PART2. 약점 체크

문제풀이를 쭉쭉하기 전, 기본 알고리즘을 잘 습득했는지 점검할 수 있는 문제를 소개합니다. 뼈대 문제는 시간을 두고 반복 구현하여 손에 익혀서 응용문제가 나왔을 때 유연하게 대처할 수 있는 생각을 길러야 합니다.

 

• 재귀 탐색의 기본: 연산자 끼워넣기 (🥈실버 1티어)
• 스택의 응용: 괄호의 값 (🥈실버 2티어)
• 시뮬레이션 기본: 빗물 (🥇 골드 5티어)
• 완전탐색의 유연한 생각: 가르침 (🥇 골드 5티어)
• 그리디의 기본: 멀티탭 스케줄링 (🥇 골드 2티어)
• 투 포인터의 기본: 부분합 (🥇골드 4티어)
• 벨만포드 뼈대문제: 최소비용 구하기 (🥇 골드 5티어)
• Prime, Kruskal 뼈대문제: 최소 스패닝 트리 (🥇 골드 4티어)
• KMP 뼈대문제: 부분 문자열 (🥇 골드 4티어)
• 위상정렬: 줄 세우기 (🥇 골드 2티어)

출처: https://covenant.tistory.com/224

 

14888번: 연산자 끼워넣기 (실버 1티어)

14888번: 연산자 끼워넣기

n = int(input())
operands = list(map(int, input().split()))
operator = list(map(int, input().split()))

operators = (operator[0] * ['+']) + (operator[1] * ['-']) + (operator[2] * ['*']) + (operator[3] * ['//'])

# 순열 만들기
from itertools import permutations
operatorList = list(set(permutations(operators, len(operators)))) # set 안하면 시간 초과

resultList = []
# 계산하기
for operator in operatorList:  # [+, +, -, //, *]
    temp = operands[0]
    for i in range(n - 1):
        if operator[i] == '+':
            temp = temp + operands[i + 1]
        elif operator[i] == '-':
            temp = temp - operands[i + 1]
        elif operator[i] == '*':
            temp = temp * operands[i + 1]
        elif operator[i] == '//':
            if temp < 0:
                temp = -(-(temp) // operands[i + 1])
            else:
                temp = temp // operands[i + 1]
    resultList.append(temp)

print(max(resultList))
print(min(resultList))