[프로그래머스 lv.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의 문자열들은 모두 알파벳 소문자로만 이루어져 있습니다.

 

예전 풀이

생각

無

 

코드

無

 

다시 생각해보기

생각

cards1과 cards2를 동시에 순회(?)하면서 요소들을 검사

(혹은 [0]을 계속 검사..?)

이 안에서 goald의 요소들을 for문을 돌면서

goal의 j번째 요소와 같은 것이 있는지 확인하고

만약 같은 것이 있다면 해당 리스트에서 그 요소를 삭제 후 다음 j로 넘어가서 검사

만약 양쪽 다 같은 것이 없다면 No를 반환

 

코드

1차 시도

def solution(cards1, cards2, goal):
    answer = ''
    for j in goal:
        if cards1[0] == j:
            del cards1[0]
        elif cards2[0] == j:
            del cards2[0]
        else:
            return "No"
            break

        if len(cards1) == 0 and len(cards2) == 0:
            return "Yes"

- goal에 대해서만 순회를 하면 될 것 같아서 딱히 while이나 for을 더 쓰지 않고 goal에 대해서 한 번만 사용

- 순서를 건너 뛸 수 없고 이미 사용된 카드는 사용할 수 없어서 del해주기 때문에 계속 맨 앞 요소인 [0]를 검사

- cards1과 cards2의 길이가 0이라는 것은 모든 것이 순서대로 goal과 일치한다는 것이기 때문에 Yes를 반환

- 그런데 코드 실행에서 하나는 통과했는데 하나는   IndexError: list index out of range  에러가 남

- 리스트가 이미 모두 비워져서 0이라는 인덱스조차 없어서 그런 것 같음

- 안쪽에 또 조건문을...?

- 어차피 cards1에서 검사 했는데 cards2로 와서 비어있다고 에러가 나는건 No를 반환해야하는 경우이므로 elif 안에만 조건문을 하나 추가해주면 될 것 같다

 

2차 시도

def solution(cards1, cards2, goal):
    # answer = ''
    for j in goal:
        if len(cards1) != 0:
            if cards1[0] == j:
                del cards1[0]
        elif len(cards2) != 0:
            if cards2[0] == j:
                del cards2[0]

    if len(cards1) == 0 and len(cards2) == 0:
        return "Yes"
    else:
        return "No"
            
#     return answer

- return이 나오는 조건을 모두  for문 밖으로 빼고 for문 안에서는 조건에 해당할 경우 삭제만 진행하도록

- 그나마 좀 더 맞아서 64점이 되었지만 통과는 못 했다

 

다른 사람 풀이

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

코드 스스로 해석하고 이해하기

- goal의 요소들을 하나씩 돌면서 

- 만약 cards1가 빈 리스트가 아니고 (리스트 값이 존재하는 경우 True가 되므로 리스트명만 넣은 것) 이때 i가 0번째 요소와 같다면

- cards1에서 0번째 요소를 pop한다

- cards2에 대해서도 마찬가지

- 만약 cards1과 cards2 모두에 같은 것이 없다면 No를 반환하고

- 이 모든 과정을 다 거치면 Yes를 반환한다

 

근데 진짜 솔직히 말하면 내 코드랑 무슨 차인지 잘 모르겠다...

혹시나 하고 No반환하는 else 코드를 다시 for문 안에 넣어서도 돌려봤는데 결과는 똑같다

 

 

from collections import deque

def solution2(cards1, cards2, goal):
    cards1 = deque(cards1)
    cards2 = deque(cards2)
    
    for word in goal:
        if card1 and word == cards1[0]: cards1.popleft()
        if card2 and word == cards2[0]: cards2.popleft()
        else: return 'No'
    
    return 'Yes'

코드 스스로 해석하고 이해하기

** deque ** (디큐인 줄 알았는데 덱이었음)
- collections모듈의 deque(double-ended-queue)
- 양쪽 끝에서 빠르게 추가와 제거가 가능한 데이터 구조
- 리스트와 유사 but 양쪽 끝에서의 연산이 훨씬 빠름
     - 리스트는 앞쪽에 아이템을 추가하거나 제거하려면 모든 요소들을 한 칸씩 이동시켜야함
     - deque는 양 끝의 추가와 제거가 매우 빠름
- append(x): 오른쪽 끝에 x를 추가
- appendleft(x): 왼쪽 끝에 x를 추가
- pop(): 오른쪽 끝의 요소를 제거하고 반환
- popleft(): 왼쪽 끝의 요소를 제거하고 반환

- cards1과 cards2를 deque 객체로 변환하여 초기화한다

      - popleft() 메소드를 통해 덱의 왼쪽 첫 번째 요소를 효율적으로 제거하기 위함

- goal의 요소들을 돌면서

- cards1이 비어 있지 않고 그 첫 번째 요소가 현재의 word와 동일할 때 해당 요소를 제거한다

- cards2에 대해서도 마찬가지

- 위 두 조건문 중 어느 것도 충족되지 않았을 때 No를 반환한다

     - 현재의 word가 cards1과 cards2 양쪽 덱의 첫 번째 요소와 모두 일치하지 않으면 No를 반환

- 끝까지 모든 조건에 대해 참이었다면 Yes를 반환