99클럽 코테 스터디 11/99일차 TIL #카드 뭉치(미들러)

 

문제:카드 뭉치

출처: 프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/159994

프로그래머스

 

1. 문제 설명

코니는 영어 단어가 적힌 카드 뭉치 두 개를 선물로 받았습니다. 코니는 다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는지 알고 싶습니다.
원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다.한 번 사용한 카드는 다시 사용할 수 없습니다.카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.
예를 들어 첫 번째 카드 뭉치에 순서대로 ["i", "drink", "water"], 두 번째 카드 뭉치에 순서대로 ["want", "to"]가 적혀있을 때 ["i", "want", "to", "drink", "water"] 순서의 단어 배열을 만들려고 한다면 첫 번째 카드 뭉치에서 "i"를 사용한 후 두 번째 카드 뭉치에서 "want"와 "to"를 사용하고 첫 번째 카드뭉치에 "drink"와 "water"를 차례대로 사용하면 원하는 순서의 단어 배열을 만들 수 있습니다.
문자열로 이루어진 배열 cards1, cards2와 원하는 단어 배열 goal이 매개변수로 주어질 때, cards1과 cards2에 적힌 단어들로 goal를 만들 있다면 "Yes"를, 만들 수 없다면 "No"를 return하는 solution 함수를 완성해주세요.

제한사항

• 1 ≤ cards1의 길이, cards2의 길이 ≤ 10
  • 1 ≤ cards1[i]의 길이, cards2[i]의 길이 ≤ 10
  • cards1과 cards2에는 서로 다른 단어만 존재합니다.
• 2 ≤ goal의 길이 ≤ cards1의 길이 + cards2의 길이
  • 1 ≤ goal[i]의 길이 ≤ 10
  • goal의 원소는 cards1과 cards2의 원소들로만 이루어져 있습니다.
• cards1, cards2, goal의 문자열들은 모두 알파벳 소문자로만 이루어져 있습니다.

2. 문제 해석

간단한 que 문제이다.

제한사항 덕분에 문제가 생각보다 단순하게 풀 수 있다.

3. 문제 풀이

풀이 (1) 100/100: deque 사용

영어 단어 카드 뭉치 2개
카드에 적힌 단어들 -> 단어 배열 만들기
- 원하는 카드 뭉치에서 카드 순서대로 한 장씩
- 재사용 x
- 카드 나오면 무조건 사용
- 순서 변경x
cards1 =  ["i", "drink", "water"]
cards1 =  ["want", "to"]
goal: 원하는 문자 배열

=> que 
popleft()
word = cards1.popleft() / cards2.popleft()
sentense = []

되는지 안되는지 구분하는 방법?
case2 가 해결이 안되는 문제: 동일한 문자열이 왔을때 처리 방법?
=> cards1과 cards2에는 서로 다른 단어만 존재합니다.

이 제한사항을 확인하지 않으면 문제가 생각보다 많이 복잡해진다.

이전에 풀었던 문제임에도 불구하고 해당 제한사항을 확인하지 못해 case를 어떻게 해결하지? 하고 있었다.

재귀를 이용해서 풀어야 저 문제가 풀리겠구나 하다가 제한사항을 확인하고 다시 풀었다.

from collections import deque

def solution(cards1, cards2, goal):
    
    que1 = deque(cards1)
    que2 = deque(cards2)
    
    for word in goal:
        
        if que1 and que1[0] == word:
            que1.popleft()
        elif que2 and que2[0] == word:
            que2.popleft()
        else:
            return 'No'
        
        
    return 'Yes'

