Henry's Algorithm

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 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

출처

※ 공지 - 2020년 4월 06일 테스트케이스가 추가되었습니다.

트럭이 지나가는 시간이나, 자동차가 지나가는 시간을 계산해주어야 할때는

0을 잘 활용하자.

[0,0,0,3,0,0] <= 이렇게 트럭이 다리를 지난가는 것처럼 0 값으로 시간의 흐름을 나타내주면 문제에 접근하기 쉽다.

직관적인 방법으로 해결해주는 것이다.

정답:

def solution(bridge_length, weight, truck_weights):
    time = 0
    q = [0]*bridge_length
    
    while q:
        time += 1
        q.pop(0)
        if truck_weights:
            if sum(q) + truck_weights[0] <= weight:
                q.append(truck_weights.pop(0))
            else:
                q.append(0)
            
    
    return time

알게된 것

처음에는 from collections import deque 를 통해 deque를 사용하려고 했는데,

arr = []

a.pop(0) <- 이 방법으로 0번째 값을 뺄 수 있는 것을 몰랐다.

또한 del a[0] 은 오버헤드는 커서 timeout이 발생하는 것도 알게 되었다.

문제 설명

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

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

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

제한 사항

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

입출력 예

progressesspeedsreturn

입출력 예 설명

입출력 예 #1
첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

입출력 예 #2
모든 기능이 하루에 1%씩 작업이 가능하므로, 작업이 끝나기까지 남은 일수는 각각 5일, 10일, 1일, 1일, 20일, 1일입니다. 어떤 기능이 먼저 완성되었더라도 앞에 있는 모든 기능이 완성되지 않으면 배포가 불가능합니다.

따라서 5일째에 1개의 기능, 10일째에 3개의 기능, 20일째에 2개의 기능이 배포됩니다.

※ 공지 - 2020년 7월 14일 테스트케이스가 추가되었습니다.

단일 for문을 두번 돌려서 문제를 풀었다.

처음으로 zip 이라는 내장함수를 사용할 수 있어서 좋았다.

꾸준히 공부하다보면 점점 실력을 향상시킬 수 있을 것이다. 화이팅!!

정답

def solution(progresses, speeds):
    import math
    
    answer = []
    remain = []
    
    for i in zip(progresses, speeds):
        remain.append(math.ceil((100-i[0])/i[1]))
    
    cur_max = remain[0]
    cur_cnt = 1
    
    for i in range(1,len(remain)):
        if cur_max < remain[i]:
            answer.append(cur_cnt)
            cur_max = remain[i]
            cur_cnt = 1
        else:
            cur_cnt += 1
    
    answer.append(cur_cnt)
    
    return answer

근데, 다른 사람의 코드를 보니까

아예 for 문 한번으로 끝낼 수도 있었다.

앞으로 최대한 간결하게 풀어보자

