이코테의 문자열 뒤집기. 

0과 1로만 이루어진 문자열 S에서, 문자열 내 모든 숫자를 전부 같게 만들때 
연속된 하나 이상의 숫자를 잡고 모두 뒤집는게 가능한 상황 (카운트 1번으로 처리) 에서 최소한으로 뒤집는 횟수는?

# 이코테 문자열뒤집기 - 313페이지
# 1을 0으로 또는 0을 1으로 해서 모든 숫자를 같게 만들기 (0,1로만 이루어짐), 
# 한 카운트는 한번에 연속된 하나이상의 숫자를 잡고 모두 뒤집는것... 이때 카운트 수 return하기
def solution(s):
    def flip(ss, n):
        cnt=0
        s=ss[:]
        l,r=0,0
        while r < len(s):
            if s[r]==n:
                print(l,r,s[r],'Go')
                r+=1
                l+=1
            else:
                while r<len(s) and s[r]!=n:
                    r+=1
                print(l,r,'Cnt++')
                cnt+=1
                l=r
        return cnt
    answer=0
    count = min(flip(s, '0'), flip(s,'1'))
    return count

나의 풀이 : 더블포인터 아이디어로 구현, 
flip이라는 함수를 통해, 0으로 뒤집을때, 1로 뒤집을때 두번 시행. 
n을 인자로 하여 어떤 숫자로 뒤집을지 받은다음, r을 기준으로 s[r]이 n과 같으면 그대로 지나감 (뒤집을 필요가 없으니까)
다르다면, 그 순간 while문에서 뒤집어야할 녀석들까지 점핑
최종, l,r은 뒤집고난 다음 인덱스로 넘어가고, count는 1 증가 

책 풀이

def solution(s):
    cnt0=0
    cnt1=0
    if s[0]=='1':
        cnt0+=1
    else:
        cnt1+=1
    for i in range(len(s)-1):
        if s[i] != s[i+1]:
            if s[i+1]=='1': cnt0+=1
            else:cnt1+=1
    print(cnt0, cnt1)

s='0001100'
solution(s)

훨씬 깔끔.. 
딱 한번 돌아가면서, cnt0, cnt1을 동시에 올려버림

코딩테스트 연습 - 디스크 컨트롤러 | 프로그래머스 (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)

최단경로를 풀 때 가장 먼저 등장하는것이 Dijkstra와 Floyd라고 생각된다.
다익스트라의경우 일반적으로 O(n^2)이지만, Heap구조를 사용하는 순간 O(NlogN)의 시간복잡도로 줄일 수 있으며,
플로이드의 경우 아주간단하게 빼박 O(n^3)이다.

먼저 다익스트라부터 본다면
graph를 만들어 놓고 시작하자.

나는 주로 파이썬의 딕셔너리를 활용해서 graph를 만들고 시작한다.

def mkgraph(ss):
    from collections import defaultdict
    dic=defaultdict(list)
    for fr,to,cost in ss:
        dic[fr].append([to,cost])
        dic[to]
    return dic
costs=[
    [1,2,2],[1,4,1],[1,3,5],[2,3,3],[2,4,2],[3,2,3],[3,6,5],[4,3,3],[4,5,1],[5,3,1],[5,6,2]
]
# dijkstra(mkgraph(costs),1)
mkgraph(costs)

이렇게 하는것이 한눈에 가독성도 좋다고 생각되기에.. 이렇게 한다..
양방향 그래프가 아닌경우 dic[to] 만을 통해서 node가 비어있지 않도록 한다. (순회 시 참조에서 Key가 없는 오류발생을 막기위함)
양방향이라면 dic[to].append([fr,cost]) 를 통해서 양방향으로 만들어준다.

일단 이렇게 그래프만드는것이 끝났으니, 이제 다익스트라를 구현해보자.

