알고리즘 오답노트 LEVEL 1

문자열 내 마음대로 정렬하기

function compareStr(s1, s2) {
    if(s1 === s2) return 0;
    if(s1 > s2) return 1;
    return -1;
}

function solution(strings, n) {
    
    const sorted = strings.sort((w1, w2) => {
        if (w1[n] === w2[n]) {
            return compareStr(w1, w2);
        }
        return compareStr(w1[n], w2[n]);
    });
    
    return sorted;
}

풀이

1. 비교 연산 함수를 만든다.

2. n번째 값이 같을 경우 string 자체를, 다를 경우 n번째 원소를 비교한다.

3. 비교한 값으로 sort에 의해 위치가 결정된다.

참고 속성

• localeCompare - 문자열과 문자열을 비교.

alert('a'.localeCompare('b')); // -1

sort 알고리즘

• 버블정렬(Bubble Sort) - 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘. 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환함. O(n^2)

• 장점 - 구현이 매우 간단하다.

• 단점 - 최선, 최악의 경우 시간복잡도가 모두 O(N^2)이므로 매우 비효율적이다.

let nums = [1, 3, 5, 6, 2, 0, 8, 9, 7, 4];

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1; j++) {
			// 화살표 방향을 바꾸면 역순 가능
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

bubbleSort(nums);
console.log(nums);

• 선택정렬(Selection Sort) - 배열을 돌면서 가장 작은 값부터 옮김. O(n^2)

let nums = [1, 3, 5, 6, 2, 0, 8, 9, 7, 4];

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (i !== minIndex) {
      let temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
}

selectionSort(nums);
console.log(nums);

• 병합정렬(Merge Sort) - 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법. O(n log n)

function mergeSort(arr) {
  if (arr.length === 1) {
    return arr;
  }
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle, arr.length);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }

  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }

  return result;
}

let nums = [1, 3, 5, 6, 2, 0, 8, 9, 7, 4];

console.log(mergeSort(nums));
> [
  0, 1, 2, 3, 4,
  5, 6, 7, 8, 9
  ]

같은 숫자는 싫어

function solution(arr) {
    
    let answer =[];
    
    for(let i=0; i<arr.length; i++) {
        if(arr[i] !== arr[i+1]){
            answer.push(arr[i])
        }
    }
    return answer;
}

풀이

사용된 속성

• continue - 현재 또는 레이블이 지정된 루프의 현재 반복에서 명령문의 실행을 종료하고 반복문의 처음으로 돌아가여 루프문의 다음 코드를 실행.

let text = '';

for (let i = 0; i < 10; i++) {
  if (i === 3) {
    continue;
  }
  text = text + i;
}

console.log(text);
// expected output: "012456789"

2016년

//달력을 볼 수 있는 경우
function solution(a, b) {
    a -= 1;
    const dayTable = ['SUN','MON','TUE','WED','THU','FRI','SAT'];
    const monthStartingDay = [5, 1, 2, 5, 0, 3, 5, 2, 4, 6, 2, 4];
    return dayTable[(monthStartingDay[a] + b - 1) % 7];
}

//달력을 볼 수 없는 경우
function getDayName(a,b){
  const dayList = ['FRI','SAT','SUN','MON','TUE','WED','THU'];
  const monthArr = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
  const daySum;
  if(a < 2) {
    daySum = b - 1;
  } else {
    daySum = monthArr.slice(0, a - 1).reduce((a, b) => a + b) + b - 1;
  }
    return dayList[daySum % 7];
}

풀이

1. 요일 배열과 일수를 합한 배열을 만든다.

2. 달을 일수로 치환해 일수의 합이 7로 나눴을 때, 나머지로 요일을 찾는다.

약수의 합

//내 풀이
function solution(n) {
    let answer = 0;
    
    const divisor = [];
    
    for(let i = 1; i <= n; i++){
        if(n%i === 0){
            divisor.push(i);
        }
    }
    
    divisor.forEach((num)=> {
        answer += num
    });  
    return answer;
}

//참고 풀이
function solution(num) {
    let sum = 0;
    for (let i = 1; i <= num; i++) {
        if (num % i === 0) sum += i
    }
    return sum
}

풀이

1. 약수의 속성(0이 나오면 약수)을 파악한다.

