[프로그래머스 고득점 KIT] 한장에 핵심 정리📝

김예지·2021년 10월 30일
0

[알고리즘] 개념

목록 보기
11/13

스택/큐

🥕프린터

const array = [1, 2, 3, 4, 5];
console.log(array.some((element) => element % 2 === 0)); //true
  • map함수를 통해 객체 형태로 만들 수도 있다.
    let list = priorities.map((v, i)=> ({
        my: i === location, 
        val: v
    }));

다리를 지나는 트럭

완전 탐색

카펫

해시

완주하지 못한 선수

  • 해시 
function solution(participant, completion) {
    let sH=new Map(); //key, value 만듦 
    for(let x of participant){
        //동명이인
        if(sH.has(x)) sH.set(x, sH.get(x)+1);
        else sH.set(x, 1);
        
    }
    for(let x of completion){
        sH.set(x, sH.get(x)-1);
    }
    for(let [key, val] of sH){
        if(sH.get(key)===1) return key; //찾으면 종료
    }
}
  • Map()객체: 맵 객체를 생성한다. 맵 객체는 key:value의 쌍으로 이루어져있다.
  • map객체로 for문을 돌 때는, for(let [key, val] of map)과 같이 도는 것을 기억하자!

위장

function solution(clothes) {
    let answer=0;
    let map=new Map();
    for(let i=0; i<clothes.length; i++){
        if(map.has(clothes[i][1])) map.set(clothes[i][1], map.get(clothes[i][1])+1);
        else map.set(clothes[i][1], 1);
    }

    let tmp=1; 
    for(let [key, val] of map){
        tmp*=(val+1);
    }
    answer=tmp-1;
    return answer;
}
  • 조합 잘 생각하기! 상의2벌, 하의1벌이라고 생각했을 때 2x1을 하게 되면 상하의가 각각 무조건 하나씩 들어간다. 하지만 만약에 상의or하의 둘 중 하나만 들어가는 경우도 고려하려면 (2+1)x(1+1)을 해줘야한다. 하지만 이렇게 연산하면 둘다 들어가지 않는경우도 고려하는 것이기 때문에 -1을 해준다. 즉, 상의 2벌과 하의1벌인데 상의나 하의 중 하나만 들어갈 수 있는 조합의 수는 (2+1)x(1+1)-1=5이다.

정렬

가장 큰 수

function solution(numberes) {
    let answer='';
    //각각 요소를 문자열로 만든 후, 문자 크기 비교 후, 배열을 문자열로 합침
    numberes=numberes.map((v)=>v+'').sort((a, b)=>(b+a)-(a+b)).join('');
    numberes[0]==='0' ? answer += '0' : answer=numberes; //모두 0일때도 고려(0000)
    return answer; 
}
  • 숫자+문자=문자 (3+''='3')
  • 문자+문자=문자 ('10'+'20'='1020')
  • sort()는 양수일때 자리를 바꾸고, 음수일때는 제자리에, 0일때는 나머지의 자리를 바꾼다.

🥕DFS

타겟 넘버

function solution(numbers, target) {
    let answer = 0;
    function DFS(v, t){
        if(v===numbers.length){
            //판단
            if(t===target) answer++;
        }
        else{
            DFS(v+1, t-numbers[v]); //- 하는경우
            DFS(v+1, t+numbers[v]); //+ 하는경우
        }
    }
    
    DFS(0, 0);
    return answer;
}
  • t-=numbers[v]와 같이 작성하면 안됨! t자체를 바꾸는 것이 아니라, 저 단계에서 빼주고 더해야함
  • else문에서 for문 사용x
profile
김예지
내가 짱이다 😎 매일 조금씩 성장하기🌱
이전 포스트

[프로그래머스 level1] 한장에 핵심 정리📝

다음 포스트

[인프런 javascript] 한장에 핵심 정리📝

0개의 댓글