from heapq import *
def dijkstra(graph,start):
    INF = int(1e9)
    distances={i : INF for i in graph}
    frt={i:0 for i in graph}
    distances[start]=0
    frt[start]=start
    q = [[0,start]]
    while q:
        dist,now = heappop(q)
        if dist> distances[now]: continue
        for node,n_dist in graph[now]:
            new_dist = dist+n_dist
            if new_dist<distances[node]:
                distances[node] = new_dist
                frt[node] = now
                heappush(q, [new_dist,node])
    return distances, frt

def getRoute(frtable,st,fr):
    tmp=[]
    while st!=fr:
        tmp.append(fr)
        fr=frtable[fr]
    ans=[st,]
    while tmp:
        ans.append(tmp.pop())
    return ans

graph = mkgraph(costs)
dist, frtable = dijkstra(graph,1)
getRoute(frtable,1,5) # 1,4,5 

난 다익스트라를 쓸 때 이후 경로까지 확인할 수 있도록 frt (from table) 을 사용한다.
이를 통해 각각의 노드가 어디에서 온것인지 알 수 있으며, 그것을 역으로 따라올라간다면, start까지 찾아감으로써 경로를 찾을 수 있다.

여담으로 floyd또한 다익스트라보다 쉽게 구현할 수 있는데. , . .
여기서는 graph보다 matrix를 활용하는것이 더욱 좋다..
links의 입력 방식에 따라 매트릭스를 구성하는 것은 쉬우니..

def solution(links,start,mid,end):
    def mkmat(links):
        nodecnt=set()
        for fr,t in links:
            nodecnt.add(fr)
            nodecnt.add(t)
        mat=[[int(1e9)]*len(nodecnt) for _ in range(len(nodecnt))]
        for fr,to in links:
            mat[fr-1][to-1]=1
            mat[to-1][fr-1]=1
        for i in range(len(nodecnt)):
            mat[i][i]=0
        return mat
    def floyd(mat):
        for mid in range(len(mat)):
            for fr in range(len(mat)):
                for to in range(len(mat)):
                    mat[fr][to] = min(mat[fr][to], mat[fr][mid]+mat[mid][to])
        return mat

    mat=mkmat(links)
    mat = floyd(mat)
    print(mat)

    dist= mat[start-1][mid-1] + mat[mid-1][end-1]
    return dist if dist<int(1e9) else -1

링크만 주어진 상황으로 생각하고, 링크에 등장하지 않는 노드는 없다고 가정한다면, mkmat을 통해 링크테이블을 만들고,
플로이드를 통해 각 링크를 순회하며 연산을 진행
fr, mid, to를 사용하여 보기좋게 사용할 수 있다!

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 (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])

코딩테스트 연습 - 행렬 테두리 회전하기 | 프로그래머스 (programmers.co.kr)

문제는 위 링크에서 확인하면된다.

총 두가지의 연산을 진행해야하는데, 
1. 실제 회전
2. 회전하는동안 스치는 숫자들의 최솟값

최대한 단순하게 풀기위해 시계방향으로 돌린다고 생각하고 풀었다.

#2021 Dev-matching웹백 행렬테두리 회전하기
# rows,columns,queries	result
# rows,columns,queries=6,6,[[2,2,5,4],[3,3,6,6],[5,1,6,3]]#	[8, 10, 25]
rows,columns,queries=3,3,[[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]]#	[1, 1, 5, 3]
# rows,columns,queries=100,97,[[1,1,100,97]]#	[1]
def mprint(mat):
    for m in mat:
        print(m)

def solution(rows,columns,queries):
    mat=[[1+j+(columns*i) for j in range(columns)] for i in range(rows)]
    # mprint(mat);print()
    answer=[]
    for query in queries:
        mat,miner=rot(mat,query)
        answer.append(miner)
        mprint(mat)
        print(miner)
    return answer

def rot(mat,q):
    x1,y1=q[0]-1,q[1]-1
    x2,y2=q[2]-1,q[3]-1
    print(x1,y1,x2,y2)
    tmp=mat[x1][y1]
    rt=0
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    x,y=x1,y1
    miner=mat[x1][y1]
    while True:
        nx,ny=x+dx[rt], y+dy[rt]
        if rt==0 and nx==x2 and ny<y2:
            rt=1
        elif rt==1 and nx==x2 and ny==y2:
            rt=2
        elif rt==2 and nx==x1:
            rt=3
        elif rt==3 and ny==y1:
            mat[x][y] = tmp
            break
        miner = min(miner,mat[nx][ny])
        mat[x][y]=mat[nx][ny]
        x=nx
        y=ny
    return mat, miner
