159994. 카드 뭉치

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

코딩테스트 연습 - 카드 뭉치 | 프로그래머스 스쿨

풀이

아이디어

카드는 순서대로만 사용할 수 있다는 제약조건이 있다. 큐를 사용하면 딱이다. 각 카드 뭉치에는 서로 다른 단어만 존재하기 때문에 복잡한 로직 없이 각 카드 뭉치 가장 위의 카드만 확인해서 바로 바로 사용해주면 된다.

goal을 순회하면서 각 단어가 cards1의 맨 앞이나 cards2의 맨 앞에 있다면 해당 카드를 사용(front 인덱스를 증가)하면 된다. 만약 둘 다 아니라면 goal을 만들 수가 없으므로 "No"를 반환한다.

shift()를 사용하면 배열의 남은 요소를 모두 앞으로 이동시켜야 하기 때문에 O(N)의 시간이 더 걸린다. 그래서 front 인덱스를 관리하는 방식을 써서 O(1)로 해결했다.

코드

function solution(cards1, cards2, goal) {
    let front1 = 0;
    let front2 = 0;
    let len1 = cards1.length;
    let len2 = cards2.length;

    for (let idx = 0; idx < goal.length; idx++) {
        const target = goal[idx];
        if (front1 < len1 && cards1[front1] === target) front1++;
        else if (front2 < len2 && cards2[front2] === target) front2++;
        else return 'No';
    }

    return 'Yes';
}