너무나도 늦은 회고록이지만 뒤늦게라도 Boostcamp STS 프로젝트를 회고하려 합니다. 

최종 성적

- Public 2위 : 0.9378

- Private 3위 : 0.9417 

프로젝트 시작 전

인생에서의 첫 캐글형식의 순위형 프로젝트였다.
리더보드형 프로젝트를 함에 앞서 의욕도 많이 앞섰고, 잘 하고 싶은 마음이 가득했었다. 

높은 순위를 프로젝트하면서 한번은 가지고 싶었고 추후 팀을 자유롭게 꾸릴때 높은 성적은 도움이 될 것이라고 생각했다.

프로젝트 진행

3주간 진행된 프로젝트에서 추석이라는 기간이 포함되어있었고 실질적으로는 약 2주 정도의 기간동안 프로젝트를 집중할 수 있었다.

이 글을 찾아서 들어오시는 분들은 부스트캠프 사람들로 예상이 되기에 프로젝트의 소개는 넘어가도록 하겠습니다.

위 그림은 프로젝트의 타임라인이다.
약 두달이 지나서야 쓰는 회고지만 지금 보면 다음과 같은 타임라인은 정말 잘못 되었다고 생각한다.

EDA와 앙상블을 동시에 진행하다니,,,

우리팀이 범했던 실수에 대해서 먼저 말하고자 한다. 

1.  EDA의 중요성 간과

Boostcamp에서 프로젝트를 마칠 때 마다 2팀 정도 발표를 자원하거나
지원자가 없다면 Private 높은 순위의 팀이 발표를 맡아서 하게 된다.

이번 프로젝트에서는 Public에서 3등 팀이 Private에서 1위를 하게 된 것을 보고 저팀의 노하우가 궁금했다.

1위의 비결은 바로 EDA였다. 우리팀의 패착은 모델의 성능에만 집중을 했었다.

그 어떤 팀보다 모델 탐색과 실험은 잘했다라고 생각하고 그것이 높은 순위를 얻게된 비결이라고 생각했다.

그렇지만 1등팀은 데이터셋의 모든 문장들을 일일히 수동으로 Quality check를 했다고 발표에서 전달해줬다.

(여기서 우리팀이 졌다고 생각했다)

EDA라는 것을 처음해본 우리팀은 사실 라벨의 분포정도 확인을 해보았고, 분포를 맞춰주자.. 라는 결론을 내고 

Undersampling, Oversampling, Swap등의 방식을 적용해보고 해당 증강데이터셋을 학습데이터셋으로 사용해본 결과
모델별로 성능이 아주 소폭 상승하거나 대부분 하락했었다.
그렇지만 데이터 셋 내에서 오라벨 등, 노이즈가 껴있을 것이라는 상상을 하진 않았다. 

왜 성능이 오르지 않지라는 분석을 하지 않았다. 그렇기에 데이터 셋을 뜯어볼 생각조차 없었다. 

그 이후에 어느정도 앙상블의 성능향상이 더뎌지자 KoEDA나 다른 방식의 증강을 뒤늦게 생각한 것이 정말 아쉽다.

STS와 같은 단순 태스크들에서는 EDA에 조금 더 시간을 투자할 수 있었을 텐데와 같은 생각을 지금에서야 한다.

2.  무모한 모델 탐색

아까 위에서도 말했듯, 거의 모델 탐색과 동시에 앙상블을 진행했다.

아무래도 첫 프로젝트고, 관련 지식이 없던 나는 어떤 것이 좋은 모델이지 라는 인사이트가 전혀없었다.

사실 그렇기에 모델을 무작위로 시간을 투자해서 많이 실험을 했고, 리더보드에 제출하는 형식으로 성능을 평가했었다.

모델에 대한 이해없이, 높은 순위만을 찾기 위해서 모델 선정의 기준도 없이 실험한 것은 반성해야 한다고 생각한다.

