시뮬레이션과 투포인터

🗓️ 2023-01-16(월) ~ 2023-01-22(일)
KOALA 9기 코딩테스트반

🔍 시뮬레이션

---

시뮬레이션은 주어진 문제 상황을 그대로 구현하면 되는 문제이다.
대부분 2차원 공간을 다루는 행렬(Matrix) 문제가 나온다.

🪄 프렌즈4블록

function solution(m, n, board) {
    board = board.map(s => s.split(''));

    while (true) {
        const find = [];
    
        // 찾기
        for (let y = 0; y < m - 1; y++) {
            for (let x = 0; x < n - 1; x++) {
                if (
                    board[y][x] &&
                    board[y][x] === board[y][x+1] &&
                    board[y][x] === board[y+1][x] &&
                    board[y][x] === board[y+1][x+1]
                ) {
                    find.push([y, x]);
                }
            }
        }

        // 끝내기
        if (!find.length) return [].concat(...board).filter(s => !s).length;

        // 부수기
        find.forEach(([y, x]) => {
            board[y][x] = 0;
            board[y][x+1] = 0;
            board[y+1][x] = 0;
            board[y+1][x+1] = 0;
        });

        // 정렬하기
        for (let y = m - 1; y >= 0; y--) {
            for (let x = 0; x < n; x++) {
                for (let i = y - 1; i >= 0; i--) {
                    if (board[y][x]) break;
                    if (board[i][x]) {
                        board[y][x] = board[i][x];
                        board[i][x] = 0;
                        break;
                    }
                }
            }
        }
    }
}

🔍 투포인터

---

투포인터는 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘이다.

🔐 문제를 풀 때
1. 빠른 포인터와 느린 포인터가 같은 방향으로 이동
2. 양 끝에서 시작하는 포인터가 서로의 방향으로 이동

💬 적용 가능한 키워드
연속 부분 수열, 순서를 지키며 차례대로, 곱의 최소, 부분합

🪄 구명보트

function solution(people, limit) {
    let answer = 0;
    people = people.sort((a, b) => b - a);
    
    for(let i = 0, j = people.length-1; i <= j; i++, answer++){
        if (people[i] + people[j] <= limit) j--;    
    }
    
    return answer;
}