테스트 1 〉	통과 (0.00ms, 10.3MB)
테스트 2 〉	통과 (0.00ms, 10MB)
테스트 3 〉	통과 (0.00ms, 10.1MB)
테스트 4 〉	통과 (0.00ms, 10MB)
테스트 5 〉	통과 (0.00ms, 10.2MB)
테스트 6 〉	통과 (0.00ms, 10.2MB)
테스트 7 〉	통과 (0.00ms, 10.1MB)
테스트 8 〉	통과 (0.00ms, 10.1MB)
테스트 9 〉	통과 (0.00ms, 10.2MB)
테스트 10 〉	통과 (0.00ms, 10.1MB)
테스트 11 〉	통과 (0.01ms, 10.2MB)
테스트 12 〉	통과 (0.01ms, 10.1MB)
테스트 13 〉	통과 (0.00ms, 10.1MB)
테스트 14 〉	통과 (0.01ms, 10.2MB)
테스트 15 〉	통과 (0.01ms, 10.1MB)
테스트 16 〉	통과 (0.01ms, 10MB)
테스트 17 〉	통과 (0.01ms, 10.2MB)
테스트 18 〉	통과 (0.01ms, 10.1MB)
테스트 19 〉	통과 (0.01ms, 9.96MB)
테스트 20 〉	통과 (0.01ms, 10.1MB)
테스트 21 〉	통과 (0.01ms, 10.2MB)
테스트 22 〉	통과 (0.01ms, 10.1MB)
테스트 23 〉	통과 (0.01ms, 10.1MB)
테스트 24 〉	통과 (0.00ms, 10.2MB)
테스트 25 〉	통과 (0.00ms, 10.1MB)

풀이 (2) 100/100: List 자료구조 사용

def solution(cards1, cards2, goal):
    list1 = list(cards1)
    list2 = list(cards2)
    
    for word in goal:
        if list1 and list1[0] == word:
            list1.pop(0)
        elif list2 and list2[0] == word:
            list2.pop(0)
        else:
            return 'No'
    
    return 'Yes'

테스트 1 〉	통과 (0.00ms, 10.1MB)
테스트 2 〉	통과 (0.00ms, 10.2MB)
테스트 3 〉	통과 (0.00ms, 10.2MB)
테스트 4 〉	통과 (0.00ms, 10.2MB)
테스트 5 〉	통과 (0.01ms, 10.2MB)
테스트 6 〉	통과 (0.00ms, 10.1MB)
테스트 7 〉	통과 (0.00ms, 10.2MB)
테스트 8 〉	통과 (0.01ms, 10.2MB)
테스트 9 〉	통과 (0.00ms, 10.1MB)
테스트 10 〉	통과 (0.01ms, 10.4MB)
테스트 11 〉	통과 (0.01ms, 10.1MB)
테스트 12 〉	통과 (0.01ms, 10.3MB)
테스트 13 〉	통과 (0.01ms, 10.2MB)
테스트 14 〉	통과 (0.01ms, 10.4MB)
테스트 15 〉	통과 (0.01ms, 10.4MB)
테스트 16 〉	통과 (0.01ms, 10.4MB)
테스트 17 〉	통과 (0.01ms, 10.3MB)
테스트 18 〉	통과 (0.01ms, 10.2MB)
테스트 19 〉	통과 (0.01ms, 10.2MB)
테스트 20 〉	통과 (0.01ms, 10.2MB)
테스트 21 〉	통과 (0.01ms, 10.1MB)
테스트 22 〉	통과 (0.01ms, 10.1MB)
테스트 23 〉	통과 (0.01ms, 10.4MB)
테스트 24 〉	통과 (0.00ms, 10.2MB)
테스트 25 〉	통과 (0.00ms, 10.1MB)

list를 쓰면 연산속도가 느려질 줄 알았는데 왜 더 연산량이 줄어서 빨라졌지???

Chatgpt에게 물어본 답변은 다음과 같다.

---

deque는 이론적으로 list보다 특정 연산에서 더 빠릅니다. 특히 deque의 popleft() 연산은 O(1)로 상수 시간에 수행되는 반면, list의 pop(0) 연산은 O(n) 시간이 소요됩니다. 이는 list에서 첫 번째 요소를 제거할 때 모든 나머지 요소들을 한 칸씩 앞으로 이동시켜야 하기 때문입니다.

