TIL. 알고리즘 문제풀이

1. 보이는 학생

문제 설명

선생님이 N(1<=N<=1000)명의 학생을 일렬로 세웠습니다. 일렬로 서 있는 학생의 키가 앞에 서부터 순서대로 주어질 때, 맨 앞에 서 있는 선생님이 볼 수 있는 학생의 수를 구하는 프로그 램을 작성하세요. (앞에 서 있는 사람들보다 크면 보이고, 작거나 같으면 보이지 않습니다.)

▣ 입력설명
첫 줄에 정수 N이 입력된다. 그 다음줄에 N명의 학생의 키가 앞에서부터 순서대로 주어진다.

▣ 출력설명
선생님이 볼 수 있는 최대학생수를 출력한다.

▣ 입출력 예

input	output
8 / 130 135 148 140 145 150 150 153	5
9 / 150, 153, 148, 160, 159, 165, 170, 161, 172	6

풀이

const printBigNum = (arr) => {
  let answer = [arr[0]]; // 1)
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > Math.max(...answer)) { // 2)
      answer.push(arr[i]);
    }
  }
  console.log('answer', answer); // [130, 135, 148, 150, 153]
  return answer.length;
};

const arr = [130, 135, 148, 140, 145, 150, 150, 153];
console.log(printBigNum(arr)); // 5

• 📌 Math.max() 메서드를 활용했다.
• 1) 받아온 배열값에서 가장 첫 값을 먼저 넣어준다.
• 2) for 문을 돌리면서 answer 배열 내에서 가장 큰 값보다 크다면 push 해준다.

✍️ solution

• 📌 +) 다른 풀이

function solution(arr) {
  let answer = 1,
    max = arr[0]; // 1)
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) { // 2)
      answer++;
      max = arr[i]; // 3)
    }
  }
  return answer;
}

let arr = [130, 135, 148, 140, 145, 150, 150, 153];
console.log(solution(arr));

• 1) 먼저 max 에 arr[0] 을 기본값으로 설정해준다.
• 2) arr[i] 값이 설정해둔 max 보다 클 경우 answer 카운터를 1씩 증가한다.
• 3) 동시에 max 값을 arr[i] 로 업데이트 해주면 Math.max() 를 쓰지 않고도 최댓값을 손쉽게 비교할 수 있다. 😀

---

2. 가위 바위 보

문제 설명

A, B 두 사람이 가위바위보 게임을 합니다. 총 N번의 게임을 하여 A가 이기면 A를 출력하고, B가 이기면 B를 출력합니다. 비길 경우에는 D를 출력합니다. 가위, 바위, 보의 정보는 1:가위, 2:바위, 3:보로 정하겠습니다. 예를 들어 N=5이면

회수	1	2	3	4	5
A의 정보	2	3	3	1	3
B의 정보	1	1	2	2	3
승자	A	B	A	B	D

두 사람의 각 회의 가위, 바위, 보 정보가 주어지면 각 회를 누가 이겼는지 출력하는 프로그램 을 작성하세요.

▣ 입력설명
첫 번째 줄에 게임 횟수인 자연수 N(1<=N<=100)이 주어집니다. 두 번째 줄에는 A가 낸 가위, 바위, 보 정보가 N개 주어집니다. 세 번째 줄에는 B가 낸 가위, 바위, 보 정보가 N개 주어집니다.

▣ 출력설명
각 줄에 각 회의 승자를 출력합니다. 비겼을 경우는 D를 출력합니다.

▣ 입출력 예

input	output
5 23313 11223	A B A B D

풀이

const solution = (arrA, arrB) => {
  let answer = [];
  for (let i = 0; i < arrA.length; i++) {
    if (arrA[i] === 1 && arrB[i] === 2) answer.push('B');
    if (arrA[i] === 1 && arrB[i] === 3) answer.push('A');
    if (arrA[i] === 2 && arrB[i] === 1) answer.push('A');
    if (arrA[i] === 2 && arrB[i] === 3) answer.push('B');
    if (arrA[i] === 3 && arrB[i] === 1) answer.push('B');
    if (arrA[i] === 3 && arrB[i] === 2) answer.push('A');
    if (arrA[i] === arrB[i]) answer.push('D');
  }
  return answer;
};

let arrA = [2, 3, 3, 1, 3];
let arrB = [1, 1, 2, 2, 3];
console.log(solution(arrA, arrB));

✍️ solution

