오늘의 알고리즘 👍

📝 1. 구명보트

• 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

• 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

• 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

• 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

▷ 입출력 예

solution([70, 50, 80, 50], 100) // 3
solution([70, 80, 50], 	100) // 3

▷ 해결 못함 ❌

• 시간부족으로 해결하지 못했다.

▷ 수업 풀이

function solution(people, limit) {
    people.sort((a, b) => b - a)
    
    let answer = 0;
    let boat = [];
    
    for( let i = 0; i < people.length; i++ ) {
        if(people[i] === null) continue;
        boat.push(people[i])
        people[i] = null;
        
        const weight = limit - boat[0];
        const idx = people.includes( weight )
                        ? people.indexOf( weight )
                        : people.findIndex(( el ) => {
                            return el !== null && el < weight
                        })
        
        // 태울 사람이 있는 경우
        if( idx !== -1 ) {
            people[ idx ] = null;
        }
        
        answer++;
        boat = [];
    }
    
    return answer
}

• 위 코드는 효율성 검사에서 실패해서 다시 풀었다.

function solution(people, limit) {
    people.sort((a, b) => b - a)

    let answer = 0;
    let last = people.length - 1;
    
    for( let i = 0; i < people.length; i++ ) {
        const weight = limit - people[i];
        
        // 가벼운 사람의 몸무게가 보트에 수용할 수 있는 몸무게보다 작을 경우
        // === 보트에 태울 수 있다.
        if( weight >= people[ last ] ) {
            last--;
        }
        answer++;
        
        // 대기열에 아무도 없는 경우
        if( i >= last ) {
            return answer;
        }
    }
}

▷ reduce 매서드 사용 풀이

function solution(people, limit) {
    people.sort((a, b) => b - a)

    let last = people.length - 1;
    return people.reduce(( acc, cur, i ) => {
        if( i <= last ) {
            const weight = limit - cur;
            if( weight >= people[ last ] ) {
                last--;
            }
            acc++;
        }
        return acc;
    }, 0)
}

📝 2. 오픈채팅방

• 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다.

• 신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다.

• 채팅방에 누군가 들어오면 다음 메시지가 출력된다.

  "[닉네임]님이 들어왔습니다."

• 채팅방에서 누군가 나가면 다음 메시지가 출력된다.

  "[닉네임]님이 나갔습니다."

• 채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다.

  1. 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다.
  2. 채팅방에서 닉네임을 변경한다.

• 닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다.

▷ 입출력 예

solution(["Enter uid1234 Muzi", "Enter uid4567 Prodo","Leave uid1234","Enter uid1234 Prodo","Change uid4567 Ryan"]) // ["Prodo님이 들어왔습니다.", "Ryan님이 들어왔습니다.", "Prodo님이 나갔습니다.", "Prodo님이 들어왔습니다."]

▷ 해결 못함 ❌

• 시간부족으로 해결하지 못했다.

▷ 수업 풀이

function solution(record) {
    const answer = [];
    
    const user = {}; // 유저들의 최종 닉네임 값을 저장
    for( let i = 0; i < record.length; i++ ) {
        const [ action, uid, nickname ] = record[i].split(" ");

        if( nickname ) {
            user[ uid ] = nickname;
        }
        
        if( action !== "Change" ) {
            // Enter, Leave 둘 중 하나라면
            answer.push({ action, uid })
        }
    }
    
    for( let idx in answer ) {
        answer[ idx ] = user[ answer[ idx ].uid ] + (
            answer[ idx ].action === "Enter"
                ? "님이 들어왔습니다."
                : "님이 나갔습니다."
        )
    }
    
    return answer
}

▷ reduce 매서드 사용 풀이

function solution(record) {
    record = record.map( el => el.split(' ') );
    
    // 유저들의 최종 닉네임 값을 저장
    const user = record.reduce(( acc, cur ) => {
        const [ action, uid, nickname ] = cur;
        if( nickname ) acc[ uid ] = nickname;
        return acc
    }, {})
    
    const answer = record.reduce(( acc, cur ) => {
        const [ action, uid ] = cur;
        if( action !== 'Change' ) {
            // Enter, Leave 둘 중 하나라면
            acc.push(`${ user[ uid ] }님이 ${ action === 'Enter' ? '들어왔습니다.' : '나갔습니다.' }`)
        }
        return acc;
    }, [])
    
    return answer
}

출처: 프로그래머스
출처: 코드캠프