벤치마크라는 것을 뒤늦게 알았고 이 이후 앞으로의 순위형 프로젝트에서 벤치마크를 기준으로 높은 성능의 모델을 먼저 실험해봐야 하겠다는 간단한 생각을 갖게 되었다.

(지금 두세달 전의 나는 무모했다. 거의 30개가 넘는 모델들을 주구장창 돌려봤다)  

3.  무지성 앙상블 

1등 방법론에 대해 들으면서 앙상블을 마지막날 하루 정도만 투자하였고,
그외에는 계속 단일모델로 성능을 높이는 실험을 했다고 전달 받았다.

우리팀, 아니 거의 내가 모델실험을 주로했었는데 높은 성능의 모델들을 계속 무지성으로 앙상블을 진행했다. 
앙상블에 사용된 모델의 개수가 16개인가 (다 많아서 읊지도 못한다)

LV 2에서 Data-Centric 프로젝트를 하는데 해당 프로젝트는 모델의 변경없이 데이터 셋만 변경시켜서 성능을 높이는 프로젝트다.

우리팀은 LV 1때 데이터셋을 하나도 건드리지 않고 모델링 + 앙상블로만 성능을 높이는 프로젝트를 했던 것 같다. 

EDA에 대한 고찰이 필요하다. 정말 우리팀에게 필요하다고 생각했다.

추가적으로 단순히 순위를 높이는 프로젝트를 하는 것 보다 어떤 논리적인 흐름으로 실험을 진행했는지,

그 실험에서 얻을 수 있는 것과 그 결과를 분석하고 정리하는 것이 앞으로의 프로젝트에서 도움이 되리라 생각했다.

앙상블로 좋은 결과를 냈지만, 다른 팀들이 프라이빗에서 대부분 Private 점수가 많이 오르는데 우리팀만 소폭 상승했고,
그 원인을 중첩 앙상블의 과적합이 일어났다고 생각한다.

아쉬웠던 점도 말했으면 잘했던 점도 정리하고자 한다. 

1. 허깅페이스 사용 익히기

컴공 전공이라고 말하기 아쉬울 정도로 사실 인공지능을 알지 못했고, 웹개발은 더군다나 더 모른다. 

생각보다 컴공 출신의 사람들을 만나면 어느정도 인공지능에 대한 공부도 하고오고, Transformer가 뭔지 대략적으로 알고 오는 것 같다.

다만 나는 그런 것들을 전혀 몰랐고, LV 1에서의 강의들이 솔직히 지금도 어렵고, 이해가 다 되는 것은 아니다.

그런 점에서 Hugging Face에 대해 익히는 시간을 많이 가졌고,
단순히 모델을 바꿔가며 실험을 했지만 Hugging Face에는 많이 익숙해졌다.
추가적으로 다양한 기능들을 탐구하게 된 시간이라고 생각한다.

2. 베이스라인 이해하기

파이썬에 대해서는 잘 알았지만 개념이 부족해서인가 파이토치와 관련한 코드는 이해가 잘 되지 않았다.

이를 어떻게 극복했냐 하면은 그냥 뚫어지게 쳐다봤다.

사실 프로젝트에 쏟는 시간이 정말 많았다고 생각한다.
코드를 단순히 돌리는 게 아니라 이코드가 왜 나왔지라는 주석을 달아보며 이해하려 했다.
이런 시간들이 정말 추후 LV 2에서도 도움이 많이 됐다고 생각한다.

3. 깃 사용법 익히기, 협업 툴 적응하기

노션 사용도 익숙하지 않고, 깃 사용도 거의 처음이라 Git Flow에 대한 이해가 부족했는데 사용하면서 Git에 대한 기초를 다졌다.

추후 부스트캠프에서 개발자스럽게 GitHub 사용하기 강의가 있어서 그 때 많은 공부를 했었다. 

