bright

# 효율성 tets 다 탈락

def solution(stones, k):
    
    answer = 0  #건널 수 있는 최대 수 
    cnt = 0 
    cross = True
    
    while cross:   
        for i in range( len(stones) ):
            if stones[i] != 0 : 
                cnt = 0 
                stones[i] -= 1
            elif stones[i] == 0 :
                cnt += 1 
                if cnt >= k : 
                    cross = False 
                    break 
        if cross:
            answer += 1 
    
    return answer

# 정답

def check(mid, stones, k):
    ck = 0
    for i in stones:
        if i - mid <= 0:
            ck += 1
        else:
            ck = 0
        if ck >= k:
            return True
    return False

def solution(stones, k):
    answer = 0
    MIN, MAX = 1, 200000000
    while MIN < MAX-1:
        mid = (MIN + MAX) // 2
        if check(mid, stones, k):
            MAX = mid
        else:
            MIN = mid
    return MAX

ㅜㅜ  갈 길이 멀다

Input = [ [1,3] , [4,3], [4,10] ] 

def solution(v):
    
    tmp = dict()
    
    for i in v : 
        if i[0] in tmp:
            tmp[i[0]].append(i[1])
        else:
            tmp[i[0]]=[i[1]]
            
    k = list( tmp.keys() ) 
    
    if len( tmp[k[0]]) > len( tmp[k[1]]) : 
        answer= [k[1]]
        for i in tmp[k[0]] :
            if i not in tmp[k[1]]:
                answer.append( i )
    else:
        answer= [k[0]]
        for i in tmp[k[1]] :
            if i not in tmp[k[0]]:
                answer.append( i )

    return answer

def solution(phone_book):
    phone_book.sort() 
    
    answer = True
    
    for p in range( len(phone_book)-1 ) : 
        for i in phone_book[p+1:]:
            if phone_book[p] == i[:len( phone_book[p])] :
                answer = False 
                return answer 
    
    return answer

길이가 짧은 번호가 길이가 긴 번호의 접두사로 들어갈 수 있다. 

따라서 sort 해 준 뒤, 앞에서 부터 접두사로 들어가 있는지 확인한다. 

하나라도 나오면 바로 False 를 return 하고 없으면 이중 for 문이 끝난 뒤, True 를 리턴한다. 

from collections import deque 


def solution(priorities, location):
    
    queue = deque()
    for i in range( len(priorities) ):
        queue.append( [ priorities[i], i ] )
        
    answer = [] 
        
    while queue: 
        n = queue.popleft() 
        
        for q in queue: 
            if n[0] < q[0] :
                queue.append(n)
                n = []
                break 
        
        if n : 
            answer.append( n[1] )
            
    return answer.index(location) +1 

location은 index와 동일하다. 

step 1 ) queue 자료 구조를 사용하기 위해서 deque 정의 

step 2 ) 맨 처음 대기목록에서의 순서를 사용해서 return 값에 적용할 것이므로 우선순위와 location 을 리스트로 묶어 deque에 저장

step 3 ) 문제에 주어진 대로 구현, 나보다 우선순위가 높은 값이 뒤에 있으면 빼서 큐 맨 뒤로 보내고

             없으면 answer 배열에 넣음 

step 4 ) 처음에 입력받은 location 이 answer 의 어느 위치에 있는지 출력한다. 단, 출력 순위는 1 부터 시작하므로 +1 해준다. 

def solution(prices):
    answer = [0]* len(prices)
    
    for i in range( len(prices)-1 ):
        cnt = 1
        for j in range( i+1, len(prices) ):
            if prices[i] > prices[j] : 
                answer[i] = j -i 
                break 
        
        if answer[i] == 0 : 
            answer[i] = len(prices) - i -1
            
    return answer

def solution(s):
    
    tmp = list( map(int,s.split(' ')) )
    tmp.sort()

    answer = str(tmp[0])+' '+str(tmp[-1])
    return answer

# 효율성 만족 x  정확성은 만족 

