Keep Going

1. 문제

단 한명의 선수를 제외하고는 모든 선수가 마라톤을 완주했다. 

참여 선수의 이름이 담긴 배열 participant

완주한 선수의 이름이 담긴 배열 completion

참가자 중에는 동명이인이 있을 수도 있다. 

입력예제 | participant ["leo", "kiki", "eden"], completion ["eden", "kiki"]

출력예제 | "leo"

2. 해시 알고리즘 생각하지 않고 풀었던 코드

const solution = (participant, completion) => {
    participant.sort();
    completion.sort();
    for (let i = 0; i < participant.length; i++) {
        if (participant[i] !== completion[i])
            return participant[i];
    }
}

const participant = ["mislav", "stanko", "mislav", "ana"];
const completion = ["stanko", "ana", "mislav"];
console.log(solution(participant, completion));

3. 해시 알고리즘으로 푼 코드

const solution = (participant, completion) => {
    let answer = '';

    let map1 = new Map();
    let map2 = new Map();

    for (let x of participant) {
        if (map1.has(x)) { map1.set(x, map1.get(x) + 1) }
        else { map1.set(x, 1) }
    };

    for (let x of completion) {
        if (map2.has(x)) { map2.set(x, map2.get(x) + 1) }
        else { map2.set(x, 1) }
    };

    for (let [key, value] of map1) {
        if (!map2.has(key) || map2.get(key) !== value) {
            answer = key;
        }
    }
    return answer;
}

const participant = ["mislav", "stanko", "mislav", "ana"];
const completion = ["stanko", "ana", "mislav"];
console.log(solution(participant, completion));

해시 알고리즘으로 푸는 게 효율성이 더 좋다. 

해시, 투포인터, 슬라이딩 윈도우 알고리즘을 이용해서 풀어보는 문제

1. 문제

주어지는 문자열에서 아나그램이 되는 부분 문자열의 개수 구하기.

부분문자열은 연속된 문자열이다. 

입력예제 | 문자열 bacaAacba, 부분 문자열 abc

출력예제 | 3 

2. 접근방법

주어진 부분문자열과 문자열의 일부(부분문자열의 length-1)를 객체로 바꾼다.

포인터 지점을 찍어놓고 for문으로 한칸씩 이동하면서 부분문자열의 length만큼의 자리를 비교한다.

아나그램이 아닐 경우 포인터를 다음 인덱스로 이동시키고,

아나그램일 경우 answer를 카운팅하고 다음인덱스로 이동시킨다. 

3. 풀이방법

1) answer에 개수를 카운팅 해주기위해서 0으로 세팅한다. 

let answer = 0;

2) 찾아야하는 아나그램이 되는 연속된 부분문자열이기 때문에 주어진 부분문자열의 알파벳과 값을 객체형태로 가지고 있어야한다. map 객체를 사용한다. 

let map1 = new Map();
let map2 = new Map();

for (let x of t) {
	if (map2.has(x)) {
    	map2.set(x, map2.get(x) + 1);
    } else {
    	map2.set(x, 1);
    }
}

3) 부분문자열의 크기만큼 슬라이딩 윈도우 기본 세팅을 해준다. 

let len = t.length -1;

주어진 문자열 중에서 가장 앞에 2개의 문자만 객체로 세팅한다.

length를 부문분자열의 크기만큼 하지않고 -1을 해주는 이유는

부분문자열의 크기가 3일때, 2는 고정으로 계속 두고 한자리만 바꾸면서 비교를 진행해야하기 때문이다. 

for (let i = 0; i < len; i++) {
	if (map1.has(s[i])) {
    	map1.set(s[i], map1.get(s[i] + 1);
    } else {
    	map1.set(s[i], 1);
    }
}

4) for문으로 슬라이딩 윈도우로 한칸씩 이동하면서

1개 추가해서 3개씩 비교하고(부분문자열의 length) 아나그램이 아닐 경우 빼주고 반복한다. 

비교 이후에 빼주는 작업을 하기위해서 투 포인터 변수 작성해준다.

let lt = 0;
rt는 for 반복문 안에 선언