solution(rows,columns,queries)

dx,dy를 통해 4방향의 회전을 구했으며, 각각 반시계방향 앞녀석의 것을 가져온다. 
rt를 통해 회전의 방향을 확인하며, 각 회전방향 중 tern이 필요한 순간을 if의 조건을 통해 나눠줬다.

참조 : python-for-coding-test/8.cpp at master · jun1116/python-for-coding-test (github.com) , 이것이 코딩테스트다

이진탐색으로 바꿔서 푸는문제이다. 

원하는 조건에 맞게 탐색을 진행해야한다는 점에서 연습을 반복해놓을 필요가 있다.

n=6
m=[19,15,10,17]
def solution(n,m):
    st=0
    end=max(m)
    ans=0
    while st<=end:
        tmp=0
        mid = (st+end)//2
        for i in m:
            tmp+=max(0,i-mid)
        if tmp<n:
            end=mid-1
        else:
            ans=mid
            st=mid+1
    return ans
solution(n,m)

#include <bits/stdc++.h>
using namespace std;
int n,m, answer;
vector<int> arr;
n=4;m=6;
answer=0;
arr={19,15,10,17};
int st=0;
int end=1e9;
while (st<=end){
    int mid = (st+end)/2;
    long long int total=0;
    
    for (int i=0; i<n; i++){
        if (arr[i]>mid){ 
            total += arr[i]-mid;
        }
    }
    if (total<m){
        end = mid-1;
    }
    else{
        answer=mid;
        st=mid+1;
    }
}
cout<<answer<<endl;

코딩테스트 연습 - 불량 사용자 | 프로그래머스 (programmers.co.kr)

상당한 고민을 하게 만들었던 문제이다..

최대한의 효율로 풀고자 노렸했었으나. 결국 마지막 관문에서 순열조합을 어찌 사용할지 고민하다가.. 결국 permutations를 사용해서 모든 경우의 수를 다 탐색하기로 변경했다..

첫번째 풀이..

import re
from collections import defaultdict
import itertools
def solution(user_id, banned_id):
    answer = 1
    bands=list(map(lambda x:x.replace('*','.'), banned_id))
    tmpdic=defaultdict(list)
    diccnt={}
    for band in bands:
        comp = re.compile(band)
        for user in user_id:
            if comp.match(user) and len(band)==len(user):
                tmpdic[band].append(user)
        if diccnt.get(band): diccnt[band]+=1
        else: diccnt[band]=1
    
    print(tmpdic)
    print(diccnt)
    for key in tmpdic.keys():
        list(itertools.combinations(tmpdic[key], diccnt[key]))
        

    return answer

# user_id, banned_id=["frodo", "fradi", "crodo", "abc123", "frodoc"],["fr*d*", "abc1**"]	#2
# user_id, banned_id=["frodo", "fradi", "crodo", "abc123", "frodoc"],["*rodo", "*rodo", "******"]	#2
user_id, banned_id=["frodo", "fradi", "crodo", "abc123", "frodoc"],["fr*d*", "*rodo", "******", "******"]	#3
solution(user_id,banned_id)

이 이후의 과정에서 막혔따.. 
문제는, 몇개의 banned_id 가 등장할 지 모르는 상황에서, 이것을 제대로 이어나가지 못하였다..

그리하여, 순열을 활용했따..

import re
import itertools
def solution(user_id, banned_id):
    # answer = 0
    permu = list(itertools.permutations(user_id, len(banned_id)))
    bands=list(map(lambda x:x.replace('*','.'), banned_id))
    comps=[]
    for band in bands:
        comps.append([len(band),re.compile(band)])
    tmp=[]
    for perm in permu:
        if check(comps,perm):
            perm = set(perm)
            if set(perm) not in tmp:
                tmp.append(perm)
    # print(tmp)
    return len(tmp)
