언제쯤 검색없이 코딩을 짤까요.

Q. 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동

예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다. - 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다. - 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다. 따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

제한 사항

• name은 알파벳 대문자로만 이루어져 있습니다.
• name의 길이는 1 이상 20 이하입니다.

입출력 예

namereturn

틀린 정답)

def solution(name):
    answer = 0
    for i in name:
        if i != 'A' and 'Z':  
            if ord(i) <= 78:    #알파벳이 N보다 밑에 있을 때
                answer += ord(i) -65
            else:
                answer += 91 - ord(i)  #알파벳이 N보다 위에 있을 때
        else:
            answer += 1
    return answer + len(name) -1

우선 문제에서 조이스틱을 움직일 때 위로(A->Z)방향 아니면 아래로(Z->A)방향으로 움직일지를 결정해야하는 데 N을 기준으로 N보다 밑에 있으면 조이스틱을 위로, N보다 위에 있으면 조이스틱을 아래로 움직이는게 최단값을 반환할 수 있다. 

A= 0, B= 1....N=13 그리고 거꾸로 계산을 하면 Z=1, Y=2, X=3...O=12, N=13이 된다.

알파벳을 아스키코드로 바꾼 후 차이만큼을 빼서 answer에 추가하고 다음 문자로 이동하는 만큼을 더해주면 되는데...

왜 ..... 'JAN'이 23이지..? 24아닌가...?

누가...로직이 왜 틀렸는지 알려줘요...

Q.

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

triangle                      result

def solution(triangle):
    for i in range(1, len(triangle)):   #위에서부터 2번째 줄
        for j in range(i+1):            #항
            if j == 0:                  #맨 왼쪽 값인 경우
                triangle[i][j] += triangle[i-1][j]
            elif j == i:                #맨 오른쪽 값인 경우
                triangle[i][j] += triangle[i-1][j-1]
            else:                       #왼쪽 위, 오른쪽 위에 애들 중 큰값을 더해주기
                triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
    
    return max(triangle[-1])            #가장 마지막 줄의 최댓값

점화식으로 생각하면 접근이 좀 편했다.

삼각형이 한줄 씩 밑으로 내려가면서 큰 수인 수를 더해주면 되는데 일반항으로 표현해보자.

이전까지 더한 최댓값이 M이라고 하고 내가 [i][j]번째 배열이라고 하면 나보다 왼쪽 위 [i-1][j-1] 이나 오른쪽 위 [i-1][j] 중에서 더 큰놈을 더해주면 계속 최대가 될 것이다. 

[i][j] += M +  [i-1][j-1]  or  M + [i-1][j]

이 값이 계속 밑으로 내려가며 누적을 시키자. 즉, 최댓값을 계속 배열에 덮어 씌우자! 

만약 내가 가장 왼쪽에 주어진 값이면 나랑 항이 같은 바로 위의 애를 더해주면 되고

(  [i][j] + [i-1][j]  )

내가 가장 오른쪽에 주어진 값이면 나보다 하나 항이 하나 더 앞에 있는 애들 더해주면 된다.

(  [i][j] + [i-1][j-1]   or   [i][j]  + [i-1][-1]   )

동적계획법 = 점화식!

근데 문제는 점화식을 세우는 것이 아니고 생각한 점화식을 코드로 옮기는거네 ㅎㅎㅎㅎㅎㅎ 

문제

APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다. 해시 함수는 무궁무진한 응용 분야를 갖는데, 대표적으로 자료의 저장과 탐색에 쓰인다.

이 문제에서는 여러분이 앞으로 유용하게 쓸 수 있는 해시 함수를 하나 가르쳐주고자 한다. 먼저, 편의상 입력으로 들어오는 문자열에는 영문 소문자(a, b, ..., z)로만 구성되어있다고 가정하자. 영어에는 총 26개의 알파벳이 존재하므로 a에는 1, b에는 2, c에는 3, ..., z에는 26으로 고유한 번호를 부여할 수 있다. 결과적으로 우리는 하나의 문자열을 수열로 변환할 수 있다. 예를 들어서 문자열 "abba"은 수열 1, 2, 2, 1로 나타낼 수 있다.

해시 값을 계산하기 위해서 우리는 문자열 혹은 수열을 하나의 정수로 치환하려고 한다. 간단하게는 수열의 값을 모두 더할 수도 있다. 해시 함수의 정의에서 유한한 범위의 출력을 가져야 한다고 했으니까 적당히 큰 수 M으로 나눠주자. 짜잔! 해시 함수가 완성되었다. 이를 수식으로 표현하면 아래와 같다.