for (let rt = len; rt < s.length; rt++) {
    if (map1.has(s[rt])) {
      map1.set(s[rt], map1.get(s[rt]) + 1);
    } else {
      map1.set(s[rt], 1);
    }

	// 비교
    if (compareMaps(map1, map2)) {
      answer++;
    }
    
    // 비교 이후에 왼쪽 포인터 빼주는 작업 
    map1.set(s[lt], map1.get(s[lt]) - 1); // 기존 값보다 1작게 가져와서 다시 세팅
    if (map1.get(s[lt]) === 0) {
      map1.delete(s[lt]);
    }
    lt++;
}

5) 비교하는 함수 작성

부분문자열의 개수가 같은지 확인

key값이 같은지, value 값이 같은지 확인

const compareMaps = (map1, map2) => {
	if (map1.size !== map2.size) {
    	return false;
    }
    for (let [key, value] of map1) {
    	if (!map2.has(key) || map2.get(key) !== value) {
        	return false;
        }
    }
    retrun true; // 모두 아니면 같은 것으므로 true 반환
}

4. 코드

const solution = (s, t) => {
  // 아나그램이 되는 연속된 부분문자열 개수
  let answer = 0;

  let map1 = new Map(); // 문자열을 map 객체로
  let map2 = new Map(); // 부분문자열을 map 객체로

  // 찾아야하는 연속된 부분문자열을 map객체로 만듬
  for (let x of t) {
    if (map2.has(x)) {
      map2.set(x, map2.get(x) + 1);
    } else {
      map2.set(x, 1);
    }
  }

  // 슬라이딩 윈도우 할 때 길이가 3이면 2개를 먼저 세팅해 놓는 것
  let len = t.length - 1;

  for (let i = 0; i < len; i++) {
    if (map1.has(s[i])) {
      map1.set(s[i], map1.get(s[i]) + 1);
    } else {
      map1.set(s[i], 1);
    }
  }

  let lt = 0;

  // 슬라이딩 윈도우이기 때문에 rt는 len길이를 시작점으로 세팅
  // 추가해서 3개로 맞춰주고
  for (let rt = len; rt < s.length; rt++) {
    if (map1.has(s[rt])) {
      map1.set(s[rt], map1.get(s[rt]) + 1);
    } else {
      map1.set(s[rt], 1);
    }

    // 3개이니까 이제 비교가능
    if (compareMaps(map1, map2)) {
      answer++;
    }

    // 비교 이후에 왼쪽 포인터 빼주는 작업 
    map1.set(s[lt], map1.get(s[lt]) - 1); // 기존 값보다 1작게 가져와서 다시 세팅
    if (map1.get(s[lt]) === 0) {
      map1.delete(s[lt]);
    }
    lt++;
  }
  return answer;
}

const compareMaps = (map1, map2) => {
  if (map1.size !== map2.size) { // 1. 개수가 같은지 확인
    return false;
  }
  for (let [key, value] of map1) { // 2. key 값이 같은지 확인
    if (!map2.has(key) || map2.get(key) !== value) { // 3. value 값이 같은지 확인
      return false;
    }
  }
  return true;
}

const str1 = "bacaAacba";
const str2 = "abc";
console.log(solution(str1, str2));

문제

5명의 학생이 주어질 때 각 학생이 받은 점수의 평균을 구하여 기준에 따라 학점을 부여

조건 : 자기자신을 평가한 점수가 유일한 최고점 또는 유일한 최저점이라면, 그 점수는 제외하고 평균을 구한다. 

풀이

평균을 먼저 구하고, 학점을 구한다. 각 행에 평균을 구해야 할 점수가 들어있다. 

통과하지못한 코드

