21-03-22 알고리즘 문제풀기 및 노트 정리

크레인 인형뽑기 게임

stack 배열을 생성하고 인형을 차례대로 담으면서 이전에 추가한 인형(stack의 마지막값)과 같은지 비교해서 score 계산을 해 주면 된다

function solution(board, moves) {
    let stack = [];
    let score = 0;
    for(let i = 0; i < moves.length; i++) {
        let move = moves[i]-1; // x좌표를 구함 (index는 1부터 시작하므로 1을 빼줌)
        for (let j = 0; j <board.length; j++){ // board 길이만큼 돌고
            if (board[j][move] !== 0) { // 해당 좌표에 있는 인형이 0이 아니고
                if (board[j][move] === stack[stack.length-1] && stack.length > 0){
                    // 이전에 추가한 인형과 값이 같다면 stack에서 빼주고 scoring하기
                    stack.pop();
                    score += 2
                } else {
                    // 값이 다르다면 그냥 stack에 push만 하기
                    stack.push(board[j][move])
                }
                // 해당 인형은 옮겼으니 0으로 바꿔 다시 선택하지 않도록 하기
                board[j][move] = 0;
                break;
            } 
        }
    }
    return score;
}

다트 게임

해당 문제 링크

처음에 혼자 풀 때 짰던 코드
스타상이 이전 점수에도 영향을 준다는 것을 고려하지 못함

또, 10점을 고려하기 위해 같은 코드가 반복되어 지저분해보임

function solution(dartResult) {
    let answer = 0;
    let split = dartResult.split('');
    let dartScore = 0, alphabet = '', powValue = 0, starOrSharp = '';
    while (split.length > 0){
        if (split[1] === '0') {
            dartScore = split.shift() * 10;
            split.shift();
            alphabet = split.shift();
            powValue = alphabet === 'S' ? 1 : alphabet === 'D' ? 2 : 3
            if (split[0] === '*' || split[0] === '#') {
                starOrSharp = split.shift() === '*' ? 2 : -1;
            } else {
                starOrSharp = 1;
            }
            answer += Math.pow(dartScore, powValue) * starOrSharp;
        } else if (split[1] !== '0') {
            dartScore = split.shift() * 1;
            alphabet = split.shift();
            powValue = alphabet === 'S' ? 1 : alphabet === 'D' ? 2 : 3
            if (split[0] === '*' || split[0] === '#') {
                starOrSharp = split.shift() === '*' ? 2 : -1;
            } else {
                starOrSharp = 1;
            }
            answer += Math.pow(dartScore, powValue) * starOrSharp;
        }
    }
    return answer;        
}

다른분 풀이
Object로 S, D, T값을 설정해 찾아 쓰는 방식은 O(1)로 가능하므로 보고 배워야겠다는 생각을 함

스택 구조를 만들고 스택 내에 점수를 하나씩 저장해놓고 스타상이 두번째에 온다면 스택 내 값을 수정하는 방식을 미처 생각치 못함


function solution(dartResult) {
    let stack = [];
    let score = {
        S: 1,
        D: 2,
        T: 3
    }
    let count = 0;
    const len = dartResult.length;
    
    for (let i = 0; i < len; i++) {
        let isChar = dartResult.charAt(i);
        if (+isChar != isChar) {
            if(score[isChar]) {
                stack.push(Math.pow(dartResult.slice(i - count, i), score[isChar]));
                count = 0;
            } else {
                const sharpOrStar = isChar === '*' ? 2 : -1;
                const stackLen = stack.length;
                if (sharpOrStar == 2 && stackLen > 1) {
                    stack[stackLen-2] = stack[stackLen-2] * sharpOrStar;
                }
                stack[stackLen-1] = stack[stackLen-1] * sharpOrStar;
            }
        } else {
            count++;
        }
    }
    return stack.reduce((acc, cur) => acc+ cur, 0)
}

폰켓몬

해당 문제 링크

처음에 든 생각은 그냥 set에 넣고 unique한 값만 뽑으면 되는 것 아닌가? 했음
문제에서 폰켓몬은 N/2마리를 선택해야 하므로 만약에 들어오는 배열의 길이를 반으로 나눈 값이 set의 사이즈보다 작다면 단순히 배열 길이를 반으로 나눈 값을 리턴하면 될 일이었음

function solution(nums) {
    let answer = 0;
    let set = new Set ();
    for(let number of nums){
        set.add(number);
    }

    if(set.size < nums.length/2) {
        answer = set.size;
    } else { 
        answer = nums.length/2;
    }
    return answer;
}

21-03-22 알고리즘 문제풀기 및 노트 정리

크레인 인형뽑기 게임

다트 게임

폰켓몬

Harry Kim