Greedy

<프로그래머스 고득점kit>

<체육복>

	def solution(n, lost, reserve):
    list=[1 for i in range(n)]
    #모두가 체육복을 가지고 있다고 가정
    reserve.sort();
	#=>여분의 체육복을 가진 학생을 한방향으로 하도록 설정
    for v in lost:
        list[v-1]=0;
    #=>잃어버린 학생들의 정보를 0으로 최신화
    for v in reserve:
        if(v in lost):
            list[v-1]=1;
            continue;
            #여분의 체육복이있으면서 잃어버린학생에 속하면 아무것도 못하기에 바로 continue
        if((v-2>=0) and (list[v-2]==0)):
            list[v-2]=1;
            continue;
            #자신의 왼쪽학생이 없다면 나눠준다
        if((v<n) and (list[v]==0)):
            list[v]=1;
            #자신의 오른쪽학생이 없다면 나눠준다
	//
    answer = list.count(1);
    //
    return answer

<해설>

잃어버린 학생의 입장에서 번호순대로 살펴보았을 때 단방향으로 일정하게 살피면(왼쪽오른쪽,왼쪽오른쪽...)최대한 겹치지 않고 나눠줄 수 있게된다.

<예외케이스>lost까지 업데이트한 list가 [1,0,1,0]인 경우 reserve=[3,1]이었을때 각각 3번학생과 1번학생의 왼쪽학생부터 검사 후 오른쪽학생을 검사하면 result=[1,1,1,0]이므로 최적의 결과인 [1,1,1,1]이 아니게된다.

<조이스틱>

def solution(name):
    string=name
    result=[]   
    for i in string:
        if(i<'N'):
            result.append(ord(i)-ord('A'))
        else:
            result.append(ord('Z')-ord(i)+1)
    #현재 result안에는 이름에대한 위 또는 아래로 조절해야할 횟수가 들어있다.
    count=0 
    idx=0
    #시작인덱스와 총조작할 횟수를 저장할 count
    result2=result.copy()
    while(True):
        count+=result[idx]
        result[idx]=0
        if(sum(result)==0):
            break
        #현재위치에서 위아래조작할횟수를 더하고 끝인지 확인
        left=1
        right=1
        #왼쪽,오른쪽시작위치설정
        while(result[idx+right]==0):
            right+=1
        while(result[idx-left]==0):
            left+=1
         	#A가아닌 왼쪽거리와 오른쪽거리
        if(left<right):
            idx-=left
            count+=left
        else:
            idx+=right
            count+=right
           	#더 짧은 거리로 이동
    count2=0
    idx=0
    count2+=result2[idx]
    result2[idx]=0
    if(sum(result2)==0):
        return count2;
    left=1
    right=1
    while(result2[idx+right]==0):
        right+=1
    while(result2[idx-left]==0):
        left+=1
    if(left<right):
        idx+=right
        count2+=right
    else:
        idx-=left
        count2+=left
    #AABAAAAAAABBB에대한 예외처리
    while(True):
        count2+=result2[idx]
        result2[idx]=0
        if(sum(result2)==0):
            break
        left=1
        right=1
        while(result2[idx+right]==0):
            right+=1
        while(result2[idx-left]==0):
            left+=1
        if(left<right):
            idx-=left
            count2+=left
        else:
            idx+=right
            count2+=right
    return min(count,count2)

<해설>

AAAABB가 있을때 기본적으로 위아래의 총 조작횟수는 어느방향으로 가나 같으므로 이동동선에 따라 결과가 달라진다.
이때 설정해야할 문자가 A라면 그곳을 거치지 않고서 설정이 가능하므로 최대한 변경해야할 문자가 남아있는 곳 까지의 거리가 짧은 방향으로 이동을 해야한다.

<예외케이스>AABAAAAAAABBB같은 경우 위의 구현을 통해 살펴보면

AABAAAAAAABBB
0                 321
                    45
678

위는 오른쪽으로 먼저 이동하여 조작하는데 실제로는 왼쪽으로 먼저 이동해야 최적의 이동횟수가 나온다.

<큰 수 만들기>

def solution(number, k):
    answer = []
    #정답을 저장할 문자열생성
    for num in number:
        while answer and k > 0 and answer[-1] < num:
            answer.pop()
            k -= 1
            #스택은 항상 앞자리를 최우선으로 최신화해야하기에 answer[-1]로 스택의 가장 오른쪽자리부터 클때까지 계속 pop수행,이때 k>0으로 삭제할 기회가 있을 경우에만으로 조건을 걸어둔다.
        answer.append(num)
    answer = ''.join(answer[:len(number)-k])
    #11111이나 99999인경우 스택은 그대로 쌓이기때문에 k만큼 빼서 추출
    return answer	

<해설>

기본적으로 큰 수를 만들기 위해서는 삭제할 기회 k개가 있을때 주어진 기회안에 앞자리를 우선으로 큰수를 채워나가야한다.
277924,3=>스택에 차례로 2(2)->7->77->79(1)->9(0)->924
(괄호는 남은기회를 의미)

<구명보트>

def solution(people, limit):
    people.sort()
    #가장 작은 것과 가장 큰것을 쉽게 구분하기위해 오름차순정렬
    left=0
    right=len(people)-1
    count=0
    #같이묶을사람의 순서와 보트의 갯수를 초기화
    while(left<=right):
        if(people[left]+people[right]<=limit):
            left+=1
            right-=1
            #서로 반대인 사람을 같이묶을때 여유롭다면 같이태우고 다음으로 태울사람 두명을 최신화
        else:
            right-=1
            #초과한다면 가장큰 사람은 혼자태워보내고 한단계적은 사람을 최신화
        count+=1
    if(left==right):
        count+=1
    return count

<해설>

예시로 [40,50,50,60,75,80,85,90]이 있을때 limit을 150이라 한다면 왼쪽의 작은 그룹끼리 묶어서 한보트에 태우는 것보단 가장작은 것과 가장큰 것을 묶어가면서 보트에 태우는 것이 적게 나온다.만약 둘이 limit을 초과한다면 가장큰것은 혼자태우고 가장큰것보다 한단계 적은것을 같이태워보면서 최소한의 보트를 탐색한다.