2. i(약수)의 합을 구한다.

실패율

function solution(N, stages) {    
    
    const result = {};
    stages.forEach(x => {result[x] = (result[x] || 0)+1}); 

    let failRate = [];
    let reachedCnt = stages.length;
    
    for(let i=1; i<=N; i++) {
        const curStageCnt = result[i] || 0;
        const rate = curStageCnt / reachedCnt;
        failRate.push( [rate,i] );
        reachedCnt -= curStageCnt;
    }
    
    failRate.sort((r1, r2) => {
        if(r1[0] === r2[0]) {
            return r1[1] - r2[1];
        }
        return r2[0] - r1[0];
    })
    return failRate.map(elem => elem[1])
}

풀이

1. 배열에서 중복값 개수를 구한다. 👉배열 중복 값 개수 구하기

2. 실패율 구하는 공식을 구한다.

3. sort()를 이용해 같은 값일 경우 작은 값을, 다른 값일 경우 큰 값을 반환한다.

사용된 속성

• map() - 배열 내의 모든 요소 각각에 대하여 주어진 함수를 호출한 결과를 모아 새로운 배열을 반환. forEach는 요소 각각을 호출하는 기능만 담당.

const array1 = [1, 4, 9, 16];

// pass a function to map
const map1 = array1.map(x => x * 2);

console.log(map1);
// expected output: Array [2, 8, 18, 32]

비밀지도

function hashConverter(line) {
    const arr =[];
    for(let i=0; i<line.length; i++) {
        line[i] === "1" ? arr.push("#") : arr.push(" ");
    }
    return arr.join('');
}

function solution(n, arr1, arr2) {
    var answer = [];
    
    for(let i =0; i<n; i++) {
        const line = (arr1[i]|arr2[i]).toString(2).padStart(n,'0');
        answer.push(hashConverter(line))
    }
    
    return answer;
}

풀이

1. arr의 값을 비교하여 이진수로 변환한다.

2. 값이 1이면 #을, 0이면 공백을 반환한다.

사용된 속성

• toString() - 문자열을 반환하는 object의 대표적인 방법.

• padStart() - 현재 문자열의 시작을 다른 문자열로 채워, 주어진 길이를 만족하는 새로운 문자열을 반환. 채워넣기는 대상 문자열의 시작(좌측)부터 적용함.

다트게임

const solution = dartResult => {
    let temp = 0;
    let answer = [];
    let sum = 0;
    
    for(let i = 0; i < dartResult.length; i++) {
        if(dartResult[i] >= 0 && dartResult[i] <= 9) {
            if(dartResult[i] == 1 && dartResult[i+1] == 0) {
                temp = 10;
                i++;
            } else {
                temp = dartResult[i];
            }
        }
        else if(dartResult[i] === 'S') {
            answer.push(temp);
        }
        else if(dartResult[i] === 'D') {
            answer.push(Math.pow(temp, 2));
        }
        else if(dartResult[i] === 'T'){
            answer.push(Math.pow(temp, 3));
        }
        else if(dartResult[i] === '#') {
           answer[answer.length-1] *= -1;
        }
        else if(dartResult[i] === '*') {
            answer[answer.length-1] *= 2;
            if(answer.length>=2){
                        answer[answer.length-2]*=2;
                    }
        }
    }

    for(let j = 0; j < answer.length; j++) {
        sum += Number(answer[j]);
    }
    
    return sum;
    
    
}

풀이

1. for문을 이용해 dartResult의 길이만큼 각 character를 검사하도록 한다.

2. 검사하려는 character가 0~9 사이의 숫자일 경우 다음 숫자가 0인지 한번 더 검사한다(10인지 확인하기 위해서)

3. 10인 경우 temp에 10을 저장한 뒤 i를 높여준다(0 부분을 건너뛰기 위해서)

4. 0이 아닌경우 해당 숫자를 그대로 temp에 저장한다.

5. 숫자가 아닌 'S', 'D', 'T'인 경우 해당 값을 answer에 push한다.

6. '#'일 경우 직전 값에 -1을 곱해준다.

7. '*'일 경우 직전 값과 그 전 값을 2배로 만들어야 하기 때문에 해당 값에 2를 곱해준다.

