코딩테스트 연습 - 디스크 컨트롤러 | 프로그래머스 (programmers.co.kr)

문제설명은 위의 링크를 확인하면 된다.

일단. CPU 스케줄링 알고리즘 중 SJF (Shortest Job First) 비선점형 알고리즘을 활용한다
CPU스케줄링 참조 : CPU 스케쥴링 알고리즘 : FCFS, SJF, HRN, RR, SRT [과제 : 구현하기] : 네이버 블로그 (naver.com)

큐에 있는 프로세스 중 작업시간이 가장 짧은 프로세스를 실행하는것으로, 그 순간순간에 가장 빨리 끝날녀석을 위주로 실행하는것이다. 

사실 이 스케줄링에도 문제점이 있는데, 작업의 종료시간을 정확히 예측할 수 없다는 것과, 작업시간이 긴 프로세스의 경우, 짧은녀석들에게 밀려서, 한없이 기다리고만 있을 수 있다는 단점이 존재한다 (아사현상). 그렇기에 이 문제를 Aging에이징기법으로 프로세스가 순서를 양보할때마다 카운트해서 한계점까지만 양보하도록 하는 방법을 통해 해결한다. 

간략한 CS에 대한 설명은 여기까지하고, 이제 위 문제를 풀어보자!

from heapq import *
from collections import deque
def solution(jobs):
	jobs = deque(sorted(jobs, key=(lambda x: (x[0],x[1]))))
    waited=0
    n=0
    cnt=jobs[0][0] # 첫 작업 도착시간으로 세팅
    a,b = jobs.popleft()
    hq=[[b,a]]
    while hq or jobs:
        if hq:
            n+=1 # job개수카운트
            jobtime,come = heappop(hq) # 작업시간 , 도착시간
            cnt += jobtime 
            waited+=(cnt-come)
        else:
            cnt+=1
        while jobs:
            if jobs[0][0]<=cnt:
                nextjob = jobs.popleft()
                heappush(hq, [nextjob[1], nextjob[0]])
            else:
                break
        
        print(f'남은 jobs{jobs}\t 현재 HEAP:{hq}, \t\t현재 cnt : {cnt}\t\t현재 waited:{waited}')
    return waited//n

# jobs=[[24, 10], [28, 39], [43, 20], [37, 5], [47, 22], [20, 47], [15, 34], [15, 2], [35, 43], [26, 1]]
jobs=[[0,3],[1,9],[2,6]]
solution(jobs)

힙과 deque를 사용했다. 
Deque를 사용한 이유는 처음 들어온 jobs를 queue형식으로 앞에서부터 꺼내쓰기위해서다. 
굳이 그렇게 안하고 sorted로 역순정렬 후 스택을 활용해도 좋다. (개인취향)

맨처음 heap (hq)에 첫 작업을 넣어주고 시작한다. 제일 먼저도착한, 제일 짧게 끝낼수있는 녀석을 넣어주고 시작한다. 
이후 while문에서는 hq와 jobs가 남아있다면 계속해서 반복하도록 구성하였으며, 

cnt와 waited를 설정하였는데, 
cnt는 순간순간의 초시계라고 생각하면되고, waited는 해당 초에서 heap도착시간을 빼주면서 기록한다. 

if hq에서는 힙에 작업이 있다면, 바로 꺼내서(가장 빨리 끝낼 수 있는 프로세스를) , cnt와 waited를 계산해준다. 
else구문은, hq가 비어있지만, jobs가 남아있는 상황에서 실행된다고 보면된다. 
예를들어 jobs가 [[0,3],[1,9],[20,6]] 이라면, 12초까지 cnt된 후, hp가 비어있는 상태에서 while문의 조건이 cnt보다 남은 작업의 도착시간이 작아야하므로, cnt를 계속 증가시키는것이다. 
그리하여 20초까지 카운트가 진행되면, 다시 작업이 들어가서 마지막작업까지의 계산을 할 수 있게 되는것이다.