해시 함수의 입력으로 들어올 수 있는 문자열의 종류는 무한하지만 출력 범위는 정해져있다. 다들 비둘기 집의 원리에 대해서는 한 번쯤 들어봤을 것이다. 그 원리에 의하면 서로 다른 문자열이더라도 동일한 해시 값을 가질 수 있다. 이를 해시 충돌이라고 하는데, 좋은 해시 함수는 최대한 충돌이 적게 일어나야 한다. 위에서 정의한 해시 함수는 알파벳의 순서만 바꿔도 충돌이 일어나기 때문에 나쁜 해시 함수이다. 그러니까 조금 더 개선해보자.

어떻게 하면 순서가 달라졌을때 출력값도 달라지게 할 수 있을까? 머리를 굴리면 수열의 각 항마다 고유한 계수를 부여하면 된다는 아이디어를 생각해볼 수 있다. 가장 대표적인 방법은 항의 번호에 해당하는 만큼 특정한 숫자를 거듭제곱해서 곱해준 다음 더하는 것이 있다. 이를 수식으로 표현하면 아래와 같다.

보통 r과 M은 서로소인 숫자로 정하는 것이 일반적이다. 우리가 직접 정하라고 하면 힘들테니까 r의 값은 26보다 큰 소수인 31로 하고 M의 값은 1234567891(놀랍게도 소수이다!!)로 하자.

이제 여러분이 할 일은 위 식을 통해 주어진 문자열의 해시 값을 계산하는 것이다. 그리고 이 함수는 간단해 보여도 자주 쓰이니까 기억해뒀다가 잘 써먹도록 하자.

처음 작성한 코드) 런타임 에러

M = 1234567891
num = int(input())
word = list(map(str, input()))
answer = 0

for i in range(num):
    answer += ord(word[i]-96) * (31**i)

print(answer%M)

우선 런타임 에러로 실패한 코드인데 알고리즘을 먼저 설명을 해보도록 한다.

결론은

이 수식을 코드화 하는 것!

생각보다 어렵지 않다.

1. 입력한 알파벳을 숫자화 시킨다

 => ord()함수를 이용하여 아스키코드로 변환. 하지만 소문자의 아스키코드는 97부터 시작하기 때문에 a를 1로 만들고 싶다면 96을 빼주어야 한다.

2. 숫자로 변환한 값에 r=31(문제에서 r=31이었음)의 거듭제곱을 곱해준다.

 => for문을 이용하여 거듭제곱을 늘려주었다.

3. 곱해준 갑들을 다 더해준다.

 => answer에 += 해주었다. 

4. 더한 값을 M=1234567891(문제에서 주어짐)로 나누어 출력

이상 코드 설명은 끝났다.

런타임에러가 나왔기 때문에 최대한 코드를 줄여보려 했는데....

num = int(input())
word = list(map(str, input()))
answer = 0

for i in range(num):
    answer += ord(word[i]-96) * (31**i)

print(answer%1234567891)

뭘...더 해야하노....

num = int(input())
word = input()
answer = 0

for i in range(num):
    answer += ord(word[i]-96) * (31**i)
print(answer%1234567891)

우선 사람들 코드를 힌트를 얻어 word를 list(map(str, input) 하지 않고서도 그냥 input하고 for문을 하면 알파벳들이 찢어져서 출력되는 것이 확인 되었다.

근데 이것도 런타임 에러인데?

대환장

+) 문제를 찾았다.

answer += ord(word[i]-96) * (31**i)

도대체 word[i]에서 96을 빼는 게 말이 되냐고ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

num = int(input())
word = input()
answer = 0

for i in range(num):
    answer += (ord(word[i])-96) * (31**i)
print(answer%1234567891)

다시 제정신 차리고 수정해서 100점을 받았다~^^

문제

자연수 N이 주어진다. N을 이진수로 바꿔서 출력하는 프로그램을 작성하시오.

n = int(input())
arr = []

