[항해99] programmers 코딩테스트 연습문제 30~34

[항해99] 프로그래밍 기초 주차 / 달리기반 / 7기 / D반 / 9조

 

코딩테스트 연습문제

30. 최소직사각형

(문제)

명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.

아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.

명함 번호	가로 길이	세로 길이
1	60	50
2	30	70
3	60	30
4	80	40

가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다.

모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.

 

(제출 답)

function solution(sizes) {
    let minarr = []; //최소값배열 생성
    let maxarr = []; //최대값배열 생성
    for(let i = 0; i < sizes.length; i++){ //#반복문 sizes 배열 길이 만큼 반복
    sizes[i][0] > sizes[i][1] ? maxarr.push(sizes[i][0]) : maxarr.push(sizes[i][1]); //[[0,1],...] 배열 안 각각의 인덱스 내 두 값을 비교하여 앞의 값이 큰 게 맞으면 앞의 수를 최대값배열로, 작으면 뒤의 수를 최대값배열로. 
    sizes[i][0] > sizes[i][1] ? minarr.push(sizes[i][1]) : minarr.push(sizes[i][0]); //앞의 값이 큰 게 맞으면 뒤의 수를 최소값배열로, 작으면 앞의 수를 최소값배열로.
}
    return Math.max(...minarr)*Math.max(...maxarr); //최소값배열의 최대값 곱하기 최대값배열의 최대값
}

✅ 풀이 과정

<중간에 ? 연산자 넣는 거 엄청 헷갈렸던..ㅋㅋ>

let arr = [[60, 50], [30, 70], [60, 30], [80, 40]]

// size = [w,h]

// 최소 직사각형.

// 인덱스 안에서 w와 h를 비교했을 때 최소값들 중 가장 큰 수

// 마찬가지로 비교했을 때 최대값들 중 가장 큰 수

//배열 안 값에서 0, 1 비교 => 최소값들의 배열 minarr, 최대값들의 배열 만들기 maxarr

// minarr 에서 가장 큰 수, maxarr 에서 가장 큰 수. (최대값에서 가장 큰 수는 모든 값에서 큰 수를 찾는 방식이어도 무방하겠지만)

let minarr = [];

let maxarr = [];

for(let i = 0; i < arr.length; i++){

arr[i][0] > arr[i][1] ? maxarr.push(arr[i][0]) : maxarr.push(arr[i][1]);

arr[i][0] > arr[i][1] ? minarr.push(arr[i][1]) : minarr.push(arr[i][0]);

}

console.log(minarr) // [ 50, 30, 30, 40 ]

console.log(maxarr) // [ 60, 70, 60, 80 ]

let a = Math.max(...minarr)

console.log(a) // 50

let b = Math.max(...maxarr)

console.log(b) // 80

console.log(a*b) //4000

 

🤼‍♀️ 다른 풀이 1(생각의 접근 방법은 같으나, 풀이는 두 줄이라니!)

function solution(sizes) {
    const [hor, ver] = sizes.reduce(([h, v], [a, b]) => [Math.max(h, Math.max(a, b)), Math.max(v, Math.min(a, b))], [0, 0])
    return hor * ver;
}

🤼‍♀️ 다른 풀이 2 (간단한데, 아직 이해는 잘..ㅠ)

function solution(sizes) {
    let w = 0;
    let h = 0;
    sizes.forEach(s => {
        const [a, b] = s.sort((a,b) => a-b);
        if (a > h) h = a;
        if (b > w) w = b;
    });

    return w * h;
}

 

⏩ 추가학습

 

31. 같은 숫자는 싫어(효율성...)

(문제)

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

• arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
• arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

제한사항

• 배열 arr의 크기 : 1,000,000 이하의 자연수
• 배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

(제출 답)

function solution(arr){
    let answer = []; //배열 생성
    for(let i = 0; i < arr.length; i++){ // #반복문 배열의 길이만큼 반복
    if ( arr[i] === arr[i+1]){  // 배열을 순차적으로 검사하는데, i번째 값이 바로 다음 값과 동일하다면
         continue; //계속 돌기 (continue 는 생략 가능)
    } else{
        answer.push(arr[i]) //같지 않다면(연속된 수 아님) 새 배열에 넣어주기
    }
}
    return answer;
}

