99클럽 코테 스터디 11일차 TIL

문제 설명

풀이 과정 & 코드

• 먼저 어떤 리스트를 먼저 할지는 상관 없지만 반드시 순서는 지켜져야 함을 유의해야 함
• 초기에는 words 라는 empty string을 만들고 cards와 일치하는 word를 ' '과 함께 추가하고 마지막에 goal과 words.split()이 같으면 'Yes'를 return하고 아니면 'No'를 리턴하게 했지만 for loop 안에서 일어나기 때문에 결과적으로 O(n^2)의 시간복잡도를 가져서 통과하는 코드여도 비효울적인 코드였음을 깨달음
• 이후 words에 단어를 계속 추가하는 것 보다 index를 사용해서 해당하는 단어가 있으면 1씩 증가시키며 goal의 크기만큼 for loop을 돌고 나오면 'No'를 return하고 아니면 'Yes'를 return 하게 코드를 수정함

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

    return answer