[네이버 코테 준비] 알고리즘 스터디 8일차

핵심

• 스택/큐 그리고 리스트 하나를 활용해서 문제를 풀 때, 
  • 리스트 내에 들어갈 조건을 만족하는지 체크한다.
  • 리스트에 채워지는 수는 항상 차례대로 채워질 필요는 없다. 스택에 값이 남아있을 때까지 진행해도 됨. 
• import functools
  • functools.cmp_to_key(func): 정의한 func 함수의 리턴값(1, 0, -1)에 따라 정렬될 수 있는 key값 제공 
  • sorted_list = sorted(list, key=functools.cmp_to_key(n, m))  
  • https://wikidocs.net/109303

029 순서대로 좌표를 정렬하려면? ― functools.cmp_to_key

 

• int 타입의 리스트를 문자열로 변환
  • list(map(str, list))
• 소수 찾기: 1과 자기 자신을 제외한 약수가 존재하지 않는 수 
  • 주어진 숫자의 제곱근까지 나누었을 때 나누어떨어지는 것이 있는지 확인.
  • https://coding-of-today.tistory.com/169

파이썬(Python) - 소수 찾기 알고리즘 구현하기(Prime Number)

• 에라스토테네스의 체 이용하기 
  • https://coding-lks.tistory.com/m/29

[프로그래머스] 소수 찾기 [연습문제] [python]

• 문자열을 리스트화하면 문자가 하나씩 분리되어 리스트가 된다. list('abc') -> ['a', 'b', 'c']
• 순열, 조합 리스트 생성: import itertools, itertools.permutation(list, n), itertools.combination(list, n)
  • https://velog.io/@dramatic/Python-permutation-combination-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9

[Python] permutation, combination 순열과 조합

 

1. 뒤에 있는 큰 수 찾기 

이 문제는 코드가 단순한데 발상은 단순해보이지 않는다..

stack에 numbers의 인덱스가 차례대로 쌓이고 항상 stack의 마지막 인덱스와 현재 인덱스의 값을 비교하여 

현재 인덱스가 큰 경우, 그 값을 answer에 저장함. 

def solution(numbers):
    stack = []
    answer = [-1] * len(numbers)

    for i in range(len(numbers)):
        while stack and numbers[stack[-1]] < numbers[i]:
            #가장 가까운 뒷 큰수일 때, 해당 자리의 숫자를 answer로 넣어줌. 
            #stack.pop() == stack[-1]
            answer[stack.pop()] = numbers[i]
        stack.append(i)
    
    return answer

 

2. 가장 큰 수 

이 문제도 코드가 단순한데 발상은 단순해보이지 않는다..

정렬을 위한 새로운 함수를 도입.

import functools

def comp(n, m):
    if int(n+m) < int(m+n):
        return 1
    elif int(n+m) == int(m+n):
        return 0
    else:
        return -1
    
def solution(numbers):
    numbers = list(map(str, numbers))
    sorted_list = sorted(numbers, key=functools.cmp_to_key(comp))
    answer = ''.join(sorted_list)
    # '0000' -> '0'으로 바꿔주기 위한 코드 
    return str(int(answer))

 

3. 소수찾기

이 문제가 level 1이라니; 

<주어진 숫자 n이 소수인지 확인하기>

• n의 제곱근까지 나누어떨어지는 수가 있는지 확인한다. 

def is_prime(n):
    if n <= 1: return False
    else:
    
        for i in range(2, int(n**(1/2))+1):
            if n % i == 0 :
                return False
        return True

 

 

<2~n까지의 숫자 중에서 소수가 총 몇 개 인지 반환하기>

에라토스테네스의 체를 이용할 시 원리는 다음과 같다.

• answer 에 set()자료형으로 2~n까지의 정수를 저장한다.
• 2 ~ n까지 for 문을 돌리며 answer에 i 가 있다면 n까지의 수 중 i의 배수를 모두 제거한다.
• answer에는 2~n까지의 소수만 남아있게 된다.
• len(answer)을 반환하면 해결!

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

 

<솔루션>

import itertools

def is_prime(n):
    if n <= 1: return False
    else:
    
        for i in range(2, int(n**(1/2))+1):
            if n % i == 0 :
                return False
        return True
    
def solution(numbers):
    # 문자열을 리스트화 
    numbers = list(numbers)
    stack = []
    answer = 0
    #조합 가능한 모든 경우의 수 구하기 
    for i in range(1, len(numbers)+1):
        for j in list(itertools.permutations(numbers, i)):
            num = int(''.join(j))
            if num not in stack: 
                stack.append(num)
                if is_prime(num):
                    answer += 1
                
    return answer