def check(comps,perm):
    for comp, user in zip(comps,perm):
        if comp[1].match(user)==None or comp[0]!=len(user):
            return False
    return True

user_id, banned_id=["frodo", "fradi", "crodo", "abc123", "frodoc"],["fr*d*", "abc1**"]	#2
# user_id, banned_id=["frodo", "fradi", "crodo", "abc123", "frodoc"],["*rodo", "*rodo", "******"]	#2
# user_id, banned_id=["frodo", "fradi", "crodo", "abc123", "frodoc"],["fr*d*", "*rodo", "******", "******"]	#3
solution(user_id,banned_id)

링크 : 코딩테스트 연습 - [1차] 캐시 | 프로그래머스 (programmers.co.kr) , LRU Cache Algorithm 정리 :: Jins' Dev Inside (tistory.com) , [프로그래머스] 캐시 / 2018 카카오 블라인드 1차 / 파이썬 (tistory.com)

문제에 대한 설명은 링크를 참조하는것이 좋을것같다. 

일단 LRU에 대한 기본개념을알아야하는데.. 

가장 최근에 사용된 항목은 리스트의 맨 앞에 위치하고 가장 최근에 사용되지않은 항목 순서대로 리스트에서 제거된다.

LRU 알고리즘의 구현은 Linked List 를 이용한 Queue 로 이루어지고, 접근의 성능 개선을 위해 Map 을 같이 사용한다.

중요한점 ! 가장 최근에 사용한 항목은 리스트의 맨 앞에 위치하고, 큐 속에 가장 오래된녀석이 다음번의 교체대상이되는것. 

처음 문제를 풀 땐 Queue에 대해 조금 방심하고, heap을 사용해도 되지않을까? 라고 생각했었다.. 

solution함수에서는 cache를 준비하고, city별로 연산을 진행한다. 
그리하여 findNidx라는 함수를 통해서 큐내부의 프로그램 마지막 사용시간을 -1씩 업데이트하고, 원하는 city가 있다면 해당 인덱스를 저장, 해당 사용시간 0으로 초기화를 진행
이후 리스트끝까지 돌고, city인덱스 return (city 없다면 -1) 방식을 사용했다. 

그리하여 인덱스 -1이 리턴되면  cache에 연산을 진행해주고, 
[-사용시간, 도시이름] 을 담은 heap을 사용했으며, 그렇기에 heappop하면 가장 오래된 (가장작은값) 녀석이 나오고 
 인덱스 -1이 아니라면 hit처리를 하는것으로 진행. 

import heapq
def findNidx(lru, city):
    idx=-1
    for i,v in enumerate(lru):
        lru[i][0]-=1
        time,ct = v
        if ct==city:
            idx = i
            lru[i][0]=0
    return idx

def solution(cacheSize, cities):
    answer = 0
    if cacheSize:
        lru = [[0,i] for i in range(cacheSize)]
        for city_ in cities:
            city=city_.lower()
            idx = findNidx(lru,city)
            if idx == -1: # Not in Cache
                print(lru, 'NOhit', city)
                answer+=5
                heapq.heappop(lru)
                heapq.heappush(lru,[0,city])
            else: # In Cache
                print(lru, 'hit', city)
                answer+=1
        return answer
    else:
        return 5*len(cities)

어느부분에서 잘못된건지를 모르겠다.. 

캐시사이즈 0 처리와, 동일한것들만 들어오는것, 등등 몇가지 예외를 생각해봤지만.. 도저히 모르겠다..

공부해볼만한 코드 deque의 maxlen이라는 옵션을 사용했다..!

# 공부할코드
def solution(cacheSize, cities):
    import collections
    cache = collections.deque(maxlen=cacheSize)
    time = 0
    for i in cities:
        print(i,'\n',cache)
        s = i.lower()
        if s in cache:
            cache.remove(s)
            cache.append(s)
            time += 1
        else:
            cache.append(s)
            time += 5
    return time
cacheSize, cities=5,["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"]#52
solution(cacheSize, cities)