13주차 알고리즘

크레인 인형뽑기 게임

[제한사항]
board 배열은 2차원 배열로 크기는 "5 x 5" 이상 "30 x 30" 이하입니다.
board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
0은 빈 칸을 나타냅니다.
1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
moves 배열의 크기는 1 이상 1,000 이하입니다.
moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

Java

import java.util.Stack;

class Solution {
    public static int solution(int[][] board, int[] moves) {
        Stack <Integer> basket =  new Stack<>();
        int result=0;
        for (int i = 0; i < moves.length; i++) {
            for (int []box : board) {
                if (box[moves[i]-1]> 0){
                    basket.push(box[moves[i]-1]);//stack에 저장
                    box[moves[i]-1] = 0;// 빈공간
                    while (basket.size()>1 && basket.peek() == basket.get(basket.size()-2)) {//basket의 크기가 1보다 커야된다.(예외처리) and peek값이랑 peek뒤에 있는 값과 같아야 된다.
                        basket.pop();
                        basket.pop();
                        result+=2 ;
                    }
                    break; //foreach 나가기       
               	}
            }        
        } 
   	 return result;
    }
}

덧칠하기

Java

public class Solution {
    public int solution(int n, int m, int[] section) {
        int roller = section[0];// roller의 값은  section[0]이다.
        int cnt = 1;// 최소 cnt는 1이다.
        for(int i = 1; i < section.length; i++) {// 
            if(roller + m - 1 < section[i]) {//roller의값 + roller의 길이가 다음 section의 보다 작으면  즉, roller길이가 짧다는 뜻
                cnt++;// cnt를 증가시키고
                roller = section[i];// 다음 section부터 roller를 시작해준다.
            }
        }
        return cnt;
    }
}

Javascript

function solution(n, m, section=[]) {
    let cnt =1;
    let roller =section[0];
    for (let index = 1; index < section.length; index++) {
        if (roller+m-1 <section[index]) {
            ++cnt;
            roller = section[index];    
        }
        
    }
    
    return cnt;
}

Javascript

function solution(k, score=[]) {
    let table = [];
    let result = []
    score.forEach((element,i) => {
        if (i<k) {
            table.push(element)
            table.sort((a,b)=>b-a);// 내림차순 정렬
        }
        else if(element>table[table.length-1]){//내림차순이기때문에 마지막 값이 가장 작다.
            table[table.length-1] = element;// table에서 가장 작은 값을 element로 바꿔 준다
            table.sort((a,b)=>b-a);// 내림차순 정렬
            
        }
        result.push(table[table.length-1]);// 가장 작은 값 result에 push
    });
   
    return result;// result 리턴
}

Java

import java.util.PriorityQueue;
import java.util.Queue;
class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
    
        Queue<Integer> queue = new PriorityQueue<>();// 기본적으로 우선순위 큐는 오름 차순으로 peak 되어있다.
        
        for(int i = 0; i < score.length; i++) {

            queue.add(score[i]);
            if (queue.size() > k) {// 큐의 크기가 k보다  커지면 peek값을 삭제 즉, 기존 peek값 보다 커야지  queue에 저장이된다.그렇지 않으면 새로 넣은 값이 peek값이 되서 삭제가된다.
                queue.poll();// 
            }

            answer[i] = queue.peek();//가장 작은 값 저장 
        }

        

        return answer;
    }
}