while jobs : 구문은 deque로 만들어진 jobs에서, 맨 앞 (빨리도착한순)녀석이 현재 시간 카운트에 맞아떨어진다면 (현재 카운트보다 작거나 같음), 해당하는 프로세스까지 heaq에 넣어주는 기능을 수행하게된다.

위와같은 출력형태를 볼 수 있다.

https://programmers.co.kr/learn/courses/30/lessons/12979

전체 아파트들을 순회하는것은 불가능하다고 생각하면 된다.

문제에서 첫번째 아이디어는, 기지국을 통해 중간중간 설치가 필요한 구간을 구하는것이다.

이후, 각 station에서 w+1만큼 뺀 길이로 구간을 구하면 된다.

1. 첫번째 station과 1번집 사이에서 구간 생기는지

2. station사이사이에서 각각의 구간길이 구하기

3. 마지막 station과 N번째 집 사이에 구간이 생기는지

이후, 각각 구간 길이를 2w+1만큼 나눠서 올림처리 해주어 더하면 answer가 완성된다.

첫번째 풀이

def solution(n, stations, w):
    answer=0
    segs=[]
    for i,v in enumerate(stations):
        if i==0: #처음
            segs.append(v-w-1)
        else: # 중간
            segs.append(v-w-1-(stations[i-1]+w))
    if stations[-1]+w < n : #마지막
        segs.append(n-(stations[-1]+w))

    for seg in segs:
        if seg%(2*w+1)==0:
            answer += seg//(2*w+1)
        else:
            answer += seg//(2*w+1)+1
    return answer
solution(N,stations,w)

굳이, Segs를 또 순회할 필요가 없다고 생각되었다.
그리하여 한번에 처리해버리도록 다시 코드를 짰다

def solution(n, stations, w):
    def getneeds(seg):
        if seg%(2*w+1)==0:
            return seg//(2*w+1)
        else:
            return seg//(2*w+1)+1
    answer=0
    for i,v in enumerate(stations):
        if i==0: #처음
            answer+=getneeds(v-w-1)
        else: # 중간
            answer+=getneeds((v-w-1-(stations[i-1]+w)))
    if stations[-1]+w < n : #마지막
        answer+= getneeds(n-(stations[-1]+w))
    return answer
solution(N,stations,w)

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 (wikipedia.org) , 코딩테스트 연습 - 소수 만들기 | 프로그래머스 (programmers.co.kr)

주어진 배열 속에서 숫자 3개를 뽑아서 만들 수 있는 소수의 개수를 찾는 문제. 

크게 2파트로 나뉜다. 

1. 숫자 3개 뽑아 더하기

2. 소수 판별

소수를 판별하는데는, 가장 효율적인 방법인 에라토스테네스의 체를 활용했다. 

숫자 3개를 뽑아 더하는것에 있어서는, 배열 속 중복된 수가 없다는점과, 비복원추출의 방법을 사용해야하므로, 
combinations 를 사용했다.

