이코테의 문자열 뒤집기. 

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)