깃허브와 랩업리포트를 확인 할수 있게 GitHub 링크를 남겨두겠습니다.

7기 이후 다음 기수분들이 저의 글들을 본다면, 당장 순위에 연연해하지 않고 팀의 실험을 이어나간다면 좋을 것 같습니다~ 

+ 전 기수의 실험들을 너무 쫓지말기! 

아주 살짝 늦었지만,

네이버 부스트캠프 AI Tech 7기 합격 후기를 남기려고 합니다.

네이버 부스트캠프는 워낙 유명한 부트캠프 중 하나라 전공생이라면 한번 쯤 들어보고싶은 교육 중 하나이다.

작년에 웹모바일을 지원했는데 코테가 어렵기도했고 2차 코테에서 떨어진 기억이 있었다.

찾아보니 이런 메일을 발견

워낙 경쟁률이 빡세다는 것도 알고 있고, 떨어져도 더 열심히 공부해서 붙으면 된다는 생각으로 지원했다.
(1년전 23년에는 알고리즘 더 꾸준히 공부해야지 이런 마음이 있었지만, 이 이후로는 사실 알고리즘을 꾸준히 하지는 못했다)

이번 기수에도 웹모바일을 쓸까 고민을 했는데, 졸업프로젝트를 인공지능 CV파트를 하기도 했어서 인공지능 쪽이 재밌어보이기도하고,

흥미가 생겨서 AI Tech를 지원했다.

사실 가산점을 주는 네이버 부스트캠프 AI Tech 부스트 클래스를 신청하고 하나도 듣지를 못했다.

다음 기수에서 희망하시는 분들은 부스트 클래스에서 신청하시고 수료하신 후 부스트캠프를 지원하시면 가산점을 준다고 합니다.
가산점때문은 아니라 사실 캡스톤디자인에서 인공지능 파트를 처음 맡게되서 기초가 너무 부족한거 같아서 들으려고 했지만, 
워낙 캡스톤 디자인 수업이 빡세기도 했고 시간이 잘 나지 않아서 제대로 수료를 하지 못했다.

(이런거 다 핑계겠죠? 하지만,, 뭐 이미 지나간거 붙잡지 않습니다)

모집 요강도 변화가 생겼다.
6기 까지는 코딩테스트가 2번이었는데, 이번에는 1번으로 바뀐것,,

공지를 6월 30일쯤 발견하고 사실 지원서를 7월 2일에 제출하고,

급하게 포트폴리오 정리와 깃허브, 노션 세팅을 시작했다.

지원서에 포트폴리오 넣는 링크나 첨부파일이 준비되어있으니
지원서 작성하실 분들은 미리 준비를 하시기를,,

급하게 준비한다고 전 6월 30일부터 7월 11일까지 세팅을 했습니다.
깃허브, 노션 하나도 쓸줄도 몰랐는데, 급하게 익혔습니다..

(제 플래너도 일부 공개합니다)

클릭하시면 링크로 넘어갑니당

진짜 6월 말~ 7월부터 깃허브 채웠어요.
(진짜 황급하게 세팅하면 링크를 일단 남기시고, 얼른 채워가세요!)

제 깃허브와 노션도 첨부할게요.

자기소개서랑 포트폴리오를 제출하면 코딩테스트와 AI 기초 테스트가 남아있습니다.

개인적으로 코딩테스트의 난이도는 그렇게 어렵지 않았습니다.

백준 기준 실버 상위 정도의 문제들이 나왔다고 생각합니다.
대신 문제가 10문제였습니다.

6기는 프로그래머스에서 7기는 구름에서 코딩테스트를 진행했고,
AI 테스트는 프리코스 온라인 자율학습을 듣고 수강하시면 거의 대부분 무난하게 맞추실수 있는 문제들이
준비되어있습니다. 20문제 모두 객관식이었습니다.

제 기억으로는 3시간 정도의 시간이 주어졌던걸로 기억하고,
저는 개인적으로 2시간정도 후에 퇴실했습니다.