function solution(a, b) {
  let answer = '';
  for (let i = 0; i < a.length; i++) {
    if (a[i] === b[i]) answer += 'D ';
    else if (a[i] === 1 && b[i] === 3) answer += 'A ';
    else if (a[i] === 2 && b[i] === 1) answer += 'A ';
    else if (a[i] === 3 && b[i] === 2) answer += 'A ';
    else answer += 'B ';
  }

  return answer;
}

let a = [2, 3, 3, 1, 3];
let b = [1, 1, 2, 2, 3];
console.log(solution(a, b));

• A가 이기는 상황을 제외한 나머지 상황에 전부 B를 추가해주면 더 깔끔하게 해결할 수 있다.😄

---

3. 점수계산

문제 설명

OX 문제는 맞거나 틀린 두 경우의 답을 가지는 문제를 말한다. 여러 개의 OX 문제로 만들어진 시험에서 연속적으로 답을 맞히는 경우에는 가산점을 주기 위해서 다음과 같이 점수 계산을 하기 로 하였다. 1번 문제가 맞는 경우에는 1점으로 계산한다. 앞의 문제에 대해서는 답을 틀리다가 답이 맞는 처음 문제는 1점으로 계산한다. 또한, 연속으로 문제의 답이 맞는 경우에서 두 번째 문제는 2점, 세 번째 문제는 3점, ..., K번째 문제는 K점으로 계산한다. 틀린 문제는 0점으로 계 산한다. 예를 들어, 아래와 같이 10 개의 OX 문제에서 답이 맞은 문제의 경우에는 1로 표시하고, 틀린 경 우에는 0으로 표시하였을 때, 점수 계산은 아래 표와 같이 계산되어, 총 점수는 1+1+2+3+1+2=10 점이다. 시험문제의 채점 결과가 주어졌을 때, 총 점수를 계산하는 프로그램을 작성하시오.

▣ 입력설명
첫째 줄에 문제의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 N개 문제의 채점 결과를 나 타내는 0 혹은 1이 빈 칸을 사이에 두고 주어진다. 0은 문제의 답이 틀린 경우이고, 1은 문제의 답이 맞는 경우이다.

▣ 출력설명
첫째 줄에 입력에서 주어진 채점 결과에 대하여 가산점을 고려한 총 점수를 출력한다.

▣ 입출력 예

input	output
101011100	7
101011100110	10

풀이

const solution = (arr) => {
  let answerArr = [];
  let x = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === 1) {
      x++;
      answerArr.push(x);
      if (arr[i - 1] === 1) {
        answerArr.pop();
        answerArr.push(x);
      }
    } else {
      answerArr.push(0);
      x = 0;
    }
  }
  return answerArr.reduce((a, b) => (a += b));
};

let arr = [1, 0, 1, 1, 1, 0, 0, 1, 1, 0];
console.log(solution(arr)); // 10

• 📌 reduce() 메서드를 활용했다.
• answerArr 배열에 필요한 값을 넣고 reduce 를 활용해서 값들을 합산 하여 결과를 출력했다.
• x 의 초기값을 0 으로 설정, 만약 이전 값이 1일 경우 x 값이 1씩 증가한다.
• 만약 이전 값이 0일 경우 다시 x 변수의 값이 0으로 초기화 된다.
• arr[i]===1 일 경우 값이 중복되어 저장되는 문제를 해결하기 위해 push 와 pop 을 사용했는데 더 깔끔한 방법을 찾아봐야겠다. 🧐

✍️ solution

function solution(arr) {
  let answer = 0,
    cnt = 0;
  for (let x of arr) {
    if (x === 1) {
      cnt++;
      answer += cnt;
    } else cnt = 0;
  }

  return answer;
}

let arr = [1, 0, 1, 1, 1, 0, 0, 1, 1, 0];
console.log(solution(arr));

📌 for of 문을 활용해서 더 간단하게 풀 수 있다.

• arr의 값이 1 일경우 cnt 를 올려줌과 동시에 answer 값에 합산한다.
• 만약 arr의 값이 0이라면 cnt 를 초기화 해준다. 원리는 위와 비슷하지만 따로 메서드를 사용하지 않고도 더 편리하게 풀 수 있다.😄

---

4. 등수 구하기

문제 설명

N(1<=N<=100)명의 학생의 국어점수가 입력되면 각 학생의 등수를 입력된 순서대로 출력하는 프로그램을 작성하세요.

