알고리즘 문제 정리(명예의 전당1, 2016년, 카드뭉치, 과일 장수)

문제1 : 명예의 전당1

"명예의 전당"이라는 TV 프로그램에서는 매일 1명의 가수가 노래를 부르고, 시청자들의 문자 투표수로 가수에게 점수를 부여합니다. 매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올려 기념합니다. 즉 프로그램 시작 이후 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게 됩니다. k일 다음부터는 출연 가수의 점수가 기존의 명예의 전당 목록의 k번째 순위의 가수 점수보다 더 높으면, 출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됩니다.

이 프로그램에서는 매일 "명예의 전당"의 최하위 점수를 발표합니다. 예를 들어, k = 3이고, 7일 동안 진행된 가수의 점수가 [10, 100, 20, 150, 1, 100, 200]이라면, 명예의 전당에서 발표된 점수는 아래의 그림과 같이 [10, 10, 10, 20, 20, 100, 100]입니다.

명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때, 매일 발표된 명예의 전당의 최하위 점수를 return하는 solution 함수를 완성해주세요.

제한사항

3 ≤ k ≤ 100
7 ≤ score의 길이 ≤ 1,000

입출력 예

k	score	result
3	[10, 100, 20, 150, 1, 100, 200]	[10, 10, 10, 20, 20, 100, 100]
4	[0, 300, 40, 300, 20, 70, 150, 50, 500, 1000]	[0, 0, 0, 0, 20, 40, 70, 70, 150, 300]

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

아래와 같이, [0, 0, 0, 0, 20, 40, 70, 70, 150, 300]을 return합니다.

- 내가 푼 풀이

function solution(k, score) {
    const honor = []
    const result = []

    for(let i=0; i < score.length; i++){
        if(i < k) {
            honor.push(score[i])
            honor.sort((a, b) => b-a)
        } else{ 
            if(score[i] > Math.min(...honor)){
             honor.pop()
             honor.push(score[i])
             honor.sort((a, b) => b-a)
         } 
        }
        result.push(honor[honor.length -1])
    }
    
    return result

}

for문을 이용해 일자에 나온 점수가 조건에 맞을 경우 수정해주는 방식을 사용했다.

우선 k일까지는 무조건 honor에 넣어주었으며, 그 이후부터는 명예의 전당 점수보다 클 경우에만 honor에 넣어주었다.

제일 작은 값을 pop으로 없애주었으며, 새로운 값을 넣어준 후 내림차순 배열 해주었다.

그리고 명예의 전당의 제일 작은 값을 result에 넣어준 후, for문이 끝나면 result 배열을 반환하는 방법을 사용했다.

조금더 변형해보자면, 나온 값을 'sort((a,b)=>a-b)'로 오름 차순해준 후, shift()로 맨 앞 값을 제거해주고, result에 넣을 때 'honor[0]'로 첫번 째 값을 넣어주는 방법도 있다.

'...' 연산자 : Spread 문법. 배열을 풀어서 개별 요소로 확장하는 역할을 한다 - 배열 안의 요소들을 개별 인자로 전달할 때 사용됩니다.
ex) 배열 honor가 [10, 20, 5]라고 하면 Math.min(...honor)는 실제로 Math.min(10, 20, 5)로 해석
pop() : 배열의 마지막 요소를 제거
shift() : 배열의 첫번째 요소를 제거

- 다른 풀이

function solution(k, score) {
    const stack = []; // k개의 점수를 저장할 스택

    return score.reduce((a, c) => { // reduce 함수를 사용하여 점수 배열을 처리
        if (stack.length < k) { // 스택에 아직 k개 미만의 점수가 있을 때
            stack.push(c); // 현재 점수를 스택에 추가
            stack.sort((a, b) => a - b); // 오름차순 정렬
        } else { // 스택에 k개의 점수가 모두 채워졌을 때
            stack.push(c); // 현재 점수를 스택에 추가
            stack.sort((a, b) => a - b); // 오름차순 정렬
            stack.shift(); // 가장 오래된(최하위) 점수 제거
        }
        
        a.push(stack[0]); // 현재 날짜의 명예의 전당의 최하위 점수를 결과 배열에 추가
        return a; // reduce 함수의 누산기인 배열 a를 반환
    }, []);
}

문제2 : 2016년

2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까지 각각 SUN,MON,TUE,WED,THU,FRI,SAT

입니다. 예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 "TUE"를 반환하세요.

제한 조건

2016년은 윤년입니다.
2016년 a월 b일은 실제로 있는 날입니다. (13월 26일이나 2월 45일같은 날짜는 주어지지 않습니다)

입출력 예

a	b	result
5	24	"TUE"

- 내가 푼 풀이

function solution(a, b) {
    let weeks = ['FRI', 'SAT', 'SUN', 'MON', 'TUE', 'WED', 'THU'];
    let months = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
    let whatWeek = b - 1;
    for (let i = 1; i < a; i++) {
        whatWeek += months[i - 1];
    }

    return weeks[whatWeek % 7];
}

