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. 해시 유형

Key-value 쌍으로 데이터를 저장하여 데이터를 처리하는 유형이다.

주로 0~N까지 완전 탐색을 해야하는 경우의 문제여서, 정확도에 대한 테스트만을 수행하는 경향이 있다.

(일부 효율성 테스트가 있긴 하다.)

이런 경우에는 dict = {} 으로 접근하자.

관련 Python 내장 함수 => map, reduce, Counter 등

2. 스택 & 큐 유형

보통 직선 형태의 리스트를 사용하여 문제를 풀어가는 방식이다.

Python 같은 경우는 arr = [] 리스트를 통해 스택과 큐로서 사용하면 된다.

문제가 유명한 알고리즘(BFS, DFS, 길찾기 같은 등등)들을 요하는 것보다는

그냥 문제 자체에서 요구하는 대로 구현하면 된다.

관련 Python 내장 함수

arr.pop(0) : 앞에 빼는것(큐 구현시)

arr.pop() : 맨 뒤 값 빼는것(스택 구현시)

arr.append(맨 뒤 값 추가)

문제 설명

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

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

www.acmicpc.net/problem/1065

각 자리수가 등차수열을 이루는 값을 한수라고 부르고

그 한수를 찾는 문제이다.

이번 문제를 통해서 새롭게 알게 된 사실은,

for문과 if문을 통해서 문제를 하나씩 해결하려고 하지 말고

보다 깔끔하고 간결한 코드를 짜는 연습을 해야한다는 것이다.

실제로 if문으로 조건 걸어서 풀어주려고 하니까 Human error가 발생했는지 문제를 풀 수 없었다.

그래서 python map 함수를 통해 간결한 코드를 작성할 수 있었다.

N = int(input())

hansu = 0

for i in range(1,N+1):
    if i <= 99:
        hansu += 1
    else:
        num_arr = list(map(int,str(i)))
        if num_arr[0] - num_arr[1] == num_arr[1] - num_arr[2]:
            hansu += 1
            
print(hansu)