HomeAboutMeBlogGuest
© 2025 Sejin Cha. All rights reserved.
Built with Next.js, deployed on Vercel
📎
운영진을 위한 문서 모음/
🤧
주차별 액션 안내/
🌮
14~18주차/
💌
18주차 액션 포인트/임효성/
📔
회고의 사본/
📚
알고리즘 오답노트 LEVEL 1
📚

알고리즘 오답노트 LEVEL 1

Created
Jul 7, 2021
Language
Algorithm

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

문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬.

풀이

  1. 비교 연산 함수를 만든다.
  1. n번째 값이 같을 경우 string 자체를, 다를 경우 n번째 원소를 비교한다.
  1. 비교한 값으로 sort에 의해 위치가 결정된다.
💡
- compareStr은 비교만 하고 sort에 의해 위치를 바꾼다는 점. - 배열에서 n번째 값을 알고 싶은 것이 아닌, 그 결과값으로 정렬을 하는거라면 n번째 값 자체를 구할 필요는 없음. - if가 아닐 때 값이 return밖에 없다면 else 생략 가능.

참고 속성

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

sort 알고리즘

  • 버블정렬(Bubble Sort) - 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘. 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환함. O(n^2)
  • 장점 - 구현이 매우 간단하다.
  • 단점 - 최선, 최악의 경우 시간복잡도가 모두 O(N^2)이므로 매우 비효율적이다.
notion image
  • 선택정렬(Selection Sort) - 배열을 돌면서 가장 작은 값부터 옮김. O(n^2)
      • notion image
  • 병합정렬(Merge Sort) - 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법. O(n log n)
notion image

같은 숫자는 싫어

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

풀이

💡
not(!)을 사용하면 같은 숫자, 문자가 아닌 걸 고를 수 있음.

사용된 속성

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

2016년

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

풀이

  1. 요일 배열과 일수를 합한 배열을 만든다.
  1. 달을 일수로 치환해 일수의 합이 7로 나눴을 때, 나머지로 요일을 찾는다.
💡
나만의 배열을 만들어 문제를 해결해야 함.

약수의 합

정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요.

풀이

  1. 약수의 속성(0이 나오면 약수)을 파악한다.
  1. i(약수)의 합을 구한다.
💡
코드로 구현하기 편한 공식을 도출해낼 줄 알아야 함.

실패율

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

풀이

  1. 배열에서 중복값 개수를 구한다. 👉배열 중복 값 개수 구하기
  1. 실패율 구하는 공식을 구한다.
  1. sort()를 이용해 같은 값일 경우 작은 값을, 다른 값일 경우 큰 값을 반환한다.
💡
- 공식을 세우 전 예외처리가 되어 있어야 함. - 순서와 값이 모두 필요한 경우 두 가지 모두를 배열 안에 넣어 sort해야 함.

사용된 속성

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

비밀지도

네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.

풀이

  1. arr의 값을 비교하여 이진수로 변환한다.
  1. 값이 1이면 #을, 0이면 공백을 반환한다.
💡
- 비트 연산에서 1과 0을 OR로 비교하면 1과 0을 비교할 때 1을 반환함. - 10진수에서 다른 진수로 변환할 땐 toString()을 사용하여 변환하고자 하는 수를 넣어 사용 가능. 이때 앞의 0은 생략되기 때문에 padStart()라는 속성을 통해 자릿수만큼 0을 채워넣어야 함.

사용된 속성

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

다트게임

0~10의 정수와 문자 S, D, T, *, #로 구성된 문자열이 입력될 시 총점수를 반환하는 함수를 작성하라.

풀이

  1. for문을 이용해 dartResult의 길이만큼 각 character를 검사하도록 한다.
  1. 검사하려는 character가 0~9 사이의 숫자일 경우 다음 숫자가 0인지 한번 더 검사한다(10인지 확인하기 위해서)
  1. 10인 경우 temp에 10을 저장한 뒤 i를 높여준다(0 부분을 건너뛰기 위해서)
  1. 0이 아닌경우 해당 숫자를 그대로 temp에 저장한다.
  1. 숫자가 아닌 'S', 'D', 'T'인 경우 해당 값을 answer에 push한다.
  1. '#'일 경우 직전 값에 -1을 곱해준다.
  1. '*'일 경우 직전 값과 그 전 값을 2배로 만들어야 하기 때문에 해당 값에 2를 곱해준다.
  1. answer에 push 됐던 값들을 숫자형으로 변환해서 모두 더해준다.
💡
- 한 자리와 두 자리를 나눠서 생각해야 함. - 0으로 리셋수를 만들어 하나씩 더해나간다는 원리 잘 적용하기.

사용된 속성

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

크레인 인형뽑기 게임

0~10의 정수와 문자 S, D, T, *, #로 구성된 문자열이 입력될 시 총점수를 반환하는 함수를 작성하라.

풀이

  1. moves에 기반해 인형의 위치를 파악한다.
  1. 인형 위치를 파악할 때, 인형 변수에 값을 저장하고 값을 0으로 변경한다.
  1. 인형을 basket 배열에 담아 이전 값이랑 일치하면 제거하고 result에 2를 더함.
  1. 일치하지 않으면 인행을 basket 배열에 담는다.