✅ 풀이 과정

// 다음 값이 동일한가? 제거하라

실패 1 (i를 다시 0부터 시작해야 하는 조건을 넣어줘야 함. i--)

let arr = [4,4,4,3,3]
for(let i = 0; i < arr.length; i++){
    if ( arr[i] == arr[i+1]){ // 두 값 비교했어. 같아? 같으면,
        arr.splice(i, 1) //뒤에 값 제거해    
    } 
}
console.log(arr) // [4,4,3]출력...실패

실패 2 (테스트는 다 통과했는데, 효율성 테스트 점수는 0...)

function solution(arr){
    for(let i = 0; i < arr.length; i++){
    if ( arr[i] == arr[i+1]){
        arr.splice(i, 1)
        i--; 
    } 
}
    return arr;
}

=> '같은 풀이인데 새로운 배열에 넣으면 통과되더라' 라는 경험을 듣고.. 약간 변경. splice 대신 else 조건에 push 이용.

🤼‍♀️ 다른 풀이(분명 짧은 풀이가 있을 것 같았다. filter 함수를 이해했어도 실제 적용하는 건 쉽지 않은 듯)

(값이 다음 값과 같지 않다는 조건을 충족시킬 것!이라는 뜻..?)

function solution(arr)
{
    return arr.filter((val,index) => val != arr[index+1]);
}

⏩ 추가학습

filter

find 메서드는 함수의 반환 값을 true로 만드는 단 하나의 요소를 찾습니다.

조건을 충족하는 요소가 여러 개라면 arr.filter(fn)를 사용하면 됩니다.

filter는 find와 문법이 유사하지만, 조건에 맞는 요소 전체를 담은 배열을 반환한다는 점에서 차이가 있습니다.

let results = arr.filter(function(item, index, array) {
  // 조건을 충족하는 요소는 results에 순차적으로 더해집니다.
  // 조건을 충족하는 요소가 하나도 없으면 빈 배열이 반환됩니다.
});

 

console.log("주어진 배열에서 요소 1개를 랜덤하게 골라 반환하는 함수")
let a = [5,0,2,7]
a = a[Math.floor(Math.random() * a.length)];
console.log(a)

console.log("난수 생성 함수 만들기(범위 지정)")
//min <= number <= max
function rand(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
  }
console.log(rand(0, 100))

32. 두 개 뽑아서 더하기

(문제)

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers의 길이는 2 이상 100 이하입니다.
• numbers의 모든 수는 0 이상 100 이하입니다.

(제출 답)

function solution(numbers) { 
    const answer = []; //배열 생성
    for (let i = 0; i < numbers.length; i++) { //#반복문
      for (let j = 0; j < numbers.length; j++) { //#반복문
        if (i !== j) { //#조건문 numbers 배열 내 i번째 값과 j번째 값이 같지 않으면
          answer.push(numbers[i]+numbers[j]); //두 합을 더해서 새 배열에 속에 저장~
        }
      }
    }
    const result = Array.from(new Set(answer)); //new Set 함수로 중복값 제거하고, Array.from으로 배열 새로 생성
    result.sort((a, b) => a - b); //sort 함수로 오름차순 정렬!
    return result
}

✅ 풀이 과정

// 배열 내 무작위 값 2개 선택하는데, 두 개는 같지 않아야함, 그리고 이를 더해  만들 수 있는 모든 수를 배열

let numbers = [5,0,2,7]

var answer = [];

for(let i = 0; i < numbers.length; i++){

for (let j = 0; j <numbers.length; j++){

if ( i != j){

answer.push(numbers[i]+numbers[j]);

}}}

console.log(answer) //[
  5, 7, 12, 5,  2,
  7, 7,  2, 9, 12,
  7, 9
]

 

// 배열 내 겹치는 값은 하나씩만 출력(new Set)

console.log(new Set(answer)); //Set(5) { 5, 7, 12, 2, 9 }

let result = Array.from(new Set(answer)); 

console.log(result) //[ 5, 7, 12, 2, 9 ]

 

// 오름차순 정렬 sort((a,b) => a-b)

console.log(result.sort((a,b)=>a-b)) //[ 2, 5, 7, 9, 12 ]

 

 

🤼‍♀️ 다른 풀이(array.from 대신 [...new Set()] 으로 끝낼 수도)