코딩테스트 인증 샷 
(남기려고한게 아니라 주변 환경 모니터링 세팅할때 카메라버튼 눌려져서 캡처 된듯)

코테 끝나고 포트폴리오 빠르게 채워나가시고 
합격날짜가 오면 합격했습니다 라고 메일이 옵니다.

저는 NLP에 지원해서 합격했습니다 
정확한 인원은 말씀드리기가 어렵지만 약 100명 정도가 같이 듣는것 같습니다.

다른 도메인은 각 몇명인지 정확히는 알지 못하지만
CV > NLP > RecSys 이 순서대로 인원이 듣는 것 같습니다.

이후 합격하면 온보딩 키트가 배송됩니다.
(감사합니다 운영진 분들)

플래너, 보조배터리, 노트북받침대, 키링, 스티커 등등 
너무 이쁘게 받아서 쓰고 있습니다.

요근래 저의 일상들,, 이것도 좀 많이 지난 저의 일상입니다.
아직 LEVEL 1임에도 너무 바쁩니다.
LEVEL 1 마지막 프로젝트 한주 남았는데,, busy 합니다.

절대 강의 밀리지 마세요..
나중은 없습니다. 주말에 들어야지, 연휴에 들어야지 이런생각이 드는 순간, 
거의 못듣고 넘어간다고 보면 됩니다 ㅠ
주어진 스케줄에 맞춰서 꼭 들으세요!

새로운 한주가 오지 않기를,, 늘 바라는 저의 마음,, 

문제

https://www.acmicpc.net/problem/1111

아이디어

y=ax+b 꼴이므로 입력값의 개수가 세 개 이상이면 a,b를 구하여 예측값과 비교를 하면 된다.

입력값의 개수가 한개라면 A를 출력

만약 두개라면 공차가 0인 등차수열인지 (두개의 값이 같다면) 값을 출력해주고, 다르다면 등차수열인지 등비수열인지 알수 없으므로 B를 출력한다.

코드

n=int(input())
arr=list(map(int, input().split()))

if n==1: print('A')
elif n==2:
    if arr[0]==arr[1]: print(arr[0])
    else: print('A')
else:
    # y = ax + b , 기울기랑 상수값 찾자
    if arr[1]-arr[0]!=0:
        a=(arr[2]-arr[1]) // (arr[1]-arr[0])
    else: 
        a=0

    b=arr[1]-a*arr[0]
    flag=0
    for j in range(n-1):
        tmp=a*arr[j]+b
        if arr[j+1]==tmp:
            continue
        else:
            print('B')
            flag=1
            break
    
    if flag!=1:
        print(arr[n-1]*a+b)

문제설명

아이디어

부분수열 관련 문제는 accumulate()를 사용하면 편하게 풀릴수 있다고 했는데 이 문제가 바로 그 문제이다.

일단 pulse와 repulse를 [1,-1,1,-1 ...]*sequence , [-1,1,-1,1...]*sequence로 설정하고

각각의 부분수열의 합을 계산하여 최댓값을 출력하는 것이다.

accumulate(pulse, lambda x, y:max(y,x+y))

코드를 보다보면 이 코드가 나오는데, 하나씩 뜯어보면 금방 이해가 될 것이다.

그럼에도 모르겠다면 댓글 달아주세요.

(시작값과 그 다음까지 더한 값을 기준으로 최댓값만 센다는 아이디어.. 이것이 힌트입니다.)

코드

from itertools import accumulate

def solution(sequence):
    n = len(sequence)
    pulse = [((-1)**(i%2))*sequence[i] for i in range(n)]
    repulse = [i*(-1) for i in pulse]
    print(pulse)
    print(repulse)
    arr = []
    arr.append(list(accumulate(pulse, lambda x, y:max(y,x+y))))
    arr.append(list(accumulate(repulse, lambda x, y:max(y, x+y))))
    print(arr)
    
    answer = max(max(arr[0]), max(arr[1]))
    return answer