8. answer에 push 됐던 값들을 숫자형으로 변환해서 모두 더해준다.

사용된 속성

• Math.pow() - base 에 exponent를 제곱한 값을 반환.

console.log(Math.pow(7, 3));
// expected output: 343

크레인 인형뽑기 게임

function solution(board, moves) {
    
    const basket = [];
    let result = 0;
    
    moves.forEach(order =>{
        const doll = pickup(board, order -1);
        if(doll) {
            if(basket[basket.length -1] === doll){
                basket.pop();
                result +=2;
            }
            else {
                basket.push(doll);
            }
        }
    });
    return result;
}

function pickup(board, order) {
    for(let i = 0; i<board.length; i++) {
        if(board[i][order] !== 0) {
            const doll = board[i][order];
            board[i][order] = 0;
            return doll;
        }
    }
}

풀이

1. moves에 기반해 인형의 위치를 파악한다.

2. 인형 위치를 파악할 때, 인형 변수에 값을 저장하고 값을 0으로 변경한다.

3. 인형을 basket 배열에 담아 이전 값이랑 일치하면 제거하고 result에 2를 더함.

4. 일치하지 않으면 인행을 basket 배열에 담는다.

사용된 속성

• pop() - 배열에서 마지막 요소를 제거하고 그 요소를 반환.

const plants = ['broccoli', 'cauliflower', 'cabbage', 'kale', 'tomato'];

console.log(plants.pop());
// expected output: "tomato"

console.log(plants);
// expected output: Array ["broccoli", "cauliflower", "cabbage", "kale"]

키패드 누르기

const pos = {
        1: [0, 0], 2: [0, 1], 3: [0, 2],
        4: [1, 0], 5: [1, 1], 6: [1, 2],
        7: [2, 0], 8: [2, 1], 9: [2, 2],
        '*': [3, 0], 0: [3, 1], '#': [3, 2]
    };

function middleDecider(num, lH, rH, hand){
    const leftPos = Math.abs(pos[lH][0] - pos[num][0]) + Math.abs(pos[lH][1] - pos[num][1]);
    const rightPos = Math.abs(pos[rH][0] - pos[num][0]) + Math.abs(pos[rH][1] - pos[num][1]);

    if(leftPos === rightPos) {
        return hand === 'left' ?  'L' : 'R';
    }
    else {
        return leftPos < rightPos ? 'L' : 'R';
    }
}

function solution(numbers, hand) {
       
    let lH = '*', rH = '#';
    let result =''
    for(let num of numbers){
        if(num %3 === 1) {
            result += 'L';
            lH = num;
        }
        else if (num !== 0 && num %3 ===0) {
            result += 'R';
            rH = num;
        }
        else {
            result += middleDecider(num, lH, rH, hand)
            result[result.length -1] === 'L' ? lH = num : rH = num;
        }
    }
    return result;
}

풀이

1. pos라는 1 ~ #까지를 좌표화한 객체를 생성한다.

2. 현재 왼손과 오른손의 위치를 의미하는 lH, rH 변수를 각각 '*', '#'로 초기화한다.

3. numbers의 길이만큼 for문으로 반복한다. 1, 4, 7(num%3 === 1)일 경우에는 L을 더해주고 lH의 위치를 갱신해준다. 3, 6, 9(num%3 === 0, 0은 제외)일 경우에는 R을 더해주고 rH의 위치를 갱신해준다. 이 두 경우가 아닐 경우 dis 함수를 이용해서 위치를 구한다.

4. dis 함수 설명: 매개변수로 누르려는 수, 왼손의 현 위치, 오른손의 현 위치, 좌표, 왼손/오른손잡이 여부를 받는다. lD는 왼손 현 위치에서 목표점까지의 x축과 y축의 거리를 의미하고, rD는 오른손 현 위치에서 목표점까지의 x축과 y축의 거리를 의미한다. 만약 lD와 rD가 같다면 왼손잡이인지 오른손잡이인지 확인한다. 같지 않다면 D가 더 작은 손을 return한다.

5. return된 결과가 L이라면 lH를 현 위치로 갱신하고, R이라면 rH를 현 위치로 갱신한다.

사용된 속성

• Math.abs() - 주어진 숫자의 절대값을 반환함.