구하려는 날짜의 전 일수를 모두 더해서 7로 나눠 나오는 나머지 값으로 요일을 구하는 풀이이다.

우선 각 월의 일수를 정의해놓은 후, for문을 통해 구하려는 날짜의 전 월까지(i-1)의 일수를 모두 더한다.

그리고 해당 월의 일수를 따로 더해준다. (배열이기에 0부터 시작해서 -1을 해준다.)

-> whatWeek(해당 월 일수) += months[i-1](전 월까지의 일수)

더해진 모든 일수를 7로 나눈 나머지 값을 요일 배열에 매핑시켜 return 한다.

*1월의 경우 for 반복문이 실행되지 않는다.

- 다른 풀이

function getDayName(a, b) {
    var tempDate = new Date(2016, a - 1, b); // 입력된 월과 일로 Date 객체 생성

    return tempDate.toString().slice(0, 3).toUpperCase(); // Date 객체의 요일을 문자열로 변환하여 반환
}

tempDate = Tue May 24 2016 00:00:00 GMT+0900 (KST) 이러한 형식

function getDayName(a, b) {
    var dayList = ['FRI', 'SAT', 'SUN', 'MON', 'TUE', 'WED', 'THU'];
    var monthArr = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
    var daySum;

    if (a < 2) {
        // 1월일 경우
        daySum = b - 1;
    } else {
        // 2월 이상일 경우
        daySum = monthArr.slice(0, a - 1).reduce((a, b) => a + b) + b - 1;
    }

    return dayList[daySum % 7];
}

내가 푼 풀이와 유사한 풀이.

나같은 경우 for문을 통해 이전 달까지 더해주었다.

이 풀이의 경우 slice를 통해 이전 달까지 배열을 잘라준 후(5월을 구할 경우, monthArr[3]까지 더해주어야함. 그래서 a-1 = 4가 되어야함. 4 이전 위치까지 잘라주기 때문에.), reduce 누산기를 통해 이전달과 해당 일을 더해주었다.

문제3:카드뭉치

코니는 영어 단어가 적힌 카드 뭉치 두 개를 선물로 받았습니다. 코니는 다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는지 알고 싶습니다.

원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다.
한 번 사용한 카드는 다시 사용할 수 없습니다.
카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.
기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.

예를 들어 첫 번째 카드 뭉치에 순서대로 ["i", "drink", "water"], 두 번째 카드 뭉치에 순서대로 ["want", "to"]가 적혀있을 때 ["i", "want", "to", "drink", "water"] 순서의 단어 배열을 만들려고 한다면 첫 번째 카드 뭉치에서 "i"를 사용한 후 두 번째 카드 뭉치에서 "want"와 "to"를 사용하고 첫 번째 카드뭉치에 "drink"와 "water"를 차례대로 사용하면 원하는 순서의 단어 배열을 만들 수 있습니다.

문자열로 이루어진 배열 cards1, cards2와 원하는 단어 배열 goal이 매개변수로 주어질 때, cards1과 cards2에 적힌 단어들로 goal를 만들 있다면 "Yes"를, 만들 수 없다면 "No"를 return하는 solution 함수를 완성해주세요.

제한사항

1 ≤ cards1의 길이, cards2의 길이 ≤ 10
2 ≤ goal의 길이 ≤ cards1의 길이 + cards2의 길이
cards1, cards2, goal의 문자열들은 모두 알파벳 소문자로만 이루어져 있습니다.

입출력 예

cards1	cards2	goal	result
["i", "drink", "water"]	["want", "to"]	["i", "want", "to", "drink", "water"]	"Yes"
["i", "water", "drink"]	["want", "to"]	["i", "want", "to", "drink", "water"]	"No"

입출력 예 설명

입출력 예 #1

본문과 같습니다.

입출력 예 #2

cards1에서 "i"를 사용하고 cards2에서 "want"와 "to"를 사용하여 "i want to"까지는 만들 수 있지만 "water"가 "drink"보다 먼저 사용되어야 하기 때문에 해당 문장을 완성시킬 수 없습니다. 따라서 "No"를 반환합니다.

- 내가 푼 풀이

function solution(cards1, cards2, goal) {

    for(const s of goal) {

        if(cards1[0] == s) {
            cards1.shift();
        } else if(cards2[0] == s) {
            cards2.shift();
        } else {
            return "No"
        }
    }

    return "Yes";
}

for문을 통해 goal에 있는 단어 하나하나를 card1과 card2의 첫번째 카드에 있는지 확인한 후, 일치하면 해당 카드의 첫번째 카드를 없애주는 방법. 만약 첫번째 카드에 둘다 해당하지 않으면 'no'반환.

- 다른 풀이

function solution(cards1, cards2, goal) {
    let j = 0;
    let k = 0;
    for(let i=0;i<goal.length;i++){
        if(goal[i] == cards1[j]) j++;
        else if(goal[i] == cards2[k]) k++;
        else return "No"
    }
    return "Yes";
}

비슷한듯 다른 풀이. card1과 card2 배열에 들어갈 n번째 수를 정의해놓고 for문을 통해 n번째 카드랑 일치하는지 비교하는 방식. 일치할 경우 정의한 숫자에 1을 더해주어 다음 카드랑 비교가능하도록 구현.

