프로그래머스 - 소수 만들기, 괄호 회전하기, 소수 찾기, 수식 최대화

소수 만들기

• 사이트/난이도: 프로그래머스 / 1
• 코드

from itertools import combinations
import math

def solution(nums):
    answer = 0
    for combs in list(combinations(nums, 3)):
        if is_prime(sum(combs)):
            answer += 1
    
    return answer

def is_prime(num):
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

• 느낀점
  • nums에 길이가 50 이하기 때문에 조합을 이용해 가능한 모든 경우의 수를 이용해 풀었다.
  • 근데 항상 파이썬 라이브러리를 통해 순열, 조합을 사용해서 실제로 사용하려면 어떻게 해아되나 찾아봤고 좋은 사이트가 있어서 참고했다.
  • https://shoark7.github.io/programming/algorithm/Permutations-and-Combinations
  https://foameraserblue.tistory.com/188?category=481823

조합과 순열 알고리즘, 파이썬으로 구현하기

PS를 하며 느끼는 DFS와 BFS 선택의 기준

 

괄호 회전하기 - X

• 사이트/난이도: 프로그래머스 / 2
• 코드

def solution(s):
    answer = 0
    for i in range(len(s)):
        if is_possible(rotate(s, i)):
            answer += 1
    return answer

def rotate(s, i):
    return s[i:] + s[:i]

def is_possible(s):
    stack = []
    for i in s:
        if i in ["[", "{", "("]:
            stack.append(i)
        else:
            if not stack:
                return False
            top = stack.pop()
            if i == "]" and top != "[":
                return False
            elif i == "}" and top != "{":
                return False
            elif i == ")" and top != "(":
                return False
    if stack:
        return False
    return True

• 느낀점
  • stack 을 이용해 문자열을 확인하는 문제
  • 처음에 [, {, ( 괄호들의 숫자를 세서 비교하는 식으로 코드를 작성했는데 14번 테케에서 계속 실패함.
  • 다른 사람 풀이를 보니 stack 을 이용해 간단하게 풀어서 이를 이용함
  • 그러면서 한가지 deque.rotate(-1) 를 이용하면 앞으로 회전시킨다는 사실을 발견함.

소수 찾기

• 사이트/난이도: 프로그래머스 / 1
• 코드

import math

def solution(n):
    answer = 0
    for i in range(2, n+1):
        if is_prime(i):
            answer += 1
    return answer

def is_prime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

# 에라토스테네스의 채
def solution(n):
    num=set(range(2,n+1))

    for i in range(2,n+1):
        if i in num:
            num-=set(range(2*i,n+1,i))
    return len(num)

• 느낀점
  • 소수 찾는 문제인데 n의 범위가 백만까지라서 나는 제곱근을 이용해서 최적화했다.
  • 다른사람 풀이 보니 **에라토스테네스의 체 알고리즘을 이용해 풀었다
  • 에라토스테네스의 채: 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법. 1. 1은 제거 2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다. 3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다. 4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다. 5. (반복)
  • 점프 투 파이썬

수식 최대화 - X

• 사이트/난이도: 프로그래머스 / 2
• 코드

from collections import deque
from itertools import permutations

def operate(n1, n2, op):
    if op == "+":
        return str(int(n1) + int(n2))
    elif op == "-":
        return str(int(n1) - int(n2))
    elif op == "*":
        return str(int(n1) * int(n2))

def calculate(exp, op):
    arr = deque([])
    temp = ""
    for i in exp:
        if i.isnumeric():
            temp += i
        else:
            arr.append(temp)
            temp = ""
            arr.append(i)
    if temp:
        arr.append(temp)
    for o in op:
        stack = deque([])
        while arr:
            now = arr.popleft()
            if now == o:
                stack.append(operate(stack.pop(), arr.popleft(), now))
            else:
                stack.append(now)
        arr = stack
    return abs(int(arr[0]))

def solution(expression):
    answer = 0
    operators = ["+", "-", "*"]
    for op in list(permutations(operators, 3)):
        answer = max(answer, calculate(expression, op))
    return answer

• 느낀점
  • 어떻게 풀지 감이 안잡힌 문제….
  • 다른 사람 풀이를 참고하니 일단 ["+", "-", "*"] 에서 가능한 순서를 순열로 가져와서 계산해서 최대화 했다. 그리고 계산하는 방법인 감이 안왔는데,
    1. 일단 문자열을 배열로 바꾼 후, 하나씩 확인하면서 해당 연산자가 아니면 stack에다가 계속 담는다.
    2. 해당 연산자가 나오면 Stack에서 피연산자 하나를 꺼내고 배열에서 피연산자 하나를 꺼내서 연산한 후, stack에 담는다.
    3. 배열을 stack으로 동기화 한다.
  • 그리고 eval 을 이용하면 문자열 안에 식인 eval("1+2") 이런식으로 하면 3을 반환해준다는 것을 알았다.