문제 설명

A 나라가 B 나라를 침공하였습니다. B 나라의 대부분의 전략 자원은 아이기스 군사 기지에 집중되어 있기 때문에 A 나라는 B 나라의 아이기스 군사 기지에 융단폭격을 가했습니다.
A 나라의 공격에 대항하여 아이기스 군사 기지에서는 무수히 쏟아지는 폭격 미사일들을 요격하려고 합니다. 이곳에는 백발백중을 자랑하는 요격 시스템이 있지만 운용 비용이 상당하기 때문에 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 합니다.
A 나라와 B 나라가 싸우고 있는 이 세계는 2 차원 공간으로 이루어져 있습니다. A 나라가 발사한 폭격 미사일은 x 축에 평행한 직선 형태의 모양이며 개구간을 나타내는 정수 쌍 (s, e) 형태로 표현됩니다. B 나라는 특정 x 좌표에서 y 축에 수평이 되도록 미사일을 발사하며, 발사된 미사일은 해당 x 좌표에 걸쳐있는 모든 폭격 미사일을 관통하여 한 번에 요격할 수 있습니다. 단, 개구간 (s, e)로 표현되는 폭격 미사일은 s와 e에서 발사하는 요격 미사일로는 요격할 수 없습니다. 요격 미사일은 실수인 x 좌표에서도 발사할 수 있습니다.
각 폭격 미사일의 x 좌표 범위 목록 targets이 매개변수로 주어질 때, 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

제한 사항

• 1 ≤ targets의 길이 ≤ 500,000
• targets의 각 행은 [s,e] 형태입니다.
  • 이는 한 폭격 미사일의 x 좌표 범위를 나타내며, 개구간 (s, e)에서 요격해야 합니다.
  • 0 ≤ s < e ≤ 100,000,000

아이디어

사실 관련 문제를 너무 많이 풀어서 풀이가 저절로 생각나긴 했다.

구름 Level - 구름 스퀘어 

백준도 같은 방식의 문제를 몇개 풀었는데 번호를 못찾겠다.

핵심 아이디어는 다음과 같다.

시작이 아닌 종료시간을 기준으로 정렬을 먼저 하는 것이다.

종료값을 기준으로 정렬을 하면 같은 시작값이어도 최대 길이의 종료값을 먼저 나타낼수 있기때문이다.

코드

def solution(targets):
    
    target=sorted(targets, key=lambda x: x[1])
    
    #print(target)
    answer, end= 0,0
    for s, e in target:
        if s>=end:
            answer+=1
            end=e
    return answer

문제 설명

비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.

• 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
• 부분 수열의 합은 k입니다.
• 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
• 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.

수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.

제한사항

• 5 ≤ sequence의 길이 ≤ 1,000,000
  • 1 ≤ sequence의 원소 ≤ 1,000
  • sequence는 비내림차순으로 정렬되어 있습니다.
• 5 ≤ k ≤ 1,000,000,000
  • k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.

아이디어

- accumulate() 함수를 사용한다 -> 시간복잡도가 복잡 ->실패

- 투포인터를 사용한다.

부분수열 관련 문제는 두가지 아이디어가 있다. 일반적으로 투포인터를 주로 사용하면 원하는 조건에 맞는 값을 출력할수 있다. 

부분수열을 구하라라는 문제가 있다면 accumulate()를 사용하면 편리한 경우도 있기에 문제에 따른 시간복잡도에 따라 선택하는 것이 좋다.

틀린 코드 (44.1/100)

from itertools import accumulate

def solution(sequence, k):
    s,e=0,0
    n=len(sequence)
    answer=[]
    empty=[]
    for i in range(n):
        empty.append(list(accumulate(sequence[i::])))
        
    #print(empty)
    for i in range(n):
        for j in range(len(empty[i])):
            if empty[i][j]==k:
                answer.append([i,j+i])

    answer.sort(key = lambda x: (x[1]-x[0]))
    
    return answer[0]