문제4 : 과일 장수

과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며, k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과 한 상자의 가격은 다음과 같이 결정됩니다.

한 상자에 사과를 m개씩 담아 포장합니다.
상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m 입니다.

과일 장수가 가능한 많은 사과를 팔았을 때, 얻을 수 있는 최대 이익을 계산하고자 합니다.(사과는 상자 단위로만 판매하며, 남는 사과는 버립니다)

예를 들어, k = 3, m = 4, 사과 7개의 점수가 [1, 2, 3, 1, 2, 3, 1]이라면, 다음과 같이 [2, 3, 2, 3]으로 구성된 사과 상자 1개를 만들어 판매하여 최대 이익을 얻을 수 있습니다.

(최저 사과 점수) x (한 상자에 담긴 사과 개수) x (상자의 개수) = 2 x 4 x 1 = 8

사과의 최대 점수 k, 한 상자에 들어가는 사과의 수 m, 사과들의 점수 score가 주어졌을 때, 과일 장수가 얻을 수 있는 최대 이익을 return하는 solution 함수를 완성해주세요.

제한사항

3 ≤ k ≤ 9
3 ≤ m ≤ 10
7 ≤ score의 길이 ≤ 1,000,000
이익이 발생하지 않는 경우에는 0을 return 해주세요.

입출력 예

k	m	score	result
3	4	[1, 2, 3, 1, 2, 3, 1]	8
4	3	[4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2]	33

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

다음과 같이 사과 상자를 포장하여 모두 팔면 최대 이익을 낼 수 있습니다.

사과 상자	가격
[1, 1, 2]	1 x 3 = 3
[2, 2, 2]	2 x 3 = 6
[4, 4, 4]	4 x 3 = 12
[4, 4, 4]	4 x 3 = 12

따라서 (1 x 3 x 1) + (2 x 3 x 1) + (4 x 3 x 2) = 33을 return합니다.

- 내가 푼 풀이

function solution(k, m, score) {
    if(score.length < m){
        return 0;
    }
    
    score.sort((a, b) => a - b);
    
    let total = 0;
    
    while(score.length >= m){
        const box = score.splice(score.length - m, m);
        
        const prize = m * Math.min(...box);
        
        total += prize;
    }
    
    return total;
}

- score.length를 통해 사과 개수가 1박스에 들어가는 수보다 작으면 0 return.

- 사과를 점수 순서대로 오름차순 정렬

- 박스에 뒤에서 한 박스에 들어가는 숫자만큼 splice를 통해 잘라냄

- 잘라낸 값 중 전개연산자(...)를 사용해 Math.min을 통해 가장 작은 값을 추출하여 개수만큼 곱해 1박스의 가격 도출

- 전체 가격에 더해줌

- 1박스를 채울 수 없을때까지 반복

- 다른 풀이

function solution(k, m, score) {
    let answer = 0;
    const sortedScore = score.slice().sort((a, b) => a - b).slice(score.length % m);
    for (let i = 0; i < sortedScore.length; i += m) {
        answer += sortedScore[i] * m;
    }
    return answer;
}

생각지 못한 풀이.

우선 박스에 들어가지 않는 사과는 빼고 필요한 부분만 빼내는 sortedScore를 만든다.

원본 배열 보존을 위해 'slice()'로 copy를 해서 사용한 것이 인상적이었다.

그리고 오름차순 정렬한 후, 박스에 들어가는 수로 나눠 나온 나머지를 잘라낸다.

다음은 for문을 통해 각 박스의 값을 더해준다.

오름차순을했기 때문에 맨 앞에 사과의 값에 사과의 숫자를 곱해주면 된다.

i는 사과의 숫자만큼 더해줘 각 박스의 제일 작은 값을 가리킬 수 있게 해준다.

저작자표시 비영리 변경금지

'개발 기초 다지기' 카테고리의 다른 글

티켓 예매사이트 ERD, API 명세서 구현하기 (0)	2024.07.03
tsconfig.json 기초 (0)	2024.07.01
호이스팅과 클로져 (0)	2024.06.27
과제 리팩토링 (메뉴 원하는 카체고리 순서로 정렬) (0)	2024.06.26
복습 그동안 소소하게 궁금했던것들 정리 (스키마 관계 설정, 모듈 export default) (0)	2024.06.25

차근차근 쌓아가는 개발이야기

알고리즘 문제 정리(명예의 전당1, 2016년, 카드뭉치, 과일 장수)

문제1 : 명예의 전당1

문제2 : 2016년

문제3:카드뭉치

문제4 : 과일 장수

'개발 기초 다지기' 카테고리의 다른 글

댓글

티스토리툴바

알고리즘 문제 정리(명예의 전당1, 2016년, 카드뭉치, 과일 장수)

문제1 : 명예의 전당1

문제2 : 2016년

문제3:카드뭉치

문제4 : 과일 장수

'개발 기초 다지기' 카테고리의 다른 글

관련글

댓글

티스토리툴바