def solution(people, limit):
    answer = 0

    people.sort()
    
    while people:
        total = people.pop(0) 
        answer += 1 
        
        if len(people) >= 1 : 
            for i in range(len(people)-1, -1, -1 ):
                if total+ people[i] <= limit : 
                    people.pop(i)
                    break     
    return answer

# 효율성, 정확성 둘 다 만족

def solution(people, limit) :
    answer = 0
    people.sort()

    start = 0
    end = len(people) - 1
    while start < end :
        if people[end] + people[start] <= limit :
            start += 1
            answer += 1
        end -= 1
    return len(people) - answer

정렬한 다음, 작은 것과 큰 것을 묶어 태우기 위해서 투포인터를 사용한다. 

answer 에 묶어 보낼 수 있는 경우를 세서 저장한다. 

만약 가장 작은 값이랑 가장 큰 값을 더해서 limit 보다 크다면, 가장 큰 값을 하나 감소한다. 

list 의 remove, del 등의 연산은 index를 하나씩 수정해야 하므로 최대 O(n) 의 시간이 필요하다. 

효율성을 위해서 지우지 않고, 위와 같은 방식으로 index를 조정하여 사용하는 방법을 생각할 필요가 있다. 

import copy

def solution(n, lost, reserve):
    
    lost.sort()
    reserve.sort()
    
    tmp_lost = copy.deepcopy(lost)
    tmp_reserve = copy.deepcopy(reserve)
    
    for i in lost:
        for j in reserve:
            if i == j : 
                tmp_lost.remove(i)
                tmp_reserve.remove(j)
                
    lost = tmp_lost
    reserve = tmp_reserve 
    
    answer = n - len(lost) 
    
    for i in lost: 
        if i-1 in reserve :
            answer += 1 
            reserve.remove(i-1)
        elif i+1 in reserve:
            answer += 1 
            reserve.remove(i+1)
    
    return answer

쉬워보이는데 오류가 생각보다 많이 난다. 

내가 수정한 내용은 아래와 같다. 

1. lost 정렬하기 ( greedy 니까 작은 수 부터 정렬해서 앞 사람한테 먼저 빌리고 없으면 다음사람에게 빌린다 ) 

2. 잃어버렸는데 여벌이 있는 학생 처리하기 

   - 얘네는 잃어버렸지만, 여분이 있으므로 수업에 참여할 수 있다. 

   - 하지만 빌려줄 수는 없음. 

   => lost 랑 reserve 에 모두 들어가 있는데 실제로 처리는 안되므로 빼주어야 한다. 

   - 이 때, if 문 안에서 바로 lost 랑 reserve를 remove 로 처리하면 누락 될 수 있으므로, 깊은 copy를 통해 따로 바꿀

     리스트를 마련한 다음에 나중에 대입해준다. 

3. 처음에 잃어버리지 않은 학생 수를 세는 것은 ( n - len(lost) ) 2 단계 이후에 적용한다. 

def solution(citations):
    
    citations.sort()
    L = len(citations)
    M = citations[-1]
    
    for m in range( M, -1, -1 ):
        cnt = 0 
        for i in range(L):
            if citations[i] >= m : 
                cnt += 1 
        if cnt >= m: 
            answer = m
            return answer

step 1 ) citations 오름차순으로 정렬하기 

step 2 ) 많이 인용된 논문부터 거꾸로 진행, 나보다 더 많이 인용된 것의 개수를 센다.   

           -> 여기서 정렬인 것을 이용하면 더 간단하게 코드를 짤 수 있을 듯 하다

# 다른 사람 풀이 

def solution(citations):
    citations = sorted(citations)
    l = len(citations)
    for i in range(l):
        if citations[i] >= l-i:
            return l-i
    return 0

def solution(array, commands):
    
    answer = []
    
    for data in commands:
        i = data[0]
        j = data[1]
        k = data[2]
        
        tmp = array[i-1:j]
        tmp.sort()
        
        answer.append(tmp[k-1])
        
    return answer