function solution(numbers) {
    let answer = [];
    for(let i=0; i < numbers.length; i++){
        for(let j=0; j<numbers.length; j++){
            if(i===j) continue; // 동일한 index는 skip
            answer.push(numbers[i]+numbers[j])
        }
    }
    answer = [...new Set(answer)].sort((a,b)=>a-b)
    console.log(answer)
    return answer;
}

 

⏩ 추가학습

Array.from() method returns an array from any iterable object. (반복 가능한 객체)

                        Using x.from(), where x is an array will return undefined.

Array.from("ABCDEFG") // A,B,C,D,E,F,G

new Set() Creates a new Set

const letters = new Set(["a","b","c"]); // 3

<script>
// Create a Set
const letters = new Set();

// Add Values to the Set
letters.add("a");
letters.add("b");
letters.add("b");
letters.add("c");

// Display set.size
document.getElementById("demo").innerHTML = letters.size;
</script>

//결과는 3

https://minhanpark.github.io/today-i-learned/javascript-set/

자바스크립트에서 Set 활용하기

Math.floor() rounds a number DOWN to the nearest integer(정수)

let a = Math.floor(0.60);   // 0
let b = Math.floor(0.40);   // 0
let c = Math.floor(5);        // 5
let d = Math.floor(5.1);     // 5
let e = Math.floor(-5.1);   // -6
let f = Math.floor(-5.9);   // -6

Math.random() returns a random number between 0 (inclusive) and 1 (exclusive):

let x = Math.random(); // 0~1 숫자 아무거나 

Return a random number between 1 and 10:

Math.floor((Math.random() * 10) + 1); // 1~10 숫자 아무거나

console.log("주어진 배열에서 요소 1개를 랜덤하게 골라 반환하는 함수")
let a = [5,0,2,7]
a = a[Math.floor(Math.random() * a.length)];
console.log(a)

console.log("난수 생성 함수 만들기(범위 지정)")
//min <= number <= max
function rand(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
  }
console.log(rand(0, 100))

33. 로또의 순위(ㅠㅠ)

https://writingcode.tistory.com/25

 

34. 모의고사(ㅜㅜ)

(문제)

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 조건

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

(제출 답)

function solution(answers) {
    let su1 = [1,2,3,4,5] //5개의 숫자가 반복
    let su2 = [2,1,2,3,2,4,2,5] //8개의 숫자가 반복
    let su3 = [3,3,1,1,2,2,4,4,5,5] //10개의 숫자가 반복
    
    let result = [0,0,0]; //결과 배열 생성
    for (let i = 0; i < answers.length; i++) { //정답 수의 길이 = 문제 수 #반복문
     if (su1[i % 5] === answers[i]) result[0]++; //#조건문 #비교연산자 //배열의 인덱스가 0~5이고, 인덱스 값을 5로 나눈 나머지는 0~5를 반복하게 된다. // 그 값과 정답이 같다면, result 배열의 첫번째 자리에 값 삽입.
     if (su2[i % 8] === answers[i]) result[1]++;
     if (su3[i % 10] === answers[i]) result[2]++;
  }
    var answer = []; //출력할 배열 생성
    const maxValue = Math.max(...result); //결과 배열의 최대값
    let index = 0; //answer의 인덱스값이 될 변수 생성 (이 부분이 흥미롭!)
    for (let i = 0; i < 3; i++) { //#반복문 수포자 3명의 결과를 보자
        if (maxValue === result[i]) { //결과 배열의 최대값과 일치하는 수포자 찾는다면(3명 중 점수가 가장 높은 학생은?)
            answer[index] = i + 1; //출력 값 (1번?2번?3번? , 겹칠 수 있음, 순서대로라서 오름차순 됨)
            index++; //인덱스값도 +1 한 뒤 반복해주세요
    }
  }
    return answer;
}

✅ 풀이 과정

어려워.. 찾은 답을 열심히 해석해석..

생각한 로직은 아래와 같은데,

// 각각의 답안(정답 포함)은 배열에서 n까지 반복한 것 ()

// 각각의 답안과 정답 배열의 각 인덱스 값을 비교하여 true면 +1점, false면 0점을 부여한 뒤 값 더하기