accumulate() 함수를 이용하여 부분수열을 모두 구하고, 합을 만족하는 부분수열을 찾고 길이가 가장 짧은 것을 출력했다.

시간복잡도가 굉장히 높아서 대부분이 시간초과로 뜨게 되었다.

O(n^3)의 최악의 시간복잡도로 예상한다.

정답 코드 

def solution(sequence, k):
    s,e=0,0
    n=len(sequence)
    answer=[]
    
    for i in range(n):
        while s<k and e<n:
            s+=sequence[e]
            e+=1
        if s==k:
            answer.append([i,e-1])
        s-=sequence[i]
        
    answer.sort(key=lambda x: x[1]-x[0])
    
    return answer[0]

투포인터를 이용하여 풀이하면 편리하다.

부분수열의 문제는 주로 투포인터라는 전형적인 풀이가 있다. 이를 활용하면 잘 풀린다.

이번 문제는 부분수열의 합이 주어진 값과 같은지 보는 것이기에,

만약 [s,e]구간에서의 합이 주어진 값보다 크다면 s값을 늘려주고 합보다 작다면 e값을 늘리면서 비교하는 것이다.

이렇게 풀이하면 시간복잡도가 O(n^2) 정도 나온다.

문제 설명

과제를 받은 루는 다음과 같은 순서대로 과제를 하려고 계획을 세웠습니다.

• 과제는 시작하기로 한 시각이 되면 시작합니다.
• 새로운 과제를 시작할 시각이 되었을 때, 기존에 진행 중이던 과제가 있다면 진행 중이던 과제를 멈추고 새로운 과제를 시작합니다.
• 진행중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춰둔 과제를 이어서 진행합니다.
  • 만약, 과제를 끝낸 시각에 새로 시작해야 되는 과제와 잠시 멈춰둔 과제가 모두 있다면, 새로 시작해야 하는 과제부터 진행합니다.
• 멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작합니다.

과제 계획을 담은 이차원 문자열 배열 plans가 매개변수로 주어질 때, 과제를 끝낸 순서대로 이름을 배열에 담아 return 하는 solution 함수를 완성해주세요.

제한사항

• 3 ≤ plans의 길이 ≤ 1,000
  • plans의 원소는 [name, start, playtime]의 구조로 이루어져 있습니다.
    • name : 과제의 이름을 의미합니다.
      • 2 ≤ name의 길이 ≤ 10
      • name은 알파벳 소문자로만 이루어져 있습니다.
      • name이 중복되는 원소는 없습니다.
    • start : 과제의 시작 시각을 나타냅니다.
      • "hh:mm"의 형태로 "00:00" ~ "23:59" 사이의 시간값만 들어가 있습니다.
      • 모든 과제의 시작 시각은 달라서 겹칠 일이 없습니다.
      • 과제는 "00:00" ... "23:59" 순으로 시작하면 됩니다. 즉, 시와 분의 값이 작을수록 더 빨리 시작한 과제입니다.
    • playtime : 과제를 마치는데 걸리는 시간을 의미하며, 단위는 분입니다.
      • 1 ≤ playtime ≤ 100
      • playtime은 0으로 시작하지 않습니다.
    • 배열은 시간순으로 정렬되어 있지 않을 수 있습니다.
• 진행중이던 과제가 끝나는 시각과 새로운 과제를 시작해야하는 시각이 같은 경우 진행중이던 과제는 끝난 것으로 판단합니다.

아이디어

일단 입력된 plans의 구조를 바꾸려고 한다.

문자형으로 입력된 "06:30"등의 형식을 모두 분, 정수형으로 변환시켜서 비교하는 것이 좋다.