▣ 입력설명
첫 줄에 N(3<=N<=1000)이 입력되고, 두 번째 줄에 국어점수를 의미하는 N개의 정수가 입력 된다. 같은 점수가 입력될 경우 높은 등수로 동일 처리한다. 즉 가장 높은 점수가 92점인데 92점이 3명 존재하면 1등이 3명이고 그 다음 학생은 4등이 된다.

▣ 출력설명
입력된 순서대로 등수를 출력한다.

▣ 입출력 예

input	output
87, 89, 92, 100, 76	4, 3, 2, 1, 5
92, 92, 92, 100, 76	2, 2, 2, 1, 5

풀이

const solution = (arr) => {
  let answer = []; // 1)
  for (let i = 0; i < arr.length; i++) { // 2)
    let a = 1;
    for (let j = 0; j < arr.length; j++) { // 3)
      if (arr[i] < arr[j]) {
        a++;
      }
    }
    answer.push(a);
  }
  return answer;
};

let arr = [87, 89, 92, 100, 76];
let arr1 = [92, 92, 92, 100, 76];
console.log(solution(arr)); // [4, 3, 2, 1, 5]
console.log(solution(arr1)); // [2, 2, 2, 1, 5]

• 1) answer 배열을 선언해준다.
• 2) for문 안에 변수 a 를 선언해준다.
• 3) 2중 for문을 돌려서 arr[i] 보다 arr[j] 가 클 때 변수 a를 증가시켜주고(등수를 올리고) 2중 for문이 끝난 시점에 answer 배열에 a를 추가한다.
• 점수가 중복될 경우에도 같은 등수로 적용한다.

✍️ solution

function solution(arr) {
  let n = arr.length; // 5
  let answer = Array.from({ length: n }, () => 1); // 1) 
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (arr[j] > arr[i]) answer[i]++; // 2)
    }
  }
  return answer;
}

let arr = [87, 89, 92, 100, 76];
console.log(solution(arr));

• 1) 리턴배열을 초기화 한다.
  n이 5 이므로, 배열의 길이가 0~4번까지 생긴다.
  () =>1은 1로 초기화
• 2) answer의 i번째 값을 ++ 해준다. (등수를 올려준다)

📌 Array.from 더 알아보기

Array.from() 메서드는 유사 배열 객체나 반복 가능한 객체(iterable object)를 얕게 복사해 새로운Array 객체를 만든다.
특정 길이의 배열을 만들어 연속된 수를 넣을 수도 있다.

👉 화살표 함수를 맵 함수로 사용해서 요소를 처리한다.
아래의 코드에서 length 길이와, 배열의 값이 되는 i 에 수를 더하거나 빼주면 원하는 범위의 연속된 수로 이루어진 배열이 만들어진다.

Array.from([1, 2, 3], x => x + x);
Array.from({length: 5}, (v, i) => i); // [0, 1, 2, 3, 4]
// [2, 4, 6]

❓ 어떻게 동작하는 걸까? 🧐

• {length: x} 는 x 길이의 유사 배열 객체를 생성한다.
  

• 유사 배열 객체에 length 값만 입력해 주었기 때문에 Array.from메서드가 값은 undefined로 채워진 배열을 반환해준다.
  

• 우리가 만들고자 하는 것은 연속된 수로 이루어진 인덱스(0~4) 값이 채워진 배열이다. 아래의 MDN 설명과 같이 map 메서드가 연결된 구조로 이해해보자.

  MDN-Arrat.from()
  Array.from()은 선택 매개변수인 mapFn를 가지는데, 배열(혹은 배열 서브클래스)의 각 요소를맵핑할 때 사용할 수 있습니다. 즉,Array.from(obj, mapFn, thisArg)는 중간에 다른 배열을 생성하지 않는다는 점을 제외하면Array.from(obj).map(mapFn, thisArg)와 같습니다. 이 특징은 typed arrays와 같은 특정 배열 서브클래스에서 중간 배열 값이 적절한 유형에 맞게 생략되기 때문에 특히 중요합니다.

• 따라서 Array.from 메서드에서도 인덱스를 참조하려면 두 개의 매개변수가 필요하다.
  Array.from({ length: 5 }, (x) => x);
  : 값만 매개변수로 받는다. 새로운 배열의 값은 기존 배열의 값
  Array.from({ length: 5 }, (x,i) => i)
  : 값과 인덱스를 매개변수로 받는다. 새로운 배열의 값은 기존 배열의 인덱스