내일은 알고리즘

https://school.programmers.co.kr/learn/courses/30/lessons/12906

스택/큐의 연습 문제인데 왜 스택/큐 인지 모르겠습니다.

쉽다는게 아니라 스택이랑 큐를 어디에 써서 구현할지 감이 안잡혀요... 

일단 입력을 n번 순회하면서 마지막에 넣은 값을 기억해주고, 같다면 패스 다르면 값을 넣어주고 갱신 하는 식으로 구현했습니다.

def solution(arr):
    answer = []
    before = -1
    
    for i in range(len(arr)):
        if arr[i] != before:
            before = arr[i]
            answer.append(before)
    
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/86491#qna

명함의 가로, 세로 크기의 최댓값을 포함하도록 지갑의 크기를 정해야 하는데, 명함을 돌릴 수 있으므로 명함의 긴 방향을 일치시키도록 돌리는 아이디어로 풀이할 수 있습니다.

극단적인 예를 들어, 1x10 10x1 두개의 명함을 이 상태대로 담으려면 10x10 사이즈의 지갑이 필요하지만, 하나의 명함을 돌리면 1x10 크기의 지갑에 담을 수 있습니다.

이런 상태를 만들기 위해서 w와 h값 중 한 방향을 정해 긴 쪽이 모두 일치하도록 돌려주고 최댓값을 찾으면 됩니다.

def solution(sizes):
    width = 0
    height = 0
    
    for size in sizes:
        w = size[0]
        h = size[1]
        
        if w < h:
            temp = h
            h = w
            w = temp
        
        if w > width:
            width = w
        if h > height:
            height = h   
    
    return width * height

https://school.programmers.co.kr/learn/courses/30/lessons/12901

2016년이 윤년이란 정보에 주의해서 입력의 일수에 월 별 지난 일 수를 저장해 줍니다.

예를 들어, 1월은 6일은 지난 월이 없어 그대로 6일 이지만 2월 6일은 1월이 지났기 때문에 31을 더해 37일이 됩니다.

또, 문제의 정보에서 생각해 보면 1월 1일(=1일)이 금요일이란 정보를 얻을 수 있습니다. 일주일은 7 단위로 반복되기 때문에, Index 1이 금요일인 길이 7의 배열을 만들어줍니다.

이제 입력된 날짜를 일수로 변환하고 7로 나눈 나머지의 Index 속 값을 취하면 쉽게 요일을 구할 수 있습니다.

def solution(a, b):
    month = [0,0,31,60,91,121,152,182,213,244,274,305,335]
    day = ['THU','FRI','SAT','SUN','MON','TUE','WED']

    daynum = month[a] + b
    answer = day[daynum % 7]
    return answer

solution(5,24)

https://school.programmers.co.kr/learn/courses/30/lessons/68644

입력값의 갯수와 범위가 100으로 작기 때문에 N*N으로 풀이할 수 있는 문제입니다.

입력되는 수의 크기가 100이기 때문에 두 수를 더해서 만들 수 있는 최대크기도 200입니다.

간단하게 200짜리 boolean 배열을 만들고 모든 경우에 대해 두 수의 합을 체크해준 뒤 boolean 배열을 순회하면서 True인 값들을 정답 배열에 넣어주면 자연스럽게 오름차순으로 정렬이 됩니다.

def solution(numbers):
    answer = []
    make = [False for i in range(201)]
    
    for i in range(len(numbers)):
        for j in range(i+1, len(numbers)):
            make[numbers[i] + numbers[j]] = True
    
    for i in range(len(make)):
        if make[i]:
            answer.append(i)
    
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/12982

정렬을 통해 그리디하게 풀이하면 바로 풀리는 문제입니다.

가장 작은 요구값들부터 예산에서 빼주면 됩니다.

def solution(d, budget):
    answer = 0
    d.sort()
    
    for req in d:
        if budget - req >= 0:
            answer += 1
            budget -= req
        else:
            break
    
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/68935

3진법으로 변환하는 방법만 알면 간단하게 구현 가능한 문제입니다.

나머지를 List에 저장해 reverse로 뒤집어줘도 되지만 저는 앞뒤로 출납이 가능한 deque자료구조를 활용해 구현했습니다.

from collections import deque

def solution(n):
    answer = 0
    deq = deque()
    
    while n > 0:
        remain = n % 3
        n = n // 3
        
        deq.append(remain)
    
    while len(deq) > 0:
        answer *= 3
        answer += deq.popleft()
    
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/77486

