[프로그래머스 1단계] 크레인 인형뽑기 게임

❓문제 설명

• 2중배열 형태의 배열 하나를 제공하는데 이걸 결국 n x n 형태로 만드는 것임
• 주어진 moves라는 배열의 순서대로 2중 배열에서 특정 수를 찾는 것임 그래서 찾은 값을 스택에 저장함
• 스택에 이전값과 추가되는 값이 같은 시 2개를 없애고 count를 올려서 최종적으로 count를 return하는 것임

 

✅ 문제 해결

• 2중 반복문에 대해 사용을 최대한 지양하고 싶어서 고민을 하다가 도저히 풀리지 않아서 풀이를 보고 해석하였음
• 기본적으로 배열 탐색이라는 키워드를 풀면서 공부를 하게 되면 자연스럽게 알고리즘을 이해할 수 있는 구조라고 한다.
• 배열에서 찾은 특정 수를 변수에 저장하고 그 수를 0으로 만드는 작업 이부분이 좀 막혔었는데 이런식으로 간단히 구현할 수 있다.

function solution(board, moves) {
    var answer = 0;
    const array1 = []
    moves.forEach((move)=> {
        const doll = pickup(board, move - 1)
        if (doll) {
            if (array1[array1.length - 1] === doll) {
                array1.pop()
                answer += 2
            } else {
            array1.push(doll)
        }
        } 
    })
    return answer;
}

function pickup(board, move) {
    for (let i = 0; i < board.length; i++) {
        if (board[i][move] !== 0) {
            const doll = board[i][move]
            board[i][move] = 0
            return doll
        }
    }
}

 

🔥 인상 깊은 남의 풀이

const transpose = matrix =>
    matrix.reduce(
        (result, row) => row.map((_, i) => [...(result[i] || []), row[i]]),
        []
    );

const solution = (board, moves) => {
    const stacks = transpose(board).map(row =>
        row.reverse().filter(el => el !== 0)
    );
    const basket = [];
    let result = 0;

    for (const move of moves) {
        const pop = stacks[move - 1].pop();
        if (!pop) continue;
        if (pop === basket[basket.length - 1]) {
            basket.pop();
            result += 2;
            continue;
        }
        basket.push(pop);
    }

    return result;
};

• 행과 열을 바꿔서 2중 반복문의 구조가 아닌 형태로 만들기에 배열의 길이가 길어지더라도 비슷한 연산속도를 낼 수 있다는 장점이 있다.
• 이렇듯 반복문의 중첩을 줄이는 코드를 보니 상당히 복잡해 보이는 형태여서 좀 더 많은 이해도를 요구하는 것 같다.

 

❕느낀점

• 좀 더 많이 풀어보면서 감을 찾아야할 것 같고 키워드별로 공부를 해나가면서 알고리즘에 대해서 학습을 해야겠다는 생각도 들었다.
• 무작정 문제만 풀 것이 아니라 공통된 키워드를 가진 문제를 중심으로 단계별로 공부하는 것도 좋을 것 같다.