function difference(a, b) {
  return Math.abs(a - b);
}

console.log(difference(3, 5));
// expected output: 2

숫자 문자열과 영단어

function solution(s) {
    let result = '';
    const nums = {
        'zero': '0',
        'one': '1',
        'two': '2',
        'three': '3',
        'four': '4',
        'five': '5',
        'six': '6',
        'seven': '7',
        'eight': '8',
        'nine': '9'
    }
    let nowStr = '';
    for (let i = 0; i < s.length; i++) {
        if (isNum(s[i])) result += s[i];
        else {
            nowStr += s[i];
            if (nums[nowStr]) {
                result += nums[nowStr];
                nowStr = '';
            }
        }
    }
    return +result;
}

const isNum = s => {
    const pattern = '^[0-9]+$';
    if (s.match(pattern)) return true;
    else return false;
}

//새로운 풀이
function solution(s) {
     let numbers = ["zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"];
    
    let answer = s;
    
    for(let i=0; i<numbers.length; i++) {
        let arr = answer.split(numbers[i]);
        answer = arr.join(i)
    }
    return Number(answer)
}

풀이

1. 숫자와 영어에 맞는 json을 만든다.

2. 숫자임을 판별하는 함수를 만든다.

3. 만약 숫자라면 해당 숫자를 result에 담는다.

4. 숫자가 아니라면 json에 맞는 글자가 나올 때까지 더한 후 일치하는 값을 result에 담는다.

체육복

function removeDuplicate(origin, other){
    const setOrigin = new Set(origin);
    other.forEach(o => setOrigin.has(o)&& setOrigin.delete(o));
    return [...setOrigin];
}

function solution(n, lost, reserve) {
  	const lostStudent = removeDuplicate(lost, reserve);
    const reserveStudent = removeDuplicate(reserve, lost);
    
    for(let i of reserveStudent){
        let key = lostStudent.includes(i-1) ? lostStudent.indexOf(i-1) : lostStudent.indexOf(i+1);
        if (key != -1){
            lostStudent.splice(key,1);
        }
    }    
    return n-lostStudent.length
}

풀이

1. 여벌 체육복이 있는 학생이 체육복을 잃어버릴 경우를 위해 중복을 제거한다.

2. 앞뒤로 숫자를 가지고 있다면 해당 인덱스를 key에 저장한다.

3. key를 제거한 후 체육복을 갖고 있지 않은 사람들을 반환한다.

직사각형

function solution(v) {
    return v.reduce((acc,cur) =>{
        const [accX, accY] = acc;
        const [curX, curY] = cur;
        return [accX ^ curX, accY ^ curY];
    })
}

풀이

1. reduce를 이용하여 축적된 값과 현재값을 x, y에 저장한다.

2. 축적된 x와 y를 XOR 연산자를 통해 유일한 값을 도출한다.

3. return으로 reduce 함수를 종료 후 해당 값을 반환한다.

사용된 속성

• reduce() - 배열의 각 요소에 대해 주어진 리듀서(reducer) 함수를 실행하고, 하나의 결과값을 반환.

const array1 = [1, 2, 3, 4];
const reducer = (accumulator, currentValue) => accumulator + currentValue;

// 1 + 2 + 3 + 4
console.log(array1.reduce(reducer));
// expected output: 10

• XOR - 일치하는 값은 0을, 다른 값은 -1을 반환함. 이는 비트 연산자의 원리이기 때문에 a^a^b = b를 반환하는 성질을 갖고 있음.

소수 찾기

function solution(n) {
    const sieve = new Array(n+1).fill(true);
    sieve[0] = false, sieve[1] = false;
    
    for(let i=2; i<sieve.length; i++) {
        if(sieve[i] === false) {
            continue;
        }
        for(let j=i+i; j<sieve.length; j+=i) {
            sieve[j] = false;
        }
    }
    return sieve.filter(num => num === true).length;
}

풀이

1. n+1의 수를 가진 배열을 만들고 true로 채운다. (n개는 자연수이기 때문)

2. 0과 1은 소수가 아니기 때문에 false로 변환한다.

3. 에라토스테네스의 체의 의거해 자신을 제외한 배수는 모두 false로 변환한다.

4. true를 가진 개수를 구한다.