const solution = (scores) => {
  let sum = 0;

  let sumArr = [];
  let scoreArr = [];
  let studentScoreArr = [];
  let len;

  let answer = '';

  // 배열 가공
  for (let i = 0; i < scores.length; i++) {
    studentScoreArr = [];
    for (let j = 0; j < scores.length; j++) {
      studentScoreArr.push(scores[j][i]);
    }
    scoreArr.push(studentScoreArr);
  }

  // 점수 가공
  for (let i = 0; i < scores.length; i++) {
    sum = 0;
    len = scoreArr[i].length;
    for (let j = 0; j < scores.length; j++) {
      let findIdx = scoreArr.indexOf(scoreArr[i]);
      let findCurrentIdx = scoreArr[i].indexOf(scoreArr[i][j]);

      if (findIdx === findCurrentIdx) {

        const myScore = scoreArr[i][j];
        const dubCheck = isDuplicate(scoreArr[i]);

        if (dubCheck) {
          if (Math.max(...scoreArr[i]) === myScore || Math.min(...scoreArr[i]) === myScore) {
            let myIdx = scoreArr[i].indexOf(myScore);
            console.log(myIdx);
            scoreArr[i].splice(myIdx, 1, 0);
            len--;
          } else {
            sum += scoreArr[i][j];
          }
        } else if (Math.max(...scoreArr[i]) === myScore || Math.min(...scoreArr[i]) === myScore) {
          let myIdx = scoreArr[i].indexOf(myScore);
          scoreArr[i].splice(myIdx, 1, 0);
          len--;
        } else {
          sum += scoreArr[i][j]
        }
      } else {
        sum += scoreArr[i][j];
      }
    }
    console.log(len);
    sumArr.push(sum / len);
  }

  // 학점 계산
  for (let i = 0; i < sumArr.length; i++) {
    if (sumArr[i] >= 90) {
      answer += 'A';
    } else if (90 > sumArr[i] && sumArr[i] >= 80) {
      answer += 'B';
    } else if (80 > sumArr[i] && sumArr[i] >= 70) {
      answer += 'C';
    } else if (70 > sumArr[i] && sumArr[i] >= 50) {
      answer += 'D';
    } else {
      answer += 'F';
    }
  }
  return answer;
}

const isDuplicate = (arr) => {
  const isDup = arr.some(function (x) {
    return arr.indexOf(x) !== arr.lastIndexOf(x);
  });
  return isDup;
}

기본 테스트는 통과했는데 테스트 케이스 3개를 통과하지 못했다. 

통과한 코드

const solution = (scores) => {
  let answer = '';

  for (let i = 0; i < scores.length; i++) {
    let myScore = scores[i][i];
    let count = scores.length;

    let min = 101;
    let max = -1;
    let sum = 0;

    let flag = true;

    for (let j = 0; j < scores.length; j++) {
      let score = scores[j][i];

      if (i !== j && myScore === score) { // 내점수가 아니고 동일한 점수가 아닐 때 
        flag = false;
      }

      min = Math.min(min, score);
      max = Math.max(max, score);
      sum += score;
    }

    if (flag && (min === myScore || max === myScore)) { // 내 점수일 때
      count--;
      sum -= myScore;
    }

    answer += findGrade(sum / count);
  }
  return answer;
}

const findGrade = (score) => {
  if (score >= 90) {
    return 'A';
  } else if (90 > score && score >= 80) {
    return 'B';
  } else if (80 > score && score >= 70) {
    return 'C';
  } else if (70 > score && score >= 50) {
    return 'D';
  } else {
    return 'F';
  }
}

문제

숫자의 일부 자릿수가 영단어로 바뀌어졌거나, 혹은 바뀌지 않고 그대로인 문자열 s가 매개변수로 주어진다. s가 의미하는 원래 숫자를 return 하도록 solution 함수를 완성하라.

입력예제 | "one4seveneight"

출력예제 | 1478

처음 코드(실패)

const solution = (s) => {
  const numStr = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine'];
  const num = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];

  let answer = s;

  for (let i = 0; i < numStr.length; i++) {
    let arr = answer.split(numStr[i]);

    if (arr.length > 1) {
      let idx = numStr.indexOf(numStr[i]);
      arr.splice(1, 0, num[idx]);
      answer = arr.join(i);
    }
  }
  let answer2 = answer.split('');

  let result = answer2.reduce((acc, cur, idx, arr) => {
    if (arr.indexOf(cur) === idx) acc.push(cur);
    return acc;
  }, []);

  return Number(result.join(''));
}

처음에는 이렇게 풀었는데, 테스트케이스만 보고 중복제거를 하면된다고 생각했는데, 하고보니 주어지는 문자열에 중복이 있을 수도 있는데 그것마저 없애는 코드가 되었다. 다시 새로 짜야했다. 

다른풀이

const solution = (s) => {
  let answer = 0;

  s = s.replace(/one/g, '1');
  s = s.replace(/two/g, '2');
  s = s.replace(/three/g, '3');
  s = s.replace(/four/g, '4');
  s = s.replace(/five/g, '5');
  s = s.replace(/six/g, '6');
  s = s.replace(/seven/g, '7');
  s = s.replace(/eight/g, '8');
  s = s.replace(/nine/g, '9');
  s = s.replace(/zero/g, '0');

  console.log(s);
  return Number(s);
}