하지만 실제 테스트에서 성능 차이가 거의 없거나, list가 더 빠르게 나타나는 이유는 다음과 같은 몇 가지 요인 때문일 수 있습니다:

1. 데이터 크기: 테스트 데이터가 상대적으로 작다면 list와 deque의 성능 차이가 거의 느껴지지 않을 수 있습니다. list의 pop(0)이 O(n)이라 하더라도, n이 매우 작을 경우 그 차이가 미미할 수 있습니다.
2. 파이썬 최적화: 파이썬의 내부 구현에서 list는 매우 최적화되어 있어서, 작은 규모의 연산에서는 성능 차이가 거의 없을 수 있습니다.
3. 캐싱 및 메모리 접근: deque는 list와 다르게 이중 연결 리스트로 구현되어 있습니다. 따라서 메모리 접근 방식이 달라지며, 특정 상황에서 오히려 메모리 접근 시간이나 캐시 효율성 때문에 성능이 저하될 수 있습니다.
4. 테스트 환경: 테스트가 실행되는 환경, CPU 상태, 메모리 상태 등 다양한 외부 요인에 의해 미세한 성능 차이가 발생할 수 있습니다.

결론적으로, deque가 이론적으로는 특정 연산에서 더 효율적이지만, 테스트 환경이나 데이터 크기 등의 요인에 따라 실제 성능 차이는 작거나 list가 더 빠를 수도 있습니다. 특히 작은 데이터셋에서는 차이가 거의 없기 때문에, 코드의 간결성이나 가독성을 중시한다면 list를 사용하는 것도 실용적인 선택일 수 있습니다.

---

Test: List의 pop과 deque의 popleft 비교

그래서 좀 더 극단적인 상황을 가정해 보았다.

리스트의 크기를 100000으로 하여 list와 deque의 연산 시간을 time을 이용해 비교한다.

import time
from collections import deque

# 극단적인 테스트 데이터 생성
n = 100000  # 매우 큰 리스트 크기
cards1 = list(range(n))
cards2 = list(range(n, 2*n))
goal = cards1 + cards2  # goal은 cards1과 cards2의 모든 요소를 포함

# List 사용
start_time = time.time()

def solution_list(cards1, cards2, goal):
    list1 = list(cards1)
    list2 = list(cards2)
    
    for word in goal:
        if list1 and list1[0] == word:
            list1.pop(0)
        elif list2 and list2[0] == word:
            list2.pop(0)
        else:
            return 'No'
    
    return 'Yes'

result_list = solution_list(cards1, cards2, goal)
end_time = time.time()

print(f"List solution took {end_time - start_time:.6f} seconds.")

# Deque 사용
start_time = time.time()

def solution_deque(cards1, cards2, goal):
    que1 = deque(cards1)
    que2 = deque(cards2)
    
    for word in goal:
        if que1 and que1[0] == word:
            que1.popleft()
        elif que2 and que2[0] == word:
            que2.popleft()
        else:
            return 'No'
        
    return 'Yes'

result_deque = solution_deque(cards1, cards2, goal)
end_time = time.time()

print(f"Deque solution took {end_time - start_time:.6f} seconds.")

실험결과 list에 비해 deque가 1/9 가량 덜 걸린 것을 확인 할 수 있다.

이는 위  chatgpt 설명대로 list pop의 경우 하나를 제거하고 나머지 원소들을 재배열하는 과정이 필요하여 O(n)의 연산량이 필요하지만, deque의 경우 하나만 진짜 뽑아버리면 끝이라 O(1)의 연산량으로 빠르게 정리가 가능하기 때문이다.

 

 

4. 주요 코드 및 정리

4.1 deque 자료구조

popleft()를 이용해서 선입선출을 쉽게 할 수 있다.

list형 자료구조를 사용하게 되면 remove 또는 pop을 사용하게 된다.

해당 문제에서는 크게 다르지 않지만 아무래도 차이점은 효율성에서 다소 차이가 날 수 있으므로 deque 자료구조를 자주 사용하자