기본적인 DFS로 구현이 가능한 문제입니다.

입력에 따라 판매원들의 이름을 Dictionary에 저장해서 Index화 해줍니다. 

이후 판매원들의 referral을 입력받아 자신을 초대한 사원을 가리키게 해주면 위로만 타고 올라가지는 그래프 형태의 구조가 됩니다.

이제 매출이 발생한 입력마다 위로 타고 올라가며 상납금(?)을 더해주면 됩니다.

11~13번에서 런타임 에러가 발생한다면 해당 테스트케이스의 사원들의 초대 형태가 일렬로 길게 이어진 모양이라 타고 올라가다가 스택 오버플로우가 발생한 것입니다.

종료조건이 제대로 잡히지 않았을때 자주 발생하는 에러인데, 생각해 보면 판매에서 얻어지는 이익의 최댓값은 10000입니다. (칫솔 하나의 이익이 100원, 판매수의 최대가 100)

상납금은 10%씩을 납부하는데, 가장 큰 이익이 발생해도 몇 단계만 올라가면 상납금은 0원이 됩니다.

10000 (매출 발생) -> 1000원 상납 -> 100원 상납 -> 10원 상납 -> 1원 상납 -> 0원 상납 (판매자의 5단계 위는 돈을 얻을 수 없다!)

따라서 상납금이 0원이 되는 경우 다음 호출을 하지 않도록 탈출 조건을 잡아주면 됩니다.

if lead == -1 or tax == 0: (돈을 보낼 초대자가 존재하지 않거나, 보낼 돈이 0원일시 더 이상 호출하지 않음)

def solution(enroll, referral, seller, amount):
    result = [0 for i in range(len(enroll))]
    follow = [-1 for i in range(len(enroll))]
    name_dict = {}

    index = 0
    for name in enroll:
        name_dict[name] = index
        index += 1

    for i in range(len(referral)):
        if referral[i] != '-':
            target = name_dict[referral[i]]
            follow[i] = target

    for i in range(len(seller)):
        start = name_dict[seller[i]]
        money = amount[i] * 100
        send_money(follow, result, money, start)

    return result


def send_money(follow, result, money, me):
    lead = follow[me]
    tax = int(money / 10)
    result[me] += money - tax

    if lead == -1 or tax == 0:
        return
    else:
        send_money(follow, result, tax, lead)

https://school.programmers.co.kr/learn/courses/30/lessons/42889

람다식을 활용한 정렬을 사용하면 쉽게 풀리는 문제입니다.

우선 문제의 조건을 만족하도록 실패율을 구해줍니다. n번째 스테이지에 멈춰있는 인원이 Xn명이라면, n+1번째 스테이지에 도달한 인원은 n번째 스테이지에 도달한 인원 - nX명 이 됩니다.

즉, 첫 스테이지에는 모두가 도달했으므로 실패율이 (첫 스테이지에 멈춘 인원 / 전체 인원)이라면 두번째 스테이지는 (두번째 스테이지에 멈춘 인원 / (전체인원 - 첫 스테이지에 멈춘 인원)) 이 됩니다.

실패율을 계산해 주고, 만약 도달인원이 없다면 그냥 0으로 처리해주고 (divide zero 런타임 에러를 막기 위함) 얻은 실패율을 스테이지의 순서와 함께 묶어 리스트에 저장한 뒤 실패율을 기준으로 내림차순 정렬, 두번째 요소는 스테이지를 기준으로 오름차순 정렬을 해주면 됩니다.

fail_rate.sort(key=lambda x:(-x[0], x[1]))

x[0]이 실패율로 내림차순 정렬을 위해 마이너스 부호를 붙여주고, x[1]은 스테이지 번호로 오름차순 정렬이 됩니다.

def solution(N, stages):
    answer = []
    
    fail_rate = [[0, i+1] for i in range(N)]
    stage_user = [0 for i in range(N+1)]
    total_user = len(stages)
    
    for stage in stages:
        stage_user[stage - 1] += 1
    
    for i in range(N):
        if total_user == 0:
            fail_rate[i][0] = 0
        else:
            fail_rate[i][0] = stage_user[i] / total_user
            total_user -= stage_user[i]
    
    fail_rate.sort(key=lambda x:(-x[0], x[1]))
    
    for i in fail_rate:
        answer.append(i[1])
    
    return answer

print(solution(	5, [2, 1, 2, 6, 2, 4, 3, 3]))