99클럽(3기) - 코테스터디 3일차 TIL # 정렬

프로그래머스 - 카드 뭉치

1. 문제 설명

문자열로 이루어진 배열 cards1, cards2와 원하는 단어 배열 goal이 파라미터로 주어질 때, cards1과 cards2에 적힌 단어들로 goal을 만들 수 있다면 "Yes", 만들 수 없다면 "No"를 반환해야 한다. 

 

2.  제한 사항

• 1 <= cards1의 길이, cards2의 길이 <= 10
  • 1 <= cards1[i]의 길이, cards[i]의 길이 <= 10
  • cards1과 cards2에는 서로 다른 단어만 존재함

 

• 2 <= goal의 길이 <= cards1의 길이 + cards2의 길이
  • 1 <= goal[i]의 길이 <= 10
  • goal의 원소는 cards1과 cards2의원소들로만 구성됨

 

• cards1, cards2, goal의 문자열들은 모두 알파벳 소문자로만 구성됨

 

3. 입출력 예

 

---

 

4. 나의 풀이

1) cards1과 cards2의 인덱스를 추적하기 위한 변수 할당

cards1의 인덱스를 추적할 idx1, cards2의 인덱스를 추적할 idx2를 각각 0으로 초기화한다.

 

2) goal을 구성하는 단어들을 순회하며 순서에 맞는 단어가 cards1 또는 cards2에 없으면 "No" 반환, 문제 없이 순회가 끝나면 "Yes" 반환

cards1와 cards2 둘 중 하나가 goal의 요소와 일치하면 된다. 둘 다 일치하지 않는 경우에는 바로 "No"를 반환하면 된다. 만약 goal의 모든 요소를 순회할 때까지 "No"를 반환하지 않은 상태이면 cards1과 cards2로 goal을 만들 수있는 경우이니 for 문을 빠져나온 뒤 "Yes"를 반환한다. 

def solution(cards1, cards2, goal):
    idx1 = 0
    idx2 = 0
    
    for i in goal:    
        if idx1 < len(cards1) and cards1[idx1] == i:
            idx1 += 1
        elif idx2 < len(cards2) and cards2[idx2] == i:
            idx2 += 1
        else:
            return "No"
        
    return "Yes"

 

 

5. 다른 사람의 풀이

리스트 대신에 deque을 사용하는 방법도 있다. 이렇게 되면 시간복잡도가 O(n)에서 O(1)로 줄어든다 .  

from collections import dequeue

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

 

 

6. 새롭게 알게 된 점

Deque은 Double-ended Queue의 약자로, 내부적으로 Double-linked list로 구현되어있어서 양 끝의 요소에 대한 추가/삭제 시간복잡도가 O(1)이다. list처럼 모든 요소를 순회할 필요 없이 head 포인터로 맨 첫 번째 요소에, tail 포인터로 맨 마지막 요소에 바로 접근이 가능하기 때문이다. 구현도 구현이지만 시간복잡도를 줄일 수 있는 방법에 대해서 많이 알고 있어야겠다는 점을 다시 한 번 느낀다.