def binary(n):
    if n == 1:
        arr.append(1)    # n=1 이면 이진수 변환값은 1
    elif n  == 2:
        arr.append(0)
        arr.append(1)    #n=2이면 이진수 변환값은 10인데 pop하기위해 01로 저장
    else:
        arr.append(n%2)  #n%2를 먼저 저장하고 
        binary(n//2)     #다시 함수 호출(재귀함수 사용)

binary(n)

for _ in range(len(arr)):
    print(arr.pop(), end='')   #pop해서 배열 순서 뒤집기

파이썬에는 bin함수가 있지만 재귀함수를 이용해서 푸는 것이 문제의 포인트였던 것 같아 알고리즘을 구현했다. n이 3 이상의 수라면 재귀함수를 이용하여 나머지들을 리스트에 저장하게끔 하였고 n이 2이하라면 직접 이진수값을 배열에 입력하는 식으로 구현했다.

조금 더 한줄 쓰기에 접근하려면 2이하의 수들도 if문 하나로 짤 수 있었겠지만 머리쓰기가 귀찮았다...ㅎ

그리고 배열들을 역순배치를 할까 하다가 역순->int->join 으로 하면 코드가 길어질 것 같아 pop을 이용할 수 있다는 방법을 적용해보았다!!!

재귀함수 아직도 어렵네

Q.네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.

1. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다.
2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
3. "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다.
4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.

입력 형식

입력으로 지도의 한 변 크기 n 과 2개의 정수 배열 arr1, arr2가 들어온다.

• 1 ≦ n ≦ 16
• arr1, arr2는 길이 n인 정수 배열로 주어진다.
• 정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2n - 1을 만족한다.

출력 형식

원래의 비밀지도를 해독하여 '#', 공백으로 구성된 문자열 배열로 출력하라.

입출력 예제

매개변수값

매개변수값

최종 코드)

def solution(n, arr1, arr2):
    bin_list = []

    for i in range(0, len(arr1)):
        bin_list.append(bin(arr1[i] | arr2[i])[2:].zfill(n))

    for i in range(n):
        bin_list[i] = bin_list[i].replace('1','#').replace('0',' ')
    
    return bin_list