이때 리스트 슬라이싱을 이용하여 정수형으로 바꾸는 것이 좋고, 이후 변환된 분을 기준으로 오름차순 정렬을 진행한다.

이후 스택 자료구조를 사용하여 진행중인 과제에 넣고 다음과제와 현재과제의 시간차이를 계산한다.

만약 시간차이가 현재 과제 진행하는 시간보다 적다면 완료리스트에 현재과제를 추가하고, 진행중인 과제를 pop한다.

반대로 현재 과제를 진행하는 시간이 많이 걸린다면, 앞으로 과제 수행하는데 걸리는 시간을 업데이트해주고 시간차이를 0으로 초기화 해준다.

마지막으로 마지막 과제와 남아있는 진행중인 과제는 역순으로 저장하여 출력한다.

코드

def solution(plans):
    answer=[]
    now=[]
    #배열 시간순으로 정렬
    #배열 수정: 시간을 모두 분으로 수정, 문자형 정수를 정수형으로 수정
    plans.sort(key=lambda x:x[1])
    for i in range(len(plans)):
        plans[i][1]=int(plans[i][1][0:2])*60+int(plans[i][1][3:])
        plans[i][2]=int(plans[i][2])
    
    for i in range(len(plans)-1):
        #현재과제와 다음과제 차이 계산
        now.append(plans[i])
        diff=plans[i+1][1]-plans[i][1]
        
        #시간차이가 업거나 진행중인 과제가 없을때까지 반복
        while now and diff:
            #현재과제 해결 가능: 완료리스트(answer)에 추가, 진행중과제 pop
            if now[-1][2]<=diff:
                diff-=now[-1][2]
                answer.append(now[-1][0])
                now.pop()
            #현재과제 해결 불가능: 진행중인 과제에 시간차이 업데이트
            else: 
                now[-1][2]-=diff
                diff=0
    
    #마지막과제와 남아있는 진행중인 과제 역순으로 저장
    answer.append(plans[-1][0])
    while now:
        answer.append(now[-1][0])
        now.pop(-1)
    
    return answer

# 약 한시간 정도 소요
# 시간복잡도 O(n*logn)

문제 설명

마인은 곡괭이로 광산에서 광석을 캐려고 합니다. 마인은 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이를 각각 0개에서 5개까지 가지고 있으며, 곡괭이로 광물을 캘 때는 피로도가 소모됩니다. 각 곡괭이로 광물을 캘 때의 피로도는 아래 표와 같습니다.

예를 들어, 철 곡괭이는 다이아몬드를 캘 때 피로도 5가 소모되며, 철과 돌을 캘때는 피로도가 1씩 소모됩니다. 각 곡괭이는 종류에 상관없이 광물 5개를 캔 후에는 더 이상 사용할 수 없습니다.

마인은 다음과 같은 규칙을 지키면서 최소한의 피로도로 광물을 캐려고 합니다.

• 사용할 수 있는 곡괭이중 아무거나 하나를 선택해 광물을 캡니다.
• 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용합니다.
• 광물은 주어진 순서대로만 캘 수 있습니다.
• 광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물을 캡니다.

즉, 곡괭이를 하나 선택해서 광물 5개를 연속으로 캐고, 다음 곡괭이를 선택해서 광물 5개를 연속으로 캐는 과정을 반복하며, 더 사용할 곡괭이가 없거나 광산에 있는 모든 광물을 캘 때까지 과정을 반복하면 됩니다.

마인이 갖고 있는 곡괭이의 개수를 나타내는 정수 배열 picks와 광물들의 순서를 나타내는 문자열 배열 minerals가 매개변수로 주어질 때, 마인이 작업을 끝내기까지 필요한 최소한의 피로도를 return 하는 solution 함수를 완성해주세요.

제한사항