from itertools import combinations
def solution(nums):
    def mknum(n):
        arr=[i for i in range(n+1)]
        
        for i in range(2,(n//2)+1):
            # print(arr)
            if arr[i]<2: continue
            else:
                cnt=2
                while i*cnt < len(arr):
                    # print(i*cnt)
                    arr[i*cnt]=0
                    cnt+=1
        return [i for i in arr[2:] if i!=0]
    
    arr=mknum(max(nums)*3)
    numlist=list(map(lambda x : sum(x), list(combinations(nums,3))))
    answer=0
    for n in numlist:
        if n in arr:
            answer+=1

    return answer
solution([1,2,7,6,4])

코딩테스트 연습 - [1차] 프렌즈4블록 | 프로그래머스 (programmers.co.kr)

문제설명은 위의링크에서 읽고 진행하는것을 추천합니다.

일단. 이 문제를 풀려면 최소 3개의 파트와 기능이 구현되어야한다고 생각되었다.

1번으로 Check!
보드의 인덱스에 따라 그녀석을 왼쪽위로하는 4칸을 터트릴 수 있는지 확인해야한다. 
Stride개념 (칸 건너뛰기) 을 줘서 풀면 안되는데, 그 이유는 6칸이 터져야하는데, 이걸 한칸건너뛰는 방식으로 갈 경우, 4칸만 터지고 넘어갈 것이라 그러하다.

2번으로 breaking!
찾았으면 터트려야한다. 
난 이부분을 check함수에 if문 분기를 달리하여 재활용했다. 그 이유는 어짜피 체크에서도 4칸을 뒤져봐야하고, 터트릴때고 4칸을 돌아야하기때문데, 굳이 새로운함수를 만들 필요가 없다고 생각했다.
그리하여 breaking이라는 파라미터를 줘서, 이게 체크용도로 쓰는것인지, 터트리는 용도로 쓰는것인지 조건에 따라 분기시켰다. 

3번으로 clead!
터트렸으면, 위에있는녀석들이 아래로 떨어지는것을 구현해야했다. 
사실상 코딩할때 가장 고민되었던 부분이며, 좀 더 효율적으로 짜고싶다는 욕심으로 이미 비어버린 보드row,col은 지워버릴까..도했지만, 그러면 m,n을 다시 계산해주면서 해야하는데, 그게 사실 너무 귀찮아서 다시 이터레이션을 돌도록 만들어버렸다.
만들땐 각 column마다 아래로 내려끌도록하였으며, 그 함수안에 Queue 개념을 사용했고, 맨 아랫층부터 시작하는형태로 iteration을 돌렸다.

def solution(m,n,board):
    answer=0
    bd=[[i for i in row] for row in board]
    while True:
        bklist=[]
        for i in range(m-1): # 맨오른쪽과, 맨아랫라인은 체크할 필요가 없음 
            for j in range(n-1):
                tf,_=check(bd,i,j,m,n,0)
                if tf: # check
                    bklist.append([i,j])
        if bklist :
            for i,j in bklist:
                answer += check(bd,i,j,m,n,1)[1]
            for col in range(n):
                clearbd(bd,m,col)
        else:
            break
    return answer

def check(bd,i,j,m,n,breaking):
    if bd[i][j]==0 and breaking!=1: return False, 0
    adx=[0,0,1,1]
    ady=[0,1,0,1]
    bkcnt=0
    for dx,dy in zip(adx,ady):
        x=i+dx
        y=j+dy
        if breaking:
            if bd[x][y]==0 : pass
            else: 
                bd[x][y] = 0
                bkcnt+=1
        elif x<m and y<n:
            if bd[x][y] != bd[i][j]: 
                return False, bkcnt
    return True, bkcnt

def clearbd(bd,m,col):
    tmp=[]
    tog=1
    for row in range(m-1,-1,-1):
        if bd[row][col]!=0:
            tmp.append(bd[row][col])
            bd[row][col]=0
    for row in range(m-1 , m-len(tmp)-1 , -1):
        bd[row][col] = tmp.pop(0)
# m,n,board = 4,5,["CCBDE", "AAADE", "AAABF", "CCBBF"]#14
m,n,board = 6,6,["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"]#15
solution(m,n,board)

코딩테스트 연습 - [1차] 뉴스 클러스터링 | 프로그래머스 (programmers.co.kr)

일단 나는 문자열을 토대로 str1 과 str2 의 딕셔너리를 만들어주고, 

이후, 교집합과, 합집합을 계산해준다음

최종적으로, 65536 계산을 통해 return하는 형식으로 풀었다. 

import re
# str1,str2,answer='FRANCE,french,16384'.split(',')
# str1,str2,answer='handshake,shake hands,65536'.split(',')
# str1,str2,answer='aa1+aa2,AAAA12,43690'.split(',')
# str1,str2,answer='E=M*C^2,e=m*c^2,65536'.split(',')
def mkstdic(str):
    dic={}
    for i in range(len(str)-1):
        now = str[i]+str[i+1]
        now = re.sub('[^a-z]','',now)
        if len(now)<2: continue
        if dic.get(now):
            dic[now]+=1
        else:
            dic[now]=1
    return dic

def solution(str1,str2):
    a,b = mkstdic(str1.lower()), mkstdic(str2.lower())
    kyo={}
    hap={}
    for ak in a:
        if ak in b:
            kyo[ak] = min(a[ak],b[ak])
            hap[ak] = max(a[ak],b[ak])
        else:
            hap[ak] = a[ak]
    for bk in b:
        if bk in a: continue
        else: hap[bk] = b[bk]
    oper = sum(map(lambda x : kyo[x], kyo))
    div = sum(map(lambda x : hap[x], hap))
    if div == 0 : return 65536
        return int((oper/div)*65536)
solution(str1,str2)

코딩테스트 연습 - [3차] n진수 게임 | 프로그래머스 (programmers.co.kr)

문제는 위 링크에서 확인하는것이 더욱 나을것같다.

일단 문제를 푸는데있어서 3가지 주요 부위로 나눴다.

첫번째는 divmod를 활용하여, N진수  String을 만들어주는 부분

두번째는 튜브가 말해야하는 길이보다 좀 더 길게, 그 순서까지 텍스트를 뽑으며 추가해주는 부분

세번째는 , 순서에 맞게 튜브가 말할 answer를 만드는 부분

# n진수 게임 (카카오 2018블라인드)
def solution(n,t,m,p):
    def getdiv(n, div):
        words = "0123456789ABCDEF"
        ans=""
        tmp=[]
        while n>=div:
            tmp.append(divmod(n,div)[1])
            n=divmod(n,div)[0]
        tmp.append(divmod(n,div)[1])
        while tmp:
            ans+=words[tmp.pop()]
        return ans

    start=0
    tmp = ''
    while len(tmp)< (t)*(m+1) :
        tmp +=  getdiv(start,n)
        start+=1
    
    answer = ""
    idx = p-1
    while len(answer) < t :
        answer+=tmp[idx]
        idx += m
    return answer

# n,t,m,p = 2,4,2,1
# n,t,m,p = 16,16,2,1
n,t,m,p = 16,16,2,2
solution(n,t,m,p) # n진법, 미리구할 수 t, 게임인원 m , 튜브의 순서 p

코딩테스트 연습 - 다단계 칫솔 판매 | 프로그래머스 (programmers.co.kr)

문제에 대한 설명은 링크를 직접 들어가서 확인하는것이 가장 좋을것이라고 생각된다.

일단, enroll과 referral를 사용해서, 각자의 부모 ( 추천자) 가 누구인지 확인할 수 있는 형태의 dictionary를 만들고, 
seller와 amount를 처리한다.

여기서 주의해야할점이있는데, 15원과 같이 남아있을 때, 돈의 처리이다.

15//10을 하면 1원이므로, 부모에게 1원만큼을 넘기고, 자신이 14원을 갖는 형태로 진행해야한다.
이 부분에 대한 아이디어를 생각하지 못하고 문제를 풀다가 , 계속 막혀서 한참 고생했다.

일단 DFS로 문제를 풀었다.

from collections import defaultdict
def mktree(enroll, referral):
    dic=defaultdict()
    for ee, ref in zip(enroll,referral):
        if ref=="-":
            dic[ee] = ['',0]
        else:
            dic[ee]=[ref,0]
    return dic
def solution(enroll, referral, seller, amount):
    dic=mktree(enroll,referral)
    # print(dic)
    for sell,amou in zip(seller,amount):
        coin = amou*100
        forparent=coin//10
        
        if dic[sell][0]=='':# 부모가센터
            dic[sell][1] += coin-forparent
            # print('부모가센터',dic[sell][1])
        
        else: # 다른추천자가있어
            que=[]
            que.append(sell)
            while que:
                now = que.pop()
                # print(now, coin, forparent)
                if now in dic:
                    if coin >= 1:
                        # print(now,':',dic[now][1],'+',round(coin-forparent))
                        dic[now][1] += round(coin-forparent)
                        que.append(dic[now][0])
                        coin = forparent
                        forparent = coin//10
                    else:
                        dic[now][1] += coin
    answer = [int(i[1][1]) for i in dic.items()]
    return answer

코딩테스트 연습 - 매칭 점수 | 프로그래머스 (programmers.co.kr)

어우.... re모듈 진짜 끔찍하게 사용했다...

이건 .. 문제 설명을 여기에 붙이는게 무의미한 수준이다.

노가다 끝판왕이라고 생각하면 될거같고... re모듈에 친숙하다면 노가다가 조금 더 쉬웠을지 않을까..싶다

굳이 문제에 대한 풀이를 설명하기에 이 문제를 푸는 로직에 대해 설명하는게 최선일거같다.

1. (기본점수 계산) pages들에 대하여 각 page마다 자신의 이름, 기본점수, 외부링크를 찾아서 딕셔너리화한다
딕셔너리는 { 페이지이름 : [인덱스, 기본점수, 0 (외부점수), [외부링크List]] 의 형태로 구성했다.

2. (외부점수 계산) 딕셔너리의 페이지이름마다 돌며, 자신이 가진 외부링크에 기본점수 / 외부링크수 를 더해서 해당 외부링크페이지의 외부링크점수를 넣어준다

3. 각 페이지의 [ 인덱스, 기본+외부점수 ] 를 원소로 하는 answer list생성

4. answer list를 점수값 기준 오름차순 소팅 + 인덱스 겹치면 더 낮은인덱스가 뒤로오도록 소팅

5. 마지막꺼 return

def getPage(page, word):
    basic_score = 0
    tmp = re.findall(r'<meta property.*?>', page) ## 자기 링크
    mypagename = re.findall(r'https://.*?"',tmp[0])[0].split('"')[0]

    # print('My Page name :',mypagename) ## My Page Name

    external =  re.findall(r'<a href=.*?</a>', page) ## 외부링크수
    extlist=[]
    for ext in external:
        tmp = ext.split('"')[1]
        extlist.append(tmp)
    # print("External Page list :",extlist)

    tokens = re.sub(pattern="[0-9-=+,#/\?:^$.@*\"※~&%ㆍ!』\\‘|\(\)\[\]\<\>`\'…》]", repl=' ',string=page).split()
    for token in tokens:
        if token == word.lower(): basic_score +=1
    # print(basic_score)
    return mypagename, extlist, basic_score

def solution(word , pages):
    # answer = 0
    rank = {}
    for i,page in enumerate(pages):
        myp, extlist, bs  = getPage(page.lower(), word)
        rank[myp] = [i,bs, 0 ,extlist]
    # print(rank)
    for page in rank:
        # print(page,'외부점수주기')
        for ext in rank[page][3]:
            # print(ext, rank[ext])
            if rank.get(ext):
                rank[ext][2] += rank[page][1] / len(rank[page][3]) # basicScore / link 개수
    answer=[]
    for page in rank:
        answer.append([rank[page][1]+rank[page][2], rank[page][0]])
    return sorted(answer, key=(lambda x: (x[0],-x[1])))[-1][-1]

문제 URL : 코딩테스트 연습 - 보석 쇼핑 | 프로그래머스 (programmers.co.kr)

처음 접근

gems = ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] #[3, 7]
# gems = ["AA", "AB", "AC", "AA", "AC"] #    [1, 3]
# gems = ["XYZ", "XYZ", "XYZ"]#    [1, 1]
# gems = ["ZZZ", "YYY", "NNNN", "YYY", "BBB"]#    [1, 5]
def solution(gems = gems):# 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아 구매하기
    answer = []
    gemkind=set(gems) ## O(n)
    anslist=[]
    for i,v in enumerate(gems): # 어짜피 한번은 다 돌아야해
        tmp=[v,]
        tmpidx=[i+1,]
        for j,vv in enumerate(gems[i+1:]):
            ## 나랑 같은게 뒤에도 있는데, 아직 보석을 다 담지 못했어 -> 해당 인덱스부터 시작하는조합은 X야
            if vv == v and len(tmp)<len(gemkind): break 

            if vv not in tmp:
                tmp.append(vv)
                tmpidx.append(i+j+1+1)
        if len(tmp) == len(gemkind) : 
            # tmpidx[-1] - tmpidx[0]
            anslist.append([tmpidx[-1] - tmpidx[0],tmpidx])
    anslist = sorted(anslist, key=(lambda x : (x[0], x[1][0])))
    # print(anslist)
    if len(anslist[0][1])==1:
        ans = [anslist[0][1][0] , anslist[0][1][0]]
    else:
        ans = [anslist[0][1][0], anslist[0][1][-1]]
    return ans

solution()

$O(n^2)$ 의 방법으로 생각했다.
시작은 이러하다. 어떠한 인덱스(i) 에서 시작했을 때, 그녀석부터 뒤로가면서 보석을 담는다.
그런데! 만약, 동일한 보석이 발견됐는데, 아직 보석종류를 다 담지 못했다? 그 말은, i부터 시작하는 보석바구니는 최선의 구간이 아니라는 생각이다.

예를들어 첫번째 테스트케이스를 생각했을 때
gems = ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] 에서, 0번인덱스로 시작을 한다면, j가 1씩 증가하며 보석을 검사한다, 그런데 gems[3]에 'DIA'가 또 발견이 됐다. 아직 에메랄드와 사파이어가 남아있는데 같은 보석을 발견한것이므로, 0번에서 시작하는 보석바구니는 최선의 구간이 아니라는것이다.

그렇게 gems[1] 또한 넘어가고, gems[2]에서 시작하면 RUBY , DIA , DIA, EMERALD, SAPPHIRE 를 발견한 순간, anslist에 붙이고, 다음 이터레이션을 시작한다.

결과는.. 정확도테스트는 다 맞췄으나, 효율성에서 OUT..

해결법 : 투포인터

1차원 배열에서 사용 가능하며 $O(n^2)$ 보다 작은 시간복잡도로 풀어야할 때 사용하기 좋은 알고리즘으로, start와 end 포인터를 움직이며 최적의 바구니를 만드는것이라 생가갛면 된다 .
ex. N칸의 1차원배열에서, 그 부분배열 중 원소합이 M이 되는 경우의 수를 구하기
start , end = 0,0으로 시작 , 언제나 start <= end 이어야함
start와 end는 현재 부분배열의 시작과 끝
3-1. 현재 부분합이 M 이상이거나 , 이미 end = N 이라면 :: start ++
3-2. 그렇지 않다면 end ++ 3-3. 현재 부분합이 M과 같다면 결과 ++

위 문제에 적용

s, e 두개의 포인터를 사용
바스켓에 모든 종류의 보석을 담을때까지 e를 이동하며, 바스켓에 추가
매 iteration에서 e를 이동가능한지 체크하여 수행한 수 바스켓이 가득찼는지 (모든종류의 gem을 담았는지) 검사
-> 바스켓이 가득찼다면? -> s를 이동하면서 바스켓에서 하나씩 빼면서 뺼 때마다의 answer가 최적인지 검사

def solution(gems):
    answer = [1,len(gems)]
    s,e = 0,0
    lengem = len(gems)
    gemkind = set(gems)
    if len(gemkind) == 1 : return [1,1]
    basket = {gems[0]:0}
    while s<lengem and e<lengem:
        if len(basket) < len(gemkind): # e 이동
            if basket.get(gems[e]):
                basket[gems[e]] +=1
            else:
                basket[gems[e]] = 1
            e+=1
        while len(basket) == len(gemkind): # s이동
            if basket[gems[s]] > 1:
                basket[gems[s]] -=1
            else:
                del(basket[gems[s]])
            s += 1
            if answer[1]- answer[0] > e-s:
                answer = [s, e]
    return answer
    ```