def solution(n, arr1, arr2):
    bin_list = []

    for i in range(0, len(arr1)):
        bin_list.append(bin(arr1[i] | arr2[i])

우선 가장 제일 먼저 arr1 과 arr2를 bin 함수를 이용하여 2진수로 변환하고 비트연산 or을 한번에 진행하여 bin_list에 추가했다. 그런데 이대로 추가를 하면 bin 함수로 변환하면서 2진수 앞에 0b가 붙는다.

def solution(n, arr1, arr2):
    bin_list = []

    for i in range(0, len(arr1)):
        bin_list.append(bin(arr1[i] | arr2[i])[2:]

그래서 3번째(인덱스는 2)부터 슬라이싱하여 원하는 2진수 숫자만 뽑아 append 하였다.

그런데 이대로 return을 하면 문제가 길이가 파라미터 n가 같이 않은 변수들이 에러를 일으킨다.

def solution(n, arr1, arr2):
    bin_list = []

    for i in range(0, len(arr1)):
        bin_list.append(bin(arr1[i] | arr2[i])[2:].zfill(n))

문제에서는 변수의 길이와 n이 같아야하기 때문에 zill함수를 사용해서 앞에 0으로 채워주었다.

    for i in range(n):
        bin_list[i] = bin_list[i].replace('1','#').replace('0',' ')

그리고 replace함수를 사용해서 1 -> #, 0 -> ' ' 으로 바꿔주면 끝!!

카카오 입사 코딩테스트라고 해서 처음에 너무 쫄고 들어간 것같다. 물론 시험중에서 낮은 난이도에 해당하겠지만 그래도 두려움의 문턱을 넘을 수 있었다는 것에 크게 감동하고 있다! 계속 꾸준히 화이팅!!!

문제

상근이는 보통 사람들이 사는 것과는 조금 다른 삶을 사는 사람이다. 상근이는 이런 사람들의 시선이 부담스럽기 때문에, 자신만의 숫자를 개발하기로 했다. 바로 그 이름은 팩토리얼 진법이다. 팩토리얼 진법은 각 자리에 올 수 있는 숫자는 0부터 9까지로 10진법과 거의 비슷하다. 하지만, 읽는 법은 조금 다르다. 팩토리얼 진법에서는 i번 자리의 값을 ai×i!로 계산한다. 즉, 팩토리얼 진법에서 719는 10진법에서 53과 같다. 그 이유는 7×3! + 1×2! + 9×1! = 53이기 때문이다.

팩토리얼 진법으로 작성한 숫자가 주어졌을 때, 10진법으로 읽은 값을 구하는 프로그램을 작성하시오. 

import sys

#팩토리얼 함수
def factorial(n):
    if n>1:
        return n*factorial(n-1)
    else:
        return 1
        
        
#.팩토리얼 진법(상근이)
while True:
    num = sys.stdin.readline().strip()
    if int(num) == 0:
        break

    num = list(str(num))    #입력받은 숫자를 각 자리 수로 쪼개서 리스트에 담기
    num.reverse()      #for문을 돌리기 쉽게하려고 리스트를 역순으로 정렬
    l = len(num)
    cnt = [int(num[0])]  #for문의 index를 쉽게 하기 위해 일의 자리 수를 미리 담아둠
    for i in range(1, l):
        cnt.append(int(num[i])*factorial(i+1))  #각 자리숫자와 팩토리얼을 곱하고, int로 바꾸고, 어팬드
    print(sum(cnt))   #cnt 리스트 합구하기

처음에 input값 없이 프로그래머스처럼 상근이를 함수로 정의했더니 계속 틀렸다고 나왔다.

입력값들과 출력값까지 따져주어야 한다.

그래서 num = sys.stdin.readline().strip()를 사용했다. 

백준은 이 점이 참 힘들다..... 상근아 앞으로 사회부적응자처럼 이런 짓 하지 말아라..

문제

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

def factorial(n):
    if n>1:
        return n*factorial(n-1)
    else:
        return 1

팩토리얼의 정의는 n! = n * (n-1) * (n-2) * .... * 1 이다

n을 하나씩 낮춰가면서 곱하는 형태가 동일하기 때문에 재귀함수를 이용하여 n*factorial(n-1)을 사용했다.

문제는 0! =1. 이도 맞춰주기 위해 if문을 사용했다. 

Q. 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers     /        return

import copy

def permutation(lst, strum, numbers):
    for i in range(len(numbers)):
        cns = copy.deepcopy(numbers)
        add_strum = strum + cns.pop(i)
        lst.append(int(add_strum))
        permutation(lst, add_strum, cns)

def prime_list(n):
    sieve = [True] * (n+1)
    m = int(n ** 0.5)
    if n <= 1:
        return False
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n+1, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False
    #return [i for i in range(2, n) if sieve[i] == True]
    return sieve[-1]


def solution(numbers):
    num = []
    numbers = list(numbers)
    permutation(num, '', numbers)

    number_set = set(num)
    number_list = list(number_set)

    answer = 0
    for n in number_list:
        if prime_list(n):
            answer += 1
            print(n, answer)
    return answer

테스트 케이스 몇 개에서 시간초과로 실패가 떴다. 재귀함수가 디스크를 많이 잡아먹기도 하고 소수찾는 함수를 에라토스테네스 체를 사용해서 굴리는 시간이 많아가지고 그런 듯 하다. 그래서 제출은 squt이용해서 했고 개인적으로는 이 풀이가 더 마음에 들기때문에 이걸로 블로깅하겠다.

def prime_list(n):
    sieve = [True] * (n+1)
    m = int(n ** 0.5)
    if n <= 1:
        return False
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n+1, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False
    return sieve[-1]

에라토스테네스 체를 만들기 위해서 True로만 차있는 리스트를 하나 만들었다.

반복문을  n까지 다 돌릴 필요는 없어서 n의 루트까지만 반복을 하고 처음의 i는 그대로 True, 그 이후에는 i의 배수들을 False로 바꿔서 리스트에 저장하기로 한다.

def permutation(lst, strum, numbers):
    for i in range(len(numbers)):
        cns = copy.deepcopy(numbers)
        add_strum = strum + cns.pop(i)
        lst.append(int(add_strum))
        permutation(lst, add_strum, cns)

재귀함수...처음에 코드를 짰을 때는 deepcopy를 하지 않았더니 1,2,3을 연결할 때, 두 자리 수까지 밖에 되지 않아서 애를 먹었다. 결국 deepcopy를 써서 str 형태로 수들을 연결하고 int로 변환하여 다시 permutation에 넣게끔 연습했다.

def solution(numbers):
    num = []
    numbers = list(numbers)
    permutation(num, '', numbers)

    number_set = set(num)
    number_list = list(number_set)

    answer = 0
    for n in number_list:
        if prime_list(n):
            answer += 1
            print(n, answer)
    return answer

펄뮤테이션 함수를 쓰고 난 후에 담겨진 리스트들의 요소가 중복이 있을 수 있으니 set로 하여 중복을 제거하고 소수가 맞는지 확인하여 갯수를 리턴하였다.

다시 공부해야할 부분은 재귀함수(예제 많이 풀어보기)!!

Q. 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입출력 예

bridge_lengthweighttruck_weightsreturn

def solution(bridge_length, weight, truck_weights):
    num = len(truck_weights)
    que = []   #[트럭, 다리 위 위치] 로 된 2차원 리스트
    timer = 0
    finish = []   #다리를 건넌 트럭들
    while len(finish) < num:
        timer += 1   #루프를 돌때마다 시간을 +1
        sum = 0   #다리 위에 있는 트럭들의 무게 합
        if que:
            for i in range(len(que)):
                if que[i][0] == 0:
                    continue
                
                que[i][1] += 1   #트럭을 앞으로 한칸 이동
                if que[i][1] > bridge_length:   #트럭이 이동한 거리가 다리 길이보다 길면
                    finish.append(que[i][0])    #다리 통과
                    que[i] = [0,0]              #큐(다리)를 초기화
                else:
                    sum += que[i][0]            #다음 트럭의 무게를 우선 계산(올릴지/말지)
            if truck_weights and (sum + truck_weights[0]) <= weight:  #무게가 가능하다면
                que.append([truck_weights.pop(0),1])   #큐에 추가
        else:   #큐(다리)가 비어 있을 때 
            if truck_weights:   #대기하는 트럭이 있다면  
                que.append([truck_weights.pop(0),1])   #큐(다리)에 트럭을 올리고 앞으로 거리1 이동
    return timer

우선 내가 이해한 바로 코드에 설명을 부여했다.

이 문제를 처음 접했을 때 가장 난감했던 부분은 시간을 어떻게 재야하는 것인가였는데 스택처럼 시간을 재는 변수를 추가하면 되었다. 그리고 스택/큐는 while문을 많이 활용하는 듯 하다. 그래서 while을 돌 때마다 타임을 늘리면 시간 계산이 가능하다.

그리고 2차원 리스트 [트럭, 위치]를 한꺼번에 생각하는 것이 코드를 간략하게 쓸 수 있는 좋은 아이디어같다.

다른 문제들보다 가장 직관적으로 이해할 수 있는 풀이라고 생각해서 이 코드를 외우는 것으로 공부했다.

Q. 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

progresses     /        speeds               /         return

def solution(progresses, speeds):
    n = len(progresses) 
    day = [0]*n
    for i in range(n):
        day[i] = (100 - progresses[i]) // speeds[i]
        if (100 - progresses[i]) % speeds[i] !=0:
            day[i] += 1 
       
    stack = []
    answer = []
    stack.append(day.pop(0))
    while day:
        current = day.pop(0)
        if stack[0] >= current:
            stack.append(current)
        else:
            answer.append(len(stack))
            stack = [current]

        if not day:
            answer.append(len(stack))
            
    return answer

한 progress가 완성될 때 까지 걸리는 시간을 (100 - progress) // speeds로 계산하여 day 리스트에 추가한다. 만약 일수를 계산했을 때 나머지가 나온다면 하루를 더 연장시켜야하기 때문에 +1을 계산해준다.

예를 들어, 1번 테스트 케이스라고 가정해보자.

progresses = [93, 30, 55]

speeds = [1, 30, 5]

day = [7, 2, 9]

스택에 가장 day[0]을 추가한다.

그리고 그 다음 날 current = day[1]과 day[0]을 비교해서 day[1]이 작다면 배포를 기다려야 하기 때문에 stack에 추가.

아니라면 둘이 같이 배포할 수 있기 때문에 len(stack)를 정답에 넣어주고, 스택에 다음날과 비교해야할 current = day[1] 값을 넣어준다.

만약 day가 비어있다면 바로 스택의 길이만 출력!

스택/큐 문제는 아직도 익숙하지 않아 다른 사람의 풀이를 참고해서(거의 배꼈다) 공부했다. 이제 약간 어떤식으로 스택을 사용해야할지 알듯말듯... 우선 스택에 들어가있는 요소들과 비교할 변수가 추가로 더 필요하다는 것!

리스트에 append, remove 하는 것도 결국 스택인데 저건 쉽고 스택은 어려운게 참..,,