[python][프로그래머스] 짝지어 제거하기, 구명보트 (스택, 큐 문제)

1. 짝지어 제거하기 (https://school.programmers.co.kr/learn/courses/30/lessons/12973#)

(레벨 2)

 

• 처음에는 큐를 사용해 만약 짝이 지어져있지 않다면 뒤에 다시 append해주고 짝이 있는 애들 먼저 처리하는 식으로 풀었는데 그럼 문제에서는 틀렸다고 여겨지는 문제까지 맞다고 처리되기도 하고 while loop이 한도끝도 없이 돌아갈 거 같아서 질문게시판을 읽어봤다
• 알고보니 유명한 스택 문제였다 ;;
• 스택 사용 풀이는:
  1. 일단 맨 앞에 있는 char을 스택에 넣어준다
  2. 그 다음 char은 스택의 마지막 value와 비교해준다
  3. 두 알파벳이 짝이라면 스택에서 마지막 value를 pop해주고 아니라면 해당 char도 스택에 넣어준다
  4. 모든 알파벳을 탐색 할때까지 반복한다
  5. 스택이 비었다면 모든 알파벳이 짝지어져 있는 것이다

스택 사용 풀이

def solution(s):
    stack = []
    
    for char in s:
        if len(stack) == 0:
            stack.append(char)
        else:
            if stack[-1] == char:
                stack.pop()
            else:
                stack.append(char)
    
    if len(stack) == 0:
        return 1
    else:
        return 0

 

 

큐 사용 풀이 (틀림)

from collections import deque

def solution(s):
	queue = deque(s)
    ans = 1
    
    for _ in range(len(s) * 2):
        if len(queue) == 0:
            break
            
        curr = queue.popleft()
        
        if curr == queue[0]:
            ans = 1
            queue.popleft()
        else:
            ans = 0
            queue.append(curr)
   
    return ans

 

 

---

 

2. 구명보트 (https://school.programmers.co.kr/learn/courses/30/lessons/42885)

(레벨 2)

 

• 이 문제도 처음에는 dfs로 풀어봤다
• 하지만 테스트케이스에서만 통과하고 제출 후에는 통과하지 못해서 질문게시판을 읽어보던 중 이 문제는 투포인터 알고리즘이 가장 잘 맞는다는 것을 봤다
• 그래서 야매로 배워보다가 답을 찾아봤다
• 답은 꽤나 간단했다:
  1. 일단 내림차순으로 된 people 리스트를 큐로 변환시켜준 뒤, 큐의 길이가 1이 될 때까지 while loop을 돌려준다
  2. 큐의 맨 처음 숫자와 맨 마지막 숫자를 더했을 때 limit보다 작은지 확인한다
  3. 해당 condition이 맞다면 각각 popleft()와 pop()을 사용해 제거해준 뒤 카운트를 올려준다
  4. 아니라면 구명보트에는 한명만 탈 수 있다는 것이기 때문에 popleft() 후 카운트를 올려준다
  5. while loop에서 빠져나오면 큐에 남아있는 마지막 한 명도 처리해준다 (while loop을 큐가 빌 때까지 돌리지 않는 이유는 인덱스 에러가 나기 때문이다)

큐

from collections import deque

def solution(people, limit):
    queue = deque(sorted(people, reverse=True))
    count = 0
    
    while len(queue) > 1:
        if queue[0] + queue[-1] <= limit:
            queue.pop()
            queue.popleft()
            count += 1
        else:
            count += 1
            queue.popleft()
            
    if len(queue) == 1:
        count += 1
            
    return count

 

 

dfs (틀림)

def dfs(i, weight):
        print(people[i])
        visited[i] = 1
      
        for j in range(len(people)):
            if visited[j] == 0 and weight + people[j] <= limit:
                dfs(j, weight + people[j])
                
    visited = [0] * len(people)
    weight = 0
    count = 0
    for i in range(len(people)):
        if visited[i] == 0:
            weight += people[i]
            dfs(i, weight)
            count += 1
            weight = 0
            
    return count