문제 풀이

주식가격

# 1. deque 활용
from collections import deque
def solution(prices):
    answer = []
    queue = deque(prices)
    while queue:
        price = queue.popleft()
        second = 0
        for q in queue:
            second += 1
            if price > q :
                break
        answer.append(second)
    return answer

# 2. stack 활용
def solution(prices):
    answer = [0] * len(prices)
    for i in range(len(prices)):
        for j in range(i+1, len(prices)):
            if prices[i] <= prices[j]:
                answer[i] += 1
            else:
                answer[i] += 1
                break
    return answer

< 풀이 과정 >

1. deque를 활용한 풀이 (FIFO)

• 주어진 prices 리스트를 바로 deque로 변환한 후 popleft로 price를 하나씩 꺼내 나머지 리스트 값과 비교하여 큰 값이 나오는 순간 종료하고 그 전까지 초 1씩 크게 하기

  deque를 활용한 문제 풀이는 구현이 크게 어렵지 않았다.

2. stack을 활용한 풀이 (LIFO)

• stack 관련 문제를 풀고 stack이 좀 어렵게 느껴졌다. 그동안 풀었던 스택 문제와 다른 느낌? 기존 2중 for문으로 복잡도가 높아지는 걸 막기 위해 스택을 쓴다고 생각했는데 물론 시간복잡도는 낮아지겠으나 이 문제를 풀 땐 그렇게 까지 효율적이라고는 생각이 들지 않았다. 풀이가 잘못 됐나.. 내가 구현한 문제는 스택이 아닌 일반 2중 for문을 이용한 느낌이 든다.

• answer와 stack을 0이 포함된 리스트로 생성
• 스택에는 인덱스만을 저장 (0번 인덱스는 입력하고 시작)
• for문을 1번 인덱스 ~ prices길이 만큼 돌며 stack의 끝값보다 작은 경우만 필터 걸고 for문으로 스택을 뒤부터 검사하여 현재 prices가 순서 바꾼 스택의 prices 보다 작은 경우 스택에서 제거.
• 음... 즉 순서를 바꾼 prices와 비교를 해서 prices가 낮아진다면 스택에서 제거하는 것을 의미한다. 설명을 잘 못하는,,,
• 좀 더 간략하게 설명하면 prices 순서대로 인덱스인 i와 이를 스택에 저장하고 뒤집어서 보는 j를 기준으로 prices가 낮아지면 스택에서 제거, 높아지면 스택에 추가하고 결과로서 prices 길이 - stack에 저장된 값(인덱스값) -1을 하여 결과 도출하기.

k진수에서 소수 개수 구하기

1.
def solution(n, k):
    answer = 0
    string = ''
    while n != 0:
        string = str(n % k) + string
        n = n // k
    array = string.split('0')
    for num in array:
        if num == '':
            continue
        for number in range(2, int(int(num)**0.5 + 1)):
            if int(num) % number == 0:
                break
        else:
            if num != '1':
                answer += 1
    return answer
    
    
2. def convert(n, k):
    result = ''
    while n > 0:
        n, mod = divmod(n, k)
        result += str(mod)
    return result[::-1]

def getprime(n):
    if n == 1:
        return False
    elif n == 2:
        return True
    m = int(n**0.5) + 1
    for i in range(2, m):
        if n%i == 0:
            return False
    return True

def solution(n, k):
    n = convert(n, k)
    li = str(n).split('0')
    li = list(filter(lambda x: x!= '', li))
    li = list(map(lambda x: getprime(int(x)), li))
    return li.count(True)

< 풀이 과정 > - 1번만 풀이진행!, 2번의 경우 소수구하기, k진법 전환 함수 쉽게 구현해놓음.

• 숫자 n과 k진법을 입력받고 문자열로 n >> k 진법으로 숫자 변환
• '0' 기준으로 split 진행하여 array 배열에 담기
• array 문자열 for문 돌려서 공백일 경우 건너뛰기
• 소수인 경우를 확인하기 위해 2 ~ int(num)**0.5 + 1로 num % number == 0이면 소수가 아니기에 break
• 1의 경우 소수가 아니므로 1이면 answer 값 더해주지 않기.

[3차] N진수 게임

def convert(n, val):  
    base_arr = '0123456789ABCDEF'
    quot, remain = divmod(n, val)
    if quot == 0:
        return base_arr[remain]
    else:
        return convert(quot, val) + base_arr[remain]

def solution(n, t, m, p):
    answer = ''
    check = ''
    for i in range(t*m):
        check += str(convert(i, n))
    while len(answer) < t:
        answer += check[p-1]
        p += m
        
    return answer

< 풀이 과정 >
문제를 보고 숫자를 입력 받아 n진법으로 처리하기 위해 이를 전환해주는 함수 생성

• n의 범위가 2 ~ 16이므로 미리 기본적인 10진법 배열 생성
• 몫과 나머지를 구하게 해주는 함수 divmod 이용하여 몫 나머지 구하고 몫이 0인 경우 나머지가 0 ~ 15이므로 base_arr 리스트에 인덱스로 값 리턴
• 몫이 0이 아닌 경우 재귀 진행
• 총 게임 참여자가 말해야 하는 숫자 개수는 튜브가 말해야 하는 수 * 게임 참가 인원이므로 for문으로 해당 범위 내 모든 숫자를 n진법으로 전환 후 튜브 차례인 p번째 마다 answer로 리턴

할인행사

원하는 제품을 나타낸 배열 want와 원하는 제품의 수량을 나타낸 number, 날짜 별로 할인되는 제품을 나타낸 배열discount가 주어지고 10일 간 해당 discount 배열 내의 제품, 수량이 일치하는 날짜 수를 출력하는 문제

from collections import defaultdict
def solution(want, number, discount):
    answer = 0
    hash = defaultdict(int)
    for i in range(len(want)):
        hash[want[i]] = number[i]
    for i in range(len(discount)-9):
        dc_list = discount[i:i+10]
        cnt = 0
        for w in want:
            if hash[w] == dc_list.count(w):
                cnt += 1
        if cnt == len(want):
            answer += 1
    return answer

< 풀이 과정 >
단순 구현문제.
우선 discount를 10일 단위로 끊어줄 dc_list를 만들어야겠다고 생각했다.
그 이후 want의 제품 수량과 dc_list내 수량이 일치해야 하므로 hash라는 defaultdict를 만들어 default:0을 가진 딕셔너리를 만들어주었다.
이후 10일간의 dc_list들의 속하는 제품 수량과 hash내 제품 수량이 일치하면 cnt + 1을 진행하고, want 품목과 cnt가 일치하면 기간 내 원하는 제품이 수량에 맞게 모두 할인 중인 것이므로 answer + 1을 해준다.

스킬트리

def solution(skill, skill_trees):
    answer = 0
    for user in skill_trees:
        check = ''
        for idx in user:
            if idx in skill:
                check += idx
        if skill[:len(check)] == check:
            answer += 1
    return answer

< 풀이 과정 >
구현은 쉬운 편! 존재하는 개별 유저의 skill_trees 순서가 skill과 일치하면 된다.

• check 문자열에 개별 유저의 skill_trees의 인덱스로 skill에 존재하면 순서대로 저장
• 입출력 예시 처럼 skill_trees 순서엔 D없이 CB만 있어도 옳은 스킬 순서대로 찍었다고 보는 것이기에 skill[:len(check)] 가 check와 일치하는 경우에만 리턴 + 1 처리