• picks는 [dia, iron, stone]과 같은 구조로 이루어져 있습니다.
  • 0 ≤ dia, iron, stone ≤ 5
  • dia는 다이아몬드 곡괭이의 수를 의미합니다.
  • iron은 철 곡괭이의 수를 의미합니다.
  • stone은 돌 곡괭이의 수를 의미합니다.
  • 곡괭이는 최소 1개 이상 가지고 있습니다.
• 5 ≤ minerals의 길이 ≤ 50
  • minerals는 다음 3개의 문자열로 이루어져 있으며 각각의 의미는 다음과 같습니다.
  • diamond : 다이아몬드
  • iron : 철
  • stone : 돌

아이디어

한번에 캘수 있는 광물은 5개이기에 5개씩 일단 minerals를 분할합니다.

이후 diamond, iron, stone으로 채굴할 수 있는 비용을 계산합니다.

costs가 적게드는 순서대로 정렬

이후 주어진 pick 개수 내에서 최소비용으로 채굴한다.

코드 - 틀린 코드 (97.1/100)

def solution(picks, minerals):
    answer = 0
    mineral_list=[]
    for i in range(0, len(minerals), 5):
        mineral_list.append(minerals[i:i+5])

    costs = []
    for mineral in mineral_list:
        cost = [0, 0, 0] 
        for mine in mineral:
            if mine == 'diamond':
                cost[0], cost[1], cost[2] = cost[0]+1, cost[1]+5, cost[2]+25
            elif mine == 'iron':
                cost[0], cost[1], cost[2] = cost[0]+1, cost[1]+1, cost[2]+5
            elif mine == 'stone':
                cost[0], cost[1], cost[2] = cost[0]+1, cost[1]+1, cost[2]+1
        costs.append(cost)
    
    costs.sort(key=lambda x: (-x[2]))
    
    # 주어진 픽 개수 내에서 최소 비용으로 채굴
    for cost in costs:
        if picks[0] > 0:
            picks[0] -= 1
            answer += cost[0]
            continue
        if picks[1] > 0:
            picks[1] -= 1
            answer += cost[1]
            continue
        if picks[2] > 0:
            picks[2] -= 1
            answer += cost[2]
            continue
    
    return answer

# 소요시간 40분
# 시간복잡도 O(nlogn)

코드 - 정답 코드

def solution(picks, minerals):
    answer = 0
    # 미네랄 5개씩 쪼개기
    
    mineral_list=[]
    for i in range(0, len(minerals), 5):
        mineral_list.append(minerals[i:i+5])

    # 각 미네랄 묶음의 채굴 비용 계산
    costs = []
    for mineral in mineral_list:
        cost = [0, 0, 0] 
        for mine in mineral:
            if mine == 'diamond':
                cost[0], cost[1], cost[2] = cost[0]+1, cost[1]+5, cost[2]+25
            elif mine == 'iron':
                cost[0], cost[1], cost[2] = cost[0]+1, cost[1]+1, cost[2]+5
            elif mine == 'stone':
                cost[0], cost[1], cost[2] = cost[0]+1, cost[1]+1, cost[2]+1
        costs.append(cost)
    else:
        # 곡갱이 수보다 많은 광물캐는 것 불가능
        while len(costs)>sum(picks): costs.pop()
    
    # 비용이 가장 적게 드는 순서대로 정렬
    costs.sort(key=lambda x: (-x[2]))
    
    # 주어진 픽 개수 내에서 최소 비용으로 채굴
    for cost in costs:
        if picks[0] > 0:
            picks[0] -= 1
            answer += cost[0]
            continue
        if picks[1] > 0:
            picks[1] -= 1
            answer += cost[1]
            continue
        if picks[2] > 0:
            picks[2] -= 1
            answer += cost[2]
            continue
    
    return answer

틀린 이유로는 mineral이 5개 단위로 쪼갰지만, 5의 배수 단위로 존재하지 않기때문에 costs가 곡갱이 수보다 많아지는 경우가 생기기 때문이다. 그래서 코드를 수정하였다.