[LV.3] 연습문제 > 카드 뭉치

문제

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

프로그래머스

---

문제 설명

• 단어가 순서대로 적힌 두 카드 뭉치 cards1, cards2가 주어진다.
• 각 카드 뭉치에서 순서대로 한 장씩만 사용 가능하며, 건너뛰거나 순서를 바꿀 수 없다.
• 이 카드들을 이용해 주어진 goal 배열을 만들 수 있는지 확인하는 문제
  • 만들 수 있으면 "Yes", 없으면 "No"를 반환
• 제한사항
  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의 문자열들은 모두 알파벳 소문자로만 이루어져 있다.

---

정답 코드

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

---

1. goal의 단어를 왼쪽부터 하나씩 살핀다.
2. 현재 단어가 cards1의 첫 번째와 같으면 → cards1에서 꺼냄
3. 아니면 cards2의 첫 번째와 같으면 → cards2에서 꺼냄
4. 둘 다 아니면 규칙을 어기게 되므로 "No"
5. 끝까지 성공적으로 진행되면 "Yes"

---

---

개선된 코드

pop(0) 대신 인덱스 추적으로 리스트 변경 없이 시간복잡도 O(n)으로 효율적으로 처리

def solution(cards1, cards2, goal):
    i, j = 0, 0  # cards1과 cards2에서 현재 확인할 단어의 인덱스
    for word in goal:
        # goal의 현재 단어가 cards1의 i번째 단어와 같으면 i 증가
        if i < len(cards1) and word == cards1[i]:
            i += 1
        # 그렇지 않고 goal의 현재 단어가 cards2의 j번째 단어와 같으면 j 증가
        elif j < len(cards2) and word == cards2[j]:
            j += 1
        # 위 두 경우 모두 아니라면 goal 단어를 cards1, cards2에서 순서대로 뽑아 만들 수 없음
        else:
            return "No"
    # 모든 단어를 문제 없이 뽑았다면 "Yes" 반환
    return "Yes"

---

첫 번째 시도 ( 반 정답. 출제 의도 파악하기)

def solution(cards1, cards2, goal):
    
    for i in range(len(cards2)):
        cards1.insert(i+1, cards2[i])
    
    if cards1 == goal:
        return "Yes"
    else:
        return "No"

---

문법 상 오류는 없지만, 잘못된 문제 접근 (문제의 핵심 규칙 위반)

• 카드 뭉치에서 단어는 앞에서부터 하나씩만 사용할 수 있다.
• 즉, cards1이나 cards2의 순서를 절대 바꾸거나 삽입하거나 건너뛰면 안 된다.
• 하지만 이 코드는 cards2의 단어를 cards1에 강제로 insert() 하여 goal과 같아지게 만들려고 하는 코드

→ goal을 순서대로 따라가며 두 카드 뭉치 단어와 일치하는지 확인하기