bright

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

from collections import deque

def solution(begin, target, words):

    dist = {begin: 0}
    queue = deque([begin])

    while queue:
        current = queue.popleft()

        next_words = []

        for i in words:
            diff = 0 
            for j in range(len(begin)) :
                if i[j] != current[j]:
                    diff += 1 
            
            if diff == 1 : 
                next_words.append(i)

        for next_word in next_words:
            if next_word not in dist:
                dist[next_word] = dist[current] + 1
                queue.append(next_word)

    return dist.get(target, 0)

1. 분류 : BFS 

2. 풀이 방법 

step 1) bfs 알고리즘을 구현하기 위하여 deque 를 사용한다. 

step 2 ) dist = { 단어 : 변환한 수 } 를 표현하는 딕셔너리 이다.  처음에 begin 을 넣고 deque 에도 begin 을 넣는다. 

step 3 ) current 는 지금 검증할 단어이다. 

           -> 만약 current 와 알파벳 1개 차이가 나는 단어가 있다면 next_words 배열에 넣는다.

step 4 ) next_words 가 전에 바뀌었던 단어가 아니라면, dist 와 queue 에 넣어 준다. 

=> 4 단계 까지 오게 되면 모든 단어 변환을 거친다. 

step 5 ) 만약 dist 에 target 이 있다면 ( 변환 가능함을 의미 ) 변환 한 수를 출력하고, 없다면 0 ( default ) 를 출력한다. 

+ tip )  딕셔너리의 get method 

딕셔너리.get( key[ , defualt 값 ] ) 

: 딕셔너리에 key 가 있으면 해당 key의 value를 반환하고, 없으면 default에 지정한 값을 반환한다. 

default 생략 시, 아무런 값도 ( None ) 반환하지 않는다. 

def dfs(graph, v, visited. n) : 
    tmp = 0 
    if not visited[v] :
        visited[v] = True
        for i in range( n ):
            if graph[v][i] :
                dfs(graph, i, visited)
                tmp += 1 
        
        if tmp >= 1 : return True
    return False

def solution(n, computers):

    visited = [False] * n
    answer = 0

    for i in range(n):
        if dfs(computers, i , visited, n ): 
            answer += 1 
    return answer

step 1) 전에 방문한 적 없으면 -> 방문 처리  / 방문한 적 있으면 바로 return False 

step 2 ) 나랑 연결된 것 중에 -> 방문한 것 없는지 찾기 / 방문한 적 없는 것이 하나도 없으면 return False . 

                                                                          하나라도 방문 하지 않은 것이 있으면 return True 

def solution(numbers, target):
    data = [0]
    for i in numbers:
        tmp = []
        for j in data : 
            tmp.append(j+i)
            tmp.append(j-i)
        data = tmp
    return data.count(target)

numbers 안의 값은 더해지거나 빼지거나 2가지 경우의 수를 갖는다. 

모든 numbers 에 대하여 각 경우의 수를 더해 나가면 모든 경우의 수를 가질 수 있다. 

programmers.co.kr/learn/courses/30/lessons/43165

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        while len(stack) > 0 and stack[-1] < num and k > 0:
            k -= 1
            stack.pop()
        stack.append(num)
    if k != 0:
        stack = stack[:-k]
    return ''.join(stack)

1. 분류 : 스택 / 큐 

2. 풀이 방법 

큰 수를 앞 쪽에 배치하는 문제이다. 가장 큰 수가 나올 때 까지 스택에 넣고 빼고를 반복한다. 

programmers.co.kr/learn/courses/30/lessons/42883

def solution(n):
    answer = 0
    
    dp = [0]* ( n+1 ) 
    dp[1] = 1 
    dp[2] = 2 
    
    if n < 3 : 
        answer = dp[n]
    else: 
        for i in range(3,n+1):
            dp[i] = ( dp[i-1]+ dp[i-2]  ) % 1000000007 
        answer = dp[n]  
    
    return answer

1. 분류 : 다이나믹 프로그래밍 

2. 풀이 : 

가장 기초적인 다이나믹 프로그래밍 문제이므로 잘 이해하고 넘어간다. 

왼쪽 부터 i-1 까지의 길이가 덮여 있으면, 2x1 을 채우는 경우의 수는 1가지 밖에 없다. 

왼쪽 부터 i-2 까지의 길이가 덮여 있으면 2x2 를 채우는 경우의 수는 2가지이지만, 모두 세로인 경우는 위의 방식에서도 count 되므로 가로로 채우는 경우의 수 1가지 라고 할 수 있다. 

따라서 점화식은 An = An-2 + An-1 이 된다. 

3. 유의사항 :

수가 아주 커질 수 있으므로  % 1000000007  처리를 어디서 하느냐에 따라서 효율성 문제가 걸릴 수 있다. 

나누기 연산한 값은 항상 동일하므로 dp 리스트 안에 넣는 과정에서 나눠 주자 

( answer 에 넣을 때 나누거나 return 할 때 나누면 효율성부분 점수 받기가 어렵다 )