💡
배열에서 [][]를 사용하면 가로, 세로에 기반한 위치를 파악할 수 있음.

사용된 속성

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

키패드 누르기

순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

풀이

  1. pos라는 1 ~ #까지를 좌표화한 객체를 생성한다.
  1. 현재 왼손과 오른손의 위치를 의미하는 lH, rH 변수를 각각 '*', '#'로 초기화한다.
  1. numbers의 길이만큼 for문으로 반복한다. 1, 4, 7(num%3 === 1)일 경우에는 L을 더해주고 lH의 위치를 갱신해준다. 3, 6, 9(num%3 === 0, 0은 제외)일 경우에는 R을 더해주고 rH의 위치를 갱신해준다. 이 두 경우가 아닐 경우 dis 함수를 이용해서 위치를 구한다.
  1. dis 함수 설명: 매개변수로 누르려는 수, 왼손의 현 위치, 오른손의 현 위치, 좌표, 왼손/오른손잡이 여부를 받는다. lD는 왼손 현 위치에서 목표점까지의 x축과 y축의 거리를 의미하고, rD는 오른손 현 위치에서 목표점까지의 x축과 y축의 거리를 의미한다. 만약 lD와 rD가 같다면 왼손잡이인지 오른손잡이인지 확인한다. 같지 않다면 D가 더 작은 손을 return한다.
  1. return된 결과가 L이라면 lH를 현 위치로 갱신하고, R이라면 rH를 현 위치로 갱신한다.
💡
- 키패드를 좌표화한 객체로 바꿀 수 있음. - 거리를 비교할 땐 숫자 크기로 비교하기.

사용된 속성

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

숫자 문자열과 영단어

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

풀이

  1. 숫자와 영어에 맞는 json을 만든다.
  1. 숫자임을 판별하는 함수를 만든다.
  1. 만약 숫자라면 해당 숫자를 result에 담는다.
  1. 숫자가 아니라면 json에 맞는 글자가 나올 때까지 더한 후 일치하는 값을 result에 담는다.
💡
json 형태로 담을 때 따옴표 모두 써주기.

체육복

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

풀이

  1. 여벌 체육복이 있는 학생이 체육복을 잃어버릴 경우를 위해 중복을 제거한다.
  1. 앞뒤로 숫자를 가지고 있다면 해당 인덱스를 key에 저장한다.
  1. key를 제거한 후 체육복을 갖고 있지 않은 사람들을 반환한다.
💡
- key 값을 indexOf()로 저장해 자르는 방법이 있음. - [...setOrigin]을 통해 Set과 Array 사이 변환 가능.

직사각형

직사각형을 만드는 데 필요한 4개의 점 중 3개의 좌표가 주어질 때, 나머지 한 점의 좌표를 구하려고 합니다. 점 3개의 좌표가 들어있는 배열 v가 매개변수로 주어질 때, 직사각형을 만드는 데 필요한 나머지 한 점의 좌표를 return 하도록 solution 함수를 완성해주세요.

풀이

  1. reduce를 이용하여 축적된 값과 현재값을 x, y에 저장한다.
  1. 축적된 x와 y를 XOR 연산자를 통해 유일한 값을 도출한다.
  1. return으로 reduce 함수를 종료 후 해당 값을 반환한다.
💡
reduce로 축적된 값과 현재값을 모은다는 것이 핵심. reudce((acc, cur) ⇒ acc+ cur) 원리와 동일.

사용된 속성

  • reduce() - 배열의 각 요소에 대해 주어진 리듀서(reducer) 함수를 실행하고, 하나의 결과값을 반환.
  • XOR - 일치하는 값은 0을, 다른 값은 -1을 반환함. 이는 비트 연산자의 원리이기 때문에 a^a^b = b를 반환하는 성질을 갖고 있음.

소수 찾기

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

풀이

  1. n+1의 수를 가진 배열을 만들고 true로 채운다. (n개는 자연수이기 때문)
  1. 0과 1은 소수가 아니기 때문에 false로 변환한다.
  1. 에라토스테네스의 체의 의거해 자신을 제외한 배수는 모두 false로 변환한다.
  1. true를 가진 개수를 구한다.
 
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;
}
alert('a'.localeCompare('b')); // -1
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);
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);
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;
}
let text = '';

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

console.log(text);
// expected output: "012456789"
//달력을 볼 수 있는 경우
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];
}
//내 풀이
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
}
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])
}
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;
}
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;
    
    
}
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;
        }
    }
}
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;
}
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)
}
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
}
function solution(v) {
    return v.reduce((acc,cur) =>{
        const [accX, accY] = acc;
        const [curX, curY] = cur;
        return [accX ^ curX, accY ^ curY];
    })
}
const array1 = [1, 2, 3, 4];
const reducer = (accumulator, currentValue) => accumulator + currentValue;

// 1 + 2 + 3 + 4
console.log(array1.reduce(reducer));
// expected output: 10
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;
}