// 가장 높은 점수 받은 사람 출력, 점수 같으면 같이 출력하되 오름차순 정렬 sort((a,b)=> a > b)

각각의 배열을 만들려고 했다가, 그것은 어리석은 것이었고... 찾아본 위 정답 코드는 배울 포인트가 많으니 복습해서 익히자!

🤼‍♀️  다른 풀이 1

function solution(answers) {
    var answer = [];
    var a1 = [1, 2, 3, 4, 5];
    var a2 = [2, 1, 2, 3, 2, 4, 2, 5]
    var a3 = [ 3, 3, 1, 1, 2, 2, 4, 4, 5, 5];

    var a1c = answers.filter((a,i)=> a === a1[i%a1.length]).length;
    var a2c = answers.filter((a,i)=> a === a2[i%a2.length]).length;
    var a3c = answers.filter((a,i)=> a === a3[i%a3.length]).length;
    var max = Math.max(a1c,a2c,a3c);

    if (a1c === max) {answer.push(1)};
    if (a2c === max) {answer.push(2)};
    if (a3c === max) {answer.push(3)};

    return answer;
}

🤼‍♀️  다른 풀이 2

function solution(answers) {
    var answer = [];
    const man1 = [1, 2, 3, 4, 5];
    const man2 = [2, 1, 2, 3, 2, 4, 2, 5];
    const man3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
    let count = [0, 0, 0];

    for(let i = 0; i < answers.length; i++) {
        if(answers[i] == man1[i % man1.length]) count[0]++;
        if(answers[i] == man2[i % man2.length]) count[1]++;
        if(answers[i] == man3[i % man3.length]) count[2]++;
    }

    const max = Math.max(count[0], count[1], count[2]);
    for(let i = 0; i < count.length; i++) {
        if(max == count[i]) answer.push(i + 1);
    }

    return answer;
}

🤼‍♀️  다른 풀이 3

function solution(answers) {
    var count_one = 0;
    var count_two = 0;
    var count_three = 0;
    for(var i=0; i<answers.length; i++){
      if(((i+1)%5) === 1 && answers[i] === 1) count_one += 1;
      if(((i+1)%5) === 2 && answers[i] === 2) count_one += 1;
      if(((i+1)%5) === 3 && answers[i] === 3) count_one += 1;
      if(((i+1)%5) === 4 && answers[i] === 4) count_one += 1;
      if(((i+1)%5) === 0 && answers[i] === 5) count_one += 1;        
      if(((i+1)%8) === 1 && answers[i] === 2) count_two += 1;
      if(((i+1)%8) === 2 && answers[i] === 1) count_two += 1;
      if(((i+1)%8) === 3 && answers[i] === 2) count_two += 1;
      if(((i+1)%8) === 4 && answers[i] === 3) count_two += 1;
      if(((i+1)%8) === 5 && answers[i] === 2) count_two += 1;
      if(((i+1)%8) === 6 && answers[i] === 4) count_two += 1;
      if(((i+1)%8) === 7 && answers[i] === 2) count_two += 1;
      if(((i+1)%8) === 0 && answers[i] === 5) count_two += 1;
      if(((i+1)%10) === 1 && answers[i] === 3) count_three += 1;
      if(((i+1)%10) === 2 && answers[i] === 3) count_three += 1;
      if(((i+1)%10) === 3 && answers[i] === 1) count_three += 1;
      if(((i+1)%10) === 4 && answers[i] === 1) count_three += 1;
      if(((i+1)%10) === 5 && answers[i] === 2) count_three += 1;
      if(((i+1)%10) === 6 && answers[i] === 2) count_three += 1;
      if(((i+1)%10) === 7 && answers[i] === 4) count_three += 1;
      if(((i+1)%10) === 8 && answers[i] === 4) count_three += 1;
      if(((i+1)%10) === 9 && answers[i] === 5) count_three += 1;
      if(((i+1)%10) === 0 && answers[i] === 5) count_three += 1;
    }    
    var answer = [];
    if(count_one >= count_two && count_one >= count_three){
      answer.push(1);
    }
    if(count_two >= count_one && count_two >= count_three){
      answer.push(2);      
    }
    if(count_three >= count_one && count_three >= count_two){
      answer.push(3);
    }
    return answer;
}

⏩ 추가학습