def solution(progresses, speeds):
    Q=[]
    for p, s in zip(progresses, speeds):
        if len(Q)==0 or Q[-1][0]<-((p-100)//s):
            Q.append([-((p-100)//s),1])
        else:
            Q[-1][1]+=1
    return [q[1] for q in Q]

이거는 내가 따라서 작성한 코드다.

조금 더 간결하게 만들 수 있을 것 같다.

def solution(progresses, speeds):
    import math
    
    answer = []
    cur_cnt = 1
    
    for i in zip(progresses, speeds):
        if len(answer) == 0 or answer[-1][0] < math.ceil((100-i[0])/i[1]):
            answer.append([math.ceil((100-i[0])/i[1]),1])
        else:
            answer[-1][1] += 1
    
    return [i[1] for i in answer]
   

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

pricesreturn

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

※ 공지 - 2019년 2월 28일 지문이 리뉴얼되었습니다.

이 문제를 푸는데 핵심 공략법은 Stack이다.

그러나 Stack + 차원이 높은 배열이 필요하다.

언제 들어오고 언제 나갔는지 확인하기 위해 [(값, 들어온 idx, 나간 idx)]의 형태로 문제를 풀었다.

정답

def solution(prices):
    
    stack = [(prices[0],0,-1)]
    
    answer = [0]*len(prices)
    
    for i in range(1,len(prices)):
        if stack[-1][0] <= prices[i]:
            stack.append((prices[i],i,-1))
        else:
            for j in range(len(stack)-1,-1,-1):
                if stack[j][0] > prices[i]:
                    answer[stack[j][1]] = i - stack[j][1]
                    stack.pop()
                else:
                    break
        
            stack.append((prices[i],i,-1))
                    
            
    answer = [len(prices)-(i+1) if answer[i] == 0 else answer[i] for i in range(len(answer))]
        
    
    return answer

Python의 list comprehension 덕분에 코드가 조금씩 간결해지고 있지만,

아직 부족하다 더 연습해서 진짜 간결하고 정확하게 풀고 싶다.

아래는 다른사람 코드인데,

이중 for문 돌려서 풀어도 문제가 풀리는 것 같다.

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

그러나 성능은 N**2이 나와서 stack보다는 좋지 않을 것으로 예상된다.

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

입출력 예

genresplaysreturn

입출력 예 설명

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

※ 공지 - 2019년 2월 28일 테스트케이스가 추가되었습니다.

이 문제를 푸는 스킬은

아래 코드에 있다.

answer = []
arr = {}
    
for i in range(len(genres)):
    if genres[i] in arr:
        arr[genres[i]][0] += plays[i]
        arr[genres[i]][1].append((i,plays[i]))
    else:
        arr[genres[i]] = [plays[i],[(i,plays[i])]]

같은 장르의 값이면, 같은 dict에 넣어주는 코드이다.

정답:

def solution(genres, plays):
    answer = []
    arr = {}
    
    for i in range(len(genres)):
        if genres[i] in arr:
            arr[genres[i]][0] += plays[i]
            arr[genres[i]][1].append((i,plays[i]))
        else:
            arr[genres[i]] = [plays[i],[(i,plays[i])]]
            
    arr_ = list(arr.values())
    arr_ = sorted(arr_, reverse=True)
    
    for i in range(len(arr_)):
        tmp = sorted(arr_[i][1], key=lambda x:x[1], reverse=True)
        tmp = [i for i,v in tmp]
        if len(tmp) < 2:
            answer += tmp
        else:
            answer += tmp[:2]
    
    return answer

Timeout에 대한 테스트는 없는 것을 보니,

정확하게 접근해서 짜는 연습을 하면 좋을 것 같다.

조금 아쉬운 부분은

중간에 list()나 sorted()같은 내장함수를 사용해서 코드가 지져분하다는 것이다.

또한 tmp 변수를 사용해서 코드가 정돈되지 않은 느낌이 든다.

아래는 다른 사람의 코드이다.

이렇게 응축할 수 있다니, 나는 아직도 멀은 것 같다. 더 열심히 해야겠다

def solution(genres, plays):
    answer = []
    d = {e:[] for e in set(genres)}
    
    for e in zip(genres, plays, range(len(plays))):
        d[e[0]].append([e[1] , e[2]])
        
    genreSort =sorted(list(d.keys()), key= lambda x: sum( map(lambda y: y[0],d[x])), reverse = True)
    
    for g in genreSort:
        temp = [e[1] for e in sorted(d[g],key= lambda x: (x[0], -x[1]), reverse = True)]
        answer += temp[:min(len(temp),2)]
        
    return answer

문제 설명

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.

예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.

종류이름

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
• 스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예

clothesreturn

입출력 예 설명

예제 #1
headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.

1. yellow_hat 2. blue_sunglasses 3. green_turban 4. yellow_hat + blue_sunglasses 5. green_turban + blue_sunglasses

예제 #2
face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

1. crow_mask 2. blue_sunglasses 3. smoky_makeup

옷가지의 분류를 나누어주고,

각 옷 종류에 따른 개수 +1 을 곱해준다. (+1인 이유는 안입는 경우도 있기 때문이다)

그리고 마지막에 -1을 해준다.(아무것도 안 입는 경우는 안되니까)

정답 코드:

def solution(clothes):
    clothes_ = {}
    
    for i in range(len(clothes)):
        try:
            clothes_[clothes[i][1]] += 1
        except:
            clothes_[clothes[i][1]] = 1
    
    clothes_ = list(clothes_.items())
    
    cnt = 1
    
    for i in clothes_:
        cnt *= (i[1]+1)
        
    return cnt -1

함수를 사용해서 풀어도 된다.

def solution(clothes):
    from collections import Counter
    from functools import reduce
    cnt = Counter([kind for name, kind in clothes])
    answer = reduce(lambda x, y: x*(y+1), cnt.values(), 1) - 1
        
    return answer

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.

입출력 예제

phone_bookreturn

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

알림

2019년 5월 13일, 테스트 케이스가 변경되었습니다. 이로 인해 이전에 통과하던 코드가 더 이상 통과하지 않을 수 있습니다.

해시 접근으로 푸는 문제이다.

이런 경우는 보통 완전탐색을 하지 않으면 풀 수 없기 때문에 

이중 for문으로 접근해주어도 Timeout 에러가 발생하지 않는다

정답 코드:

def solution(phone_book):
    answer = True
    
    for i in range(len(phone_book)-1):
        for j in range(i+1,len(phone_book)):
            if len(phone_book[i]) <= len(phone_book[j]):
                if phone_book[j][:len(phone_book[i])] == phone_book[i]:
                    return False
            else:
                if phone_book[i][:len(phone_book[j])] == phone_book[j]:
                    return False
    return True

문제 설명

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

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

제한사항

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

입출력 예

triangleresult

출처

프로그래머스의 LEVEL 3에 있는 정수 삼각형 문제이다.

문제 설명을 보면 Dynamic Programming 개념을 통해서 풀라고 나와있다.

나는 동적 프로그래밍이 처음에는 재귀 호출을 통해서 푸는 방식이라고 생각했는데,

이 문제를 보면서 다시 알게 된 것은

재귀호출도 그렇고 이 정수 삼각형 문제도 그렇고

"처음부터 하나씩 쌓아나가는 개념" 이라는 것을 깨달았다.

내가 푼 방식은 for문을 2번 돌리면서 진행하는데,

생각한거와는 다르게 채점 시 Timeout 에러가 발생하지 않았고,

문제에 따라서는 모든 정수에 한번씩은 다 접근해야하는 경우에 이렇게 Dynamic Programming을 통해 풀 수 있는 거 같다.

아래는 내가 푼 코드이다.

def solution(triangle):

    for i in range(1,len(triangle)):
        for j in range(len(triangle[i])):
            if j == 0:
                triangle[i][j] += triangle[i-1][0]
            elif j == len(triangle[i])-1:
                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])

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

ncomputersreturn

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

프로그래머스의 LEVEL 3단계 문제이다.

풀이의 핵심은 DFS, BFS 함수를 정의하여 풀면 된다.

나는 DFS로 시작 컴퓨터 정하고, 깊이를 파고들어서 visit 리스트에 넣어주었다.

이후 다른 컴퓨터에 한번씩 접근했을 때

이전 컴퓨터를 통해 이미 visit 값에 포함되어 있다면 네트워크에 연결이 되어있는 컴퓨터라고 생각했다.

그래서 다른 컴퓨터에 접근할 때마다 visit가 늘어나게 되면 그 컴퓨터는 독립적인 네트워크라고 판단하여 문제를 풀었다.

풀이 코드

def solution(n, computers):
    
    # 네트워크 개수
    net_num = 0
    
    # 방문 컴퓨터 리스트
    visit = list()
    
    # 컴퓨터에 한번씩 접근하면서 깊이우선탐색 수행
    for i in range(len(computers)):
        net_num += dfs(computers,i,visit)
    
    return net_num


def dfs(computers, start_computer, visit):
    
    # 깊이 우선 탐색은 스택으로 구현한다.
    stack = list()
    
    # 신규 네트워크 여부
    is_connect = 0
    
    # 시작 컴퓨터
    stack.append(start_computer)
    
    while stack:
        node = stack.pop()
        if node not in visit:
            visit.append(node)
            stack.extend([i for i in range(len(computers[node])) if i != node and computers[node][i] != 0])
            is_connect = 1
            
    return is_connect