본문 바로가기

프로그래머스/Greedy

[그리디] 프로그래머스 '구명보트' - js

반응형

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42885?language=javascript 

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

2. 설명

이 문제는 그리디 알고리즘을 사용하여 푸는 문제이다! 그리디는 정렬이 핵심이라고 한다. 어떻게 정렬해야 최적의 해가 나올지 항상 고민하자. 

+ 계단을 한 칸 내지 두 칸만 움직일 수 있다~ 토끼는 번식을 한 달 내지 두 달 뒤에 할 수 있다~와같이

1과 2에 밀접한 관계가 있으면 피보나치를 사용하여 문제를 푼다! (스터디원분이 주신 꿀팁^^)

이처럼 배열에 여러 값들이 있는데, 얘네들을 최소한의 방법으로 지지고 볶고 해야할 때(?) 그리디 알고리즘을 쓰면 좋을 것 같다.

그리디 알고리즘 이해를 위해 참고한 블로그는 다음과 같다.

https://velog.io/@devjade/JavaScript%EB%A1%9C-greedy-algorithm%ED%83%90%EC%9A%95-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

 

JavaScript로 greedy algorithm(탐욕 알고리즘) 구현하기

Greedy Algorithm(탐욕 알고리즘)은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 탐욕 알고리즘으로 문제를 해결하는 방법은 다음과

velog.io

3. 코드

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

 

다른 풀이 방법

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

처음 본 형태인데, for문 안에 저렇게 여러가지의 변수들을 넣어도 되는지 몰랐다. 무궁무진한 코딩의 세계^^

두 가지 변수를 같이 비교해가며 조건을 작성해주고 싶을 때는 저런 방법도 좋을 것 같다. 

아직까지는 나한텐 좀 어려운 형태인걸로 ㅠㅠ

저걸 내 걸로 만들고 익숙해지기까지는 시간이 좀 걸리겠지만... 유용하게 쓰일 것 같아 기록해둔다!

 

https://jsikim1.tistory.com/152

 

Programmers 코딩테스트 연습 - 구명보트 (JavaScript)

Programmers 프로그래머스 코딩테스트 연습 - 구명보트 (JavaScript) Programmers(프로그래머스)의 코딩테스트 연습문제 Level 2 중, 구명보트 문제를 JavaScript로 풀어보도

jsikim1.tistory.com

 

반응형