다른풀이

const solution = (s) => {
  let numbers = ["zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"];

  for (let i = 0; i < numbers.length; i++) {
    let arr = s.split(numbers[i]);
    s = arr.join(i);
  }

  return Number(s);
}

문제

같은 종류의 폰켓몬은 같은 번호를 가지고있다. 

최대한 다양한 종류의 폰켓몬을 가지길 원한다. 

최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려고 한다. 

N마리의 폰켓몬 종류 번호가 담긴 배열 nums가 주어질 때,

N/2마리의 폰켓몬을 선택하는 방법 중

가장 많은 종류의 포켓몬을 선택하는 방법을 찾아

폰켓몬 종류 번호의 개수를 return

자연수

양의 정수, 사물의 개수를 셀 때 쓰이는 수여서 가장 '자연스러운 수' 

코드

const solution = (nums) => {
  const selectNum = nums.length / 2;

  const possibleSelect = nums.reduce((acc, cur, idx, origin) => {
    if (origin.indexOf(cur) === idx) acc.push(cur);
    return acc;
  }, []);

  return possibleSelect.length >= selectNum ? selectNum : possibleSelect.length;
}

중복 제거를 먼저해주고, 개수를 찾아주면 되는 문제였다. 

reduce를 이용해서 중복제거를 해주었는데, 중복된 값을 허용하지 않는 Set 객체를 이용하면 더 간단하게 코드를 작성할 수 있었다. 

다른사람의 풀이

function solution(nums) {
  const max = nums.length / 2;
  const arr = [...new Set(nums)];

  return arr.length > max ? max : arr.length
}

문제

어떤 정수들이 있다. 이 정수들의 절댓값을 차례대로 담은 정수 배열에서, 실제 정수들의 합을 구하여 return해라

수학개념

절댓값(absolute value)

: 어떤 값을 양수로 만들어주기 위한 장치

정수

: 양의정수, 0, 음의 정수의 총칭

코드

const solution = (absolutes, signs) => {
  let answer = absolutes.map((num, idx) => signs[idx] ? num : parseInt(-num)).reduce((a, b) => a + b);
  return answer;
}

문제

정수를 담고 있는 배열 arr의 평균값을 return하는 함수, solution을 완성해라

에러난 코드

const average = (arr) => {
  let answer = 0;

  for (let i of arr) {
    answer += i;
  }

  return answer/arr.length;
}

문제에서 함수 solution을 작성하라고 했는데 나혼자 함수명을 따로 지어버렸다....안될리가 없는데 왜 안되지 싶었네.. 사소한 실수 하지않도록 하자.

코드

const solution = (arr) => {
  let answer = 0;

  for (let i of arr) {
    answer += i;
  }

  return answer/arr.length;
}

완전탐색으로 해결해야하는 문제 -> 조합을 이용

4Combination3 = 4C3

4개 중에 3개씩 선택할 때 나올 수 있는 모든 조합을 구한다. 이 때, 조합의 순서는 상관이 없다. 순서가 바뀌어도 같은 구성이기 때문에 하나의 조합으로 취급한다. 

소수 

: 1과 자기 자신만을 약수로 갖는 수, 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수

처음 시도한 방법

조합으로 모든 경우의 수 배열로 찾아서 다 더한다음에 소수판별할 생각이었다. -> 실패

조합을 이용하기

서로 다른 n개의 물건에서 순서를 생각하지않고 r개를 택할 때, n개에서 r를 택하는 조합 -> nCr

5개 중에서 3개를 더하는 조합 5C3 = 5*4*3 /3*2*1 = 10가지

배열의 처음부터 하나씩 고정하면서 뒤의 나머지 배열에 대해서 조합을 구한다. 

코드

const solution = (nums) => {
  let answer = 0;
  const len = nums.length;

  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      for (let k = j + 1; k < len; k++) {
        const sum = nums[i] + nums[j] + nums[k];
        if (isPrime(sum)) answer++;
      }
    }
  }
  return answer;
}

const isPrime = (sum) => {
  for (let i = 2; i < sum; i++)
    if (sum % i === 0) return false;
  return true;
}