그리디_회의실 배정, 씨름선수, 창고 정리, 침몰하는 타이타닉, 증가순열만들기, 역수열

 

 

그리디는 탐욕적인 이라는 의미로 

지금 현재 가장 최적의 것을 계속 골르는 것이다. 

주로 정렬과 함께 한다. 

 

 

회의실 배정 코드 : 

if __name__=="__main__" :
    n = int(input())
    meeting = [list(map(int,input().split())) for _ in range(n)]        
    meeting.sort(key = lambda x : (x[1],x[0]))
    
    endTime,cnt = 0,0
    for s,e in meeting :
        if s >= endTime :
            cnt +=1 
            endTime = e 
    print(cnt)

=> 끝나는 시간을 오름차순으로 정렬한 후

시작시간이 이전 회의의 끝나는 시간보다 늦거나 같으면 해당 회의를 넣는다.

 

 

 

 

 

씨름 선수 코드 : 

if __name__=="__main__" :
    n = int(input())
    person = [list(map(int,input().split())) for _ in range(n)]        
    # 키가 큰 순으로 정렬 
    person.sort(key = lambda x : x[0],reverse= True)
    
    
    weight,cnt = 0,0
    for h,w in person :
        if weight < w :
            cnt +=1 
            weight = w  
    print(cnt)

-> 키가 큰 순으로 정렬한다. 

-> person을 돌면서 키는 무조건 앞에 사람보다 작으니까 무게를 비교하며 지원자의 수를 구한다. 

만약 앞에 지원자의 무게보다 내가 작다면 나는 키 , 몸무게 둘 중 무엇도 이기지 못한것이기 때문이다. 

 

 

 

 

창고 정리 코드 : 

 

<내 코드 > 

if __name__=="__main__" :
    n = int(input())
    ch = list(map(int,input().split()))
    m = int(input())
    
    for _ in range(m) :
        ch[ch.index(max(ch))] -=1 
        ch[ch.index(min(ch))] += 1 
    print(max(ch) - min(ch))

 

 

< 선생님 풀이>

if __name__=="__main__" :
    n = int(input())
    ch = list(map(int,input().split()))
    m = int(input())
    ch.sort()
    
    for _ in range(m) :
        ch[0] +=1 
        ch[n-1] -=1 
        ch.sort()
    print(ch[n-1] - ch[0])

 

 

아...정렬이 있었구나,,,

 

 

 

 

 

침몰하는 타이타닉 코드 : 

 

if __name__=="__main__" :
    n,m = map(int,input().split())
    person = list(map(int,input().split()))
    
    person.sort()
    
    cnt = 0 
    while person :
        if len(person) == 1 : 
            cnt +=1 
            break
        if person[0]+person[-1] <= m :
            cnt +=1 
            person.pop(0)
            person.pop()
        else :
            cnt +=1 
            person.pop()
    print(cnt)

 

리스트는 pop(0)을 하면 나머지 값들이 한칸씩 앞으로 가는 연산을 한다.  -> 비효율적 

덱이 빠르다.  덱은 그저 포인터 변수만 옮기면 되기 때문에

 

person을 deque으로 바꿔주고 pop(0)를 popleft()로 바꾸면 된다. 

 

 

 

 

 

 

 

증가  수열 만들기 코드 : 

if __name__=="__main__" :
    n = int(input())
    num = list(map(int,input().split()))
    
    endNum, start,end = 0, 0,n-1
    ans = ""
    tmp_num = []
    while start <= end :
        if num[start] > endNum : tmp_num.append([num[start],'L'])
        if num[end] > endNum : tmp_num.append([num[end],'R'])
        tmp_num.sort()
        
        if len(tmp_num) == 0: break
        else :
            ans += tmp_num[0][1]
            endNum = tmp_num[0][0]
            if tmp_num[0][1] == 'L' :
                start +=1 
            else : end -=1 
        tmp_num.clear()
        
    print(len(ans))
    print(ans)

 

이전 수열의 마지막 값보다 큰 값만을 tmp_num에 방향 (L  또는 R)을 넣는다.

그리고 정렬한다. 

 

둘 중 작은 것이 앞으로 가도록 정렬되었다. 

만약 길이가 0이라면 마지막 값보다 작은 값이 없는 거이므로 break

0이 아니라면 0번째 값을 저장하고 왼쪽에서 왔냐 오른쪽에서 왔냐에 따라 start, end 를 조정한다. 

 

 

 

역수열 코드 : 

if __name__=="__main__" :
    n = int(input())
    num = list(map(int,input().split()))
    ans = [0]*n
    
    for i in range(n) :
        for j in range(n) :
        	# 나보다 큰 친구가 들어오는 수는 이미 만족 , 그리고 내가 드러갈 수 있는 자리 찾기 
            if num[i] == 0 and ans[j] ==0 :
                ans[j] = i+1 
                break
            # 나보다 큰 친구가 들어오는 수 
            elif ans[j] ==0 :
                num[i] -=1 
    print(*ans)