Algorithm - Programmers Problems (week 1)

이소라·2022년 8월 8일
0

Algorithm

목록 보기
11/77

Problem(lev.1) : 신고 결과 받기

  • 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다.
    • 각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다.
    • 신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다.
    • 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다.
    • k번 이상 신고된 유저는 게시판 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송합니다.
      유저가 신고한 모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송합니다.

Solution

function solution(id_list, report, k) {
    const userMap = new Map();
    const badUserObj = {};
    const reportUserObj = {};
    id_list.forEach((id) => {
        userMap.set(id, []);
        badUserObj[id] = 0;
        reportUserObj[id] = 0;
    });
    for (let i = 0; i < report.length; i++) {
        const [reportUser, badUser] = report[i].split(' ');
        const reportLog = userMap.get(badUser);
        if (reportLog.includes(reportUser)) continue;
        userMap.set(badUser, [...reportLog, reportUser]);
        badUserObj[badUser] += 1;
    }
    for (const [user, reportCount] of Object.entries(badUserObj)) {
        if (reportCount >= k) {
            userMap.get(user).forEach((reportUser) => {
                reportUserObj[reportUser] += 1;
            });
        }
    }
    const answer = id_list.map((id) => reportUserObj[id]);
    return answer;
}



Problem(lev.2) : 문자열 압축

  • 압축할 문자열 s가 매개변수로 주어질 때, 아래에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.
    • 예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.
    • 다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

Solution

const getCompressedStr = (str, n) => {
  let compressedStr = '';
  let prevStr = str.slice(0, n);
  let sameCount = 1;
  for (let i = 1; i <= Math.ceil(str.length/n); i++) {
    const currStr = str.slice(n*i, n*(i+1));
    if (prevStr === currStr) {
      prevStr = currStr;
      sameCount++;
      continue;
    }
    if (sameCount > 1) {
      compressedStr += sameCount;
    }
    compressedStr += prevStr;
    prevStr = currStr;
    sameCount = 1;
  }
  return compressedStr;
}

function solution(s) {
    let answer = s.length;
    for (let num = 1; num <= s.length/2; num++) {
        const length = getCompressedStr(s, num).length;
        if (length < answer) {
            answer = length;
        }
    }
    return answer;
}

Problem(lev.2) : 괄호 변환

  • 균형잡힌 괄호 문자열 p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 올바른 괄호 문자열로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요.
    • '(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다.
    • 그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다.
    1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
    2. 문자열 w를 두 균형잡힌 괄호 문자열 u, v로 분리합니다. 단, u는 균형잡힌 괄호 문자열로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
    3. 문자열 u가 올바른 괄호 문자열 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
      3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
    4. 문자열 u가 올바른 괄호 문자열이 아니라면 아래 과정을 수행합니다.
      4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
      4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
      4-3. ')'를 다시 붙입니다.
      4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
      4-5. 생성된 문자열을 반환합니다.

Solution


function solution(str) {
  if (str === '') return '';
  const { isRight, indexOfU } = checkRightBracket(str);
  if (isRight) return str;
  const u = str.slice(0, indexOfU + 1);
  const v = str.slice(indexOfU + 1);
  if (checkRightBracket(u).isRight) {
    return u + solution(v);
  } else {
    let revisedStr = '(' + solution(v) + ')';
    revisedStr += convertBracketDirection(u.slice(1, -1));
    return revisedStr;
  }
}

function convertBracketDirection(str) {
  return str.split("").map((bracket) => bracket === '(' ? ')' : '(').join('');
}

function checkBracket(str, bracket) {
  let bracketCount = 0;
  let indexOfU = 0;
  for (let i = 0; i < str.length; i++) {
    if (str[i] === bracket) {
      bracketCount++;
      continue;
    }
    if (bracketCount > 0) {
      bracketCount--;
      if (bracketCount === 0) {
        indexOfU = indexOfU === 0 ? i : indexOfU;
      }
    }
  }
  const isRight = bracket === '(' && bracketCount === 0;
  return {
    isRight,
    indexOfU
  };
}

function checkRightBracket(str) {
  if (str[0] === ')') {
    return checkBracket(str, ')');
  }
  return checkBracket(str, '(');
}

console.log(solution("(()())()"));
console.log(solution("()))((()"));
console.log(solution(")("));

Problem(lev.1) : k번째 수

  • 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
    • 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면
      1.array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
      2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
      3. 2에서 나온 배열의 3번째 숫자는 5입니다.

Solution

function solution(array, commands) {
    const answer = commands.map((command) => {
        const startIndex = command[0] - 1;
        const endIndex = command[1] - 1;
        const k = command[2] - 1;
        const sortedArray = array.slice(startIndex, endIndex + 1).sort((a,b) => a - b);
        return sortedArray[k];
    });
    return answer;
}

Problem(lev.1) : 실패율

  • 전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.
    • 실패율 : 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
    • 제한 사항
      • 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
      • stages의 길이는 1 이상 200,000 이하이다.
      • stages에는 1 이상 N + 1 이하의 자연수가 담겨있다. 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
      • 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
      • 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
      • 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

Solution

function calculateFailedUser(level, stages) {
    const failedUserCount = stages.reduce((userCount, stage) => {
        let failedCount = userCount;
        if (stage === level) {
            failedCount++;
        }
        return failedCount;
    }, 0);
    return failedUserCount;
}

function solution(N, stages) {
    let totalUser = stages.length;
    let stageFailure = {};
    for (let stage = 1; stage <= N; stage++) {
        const failedUser = calculateFailedUser(stage, stages);
        const failure = failedUser / totalUser;
        stageFailure[stage] = failure;
        totalUser -= failedUser;
    }
    const sortedStageFailure = Object.entries(stageFailure).sort(([,a],[,b]) => b - a).map((stage,_) => Number(stage[0]));
    return sortedStageFailure;
}

Problem(lev.1) : 소수 만들기

  • 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.
    • 제한사항
      • nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
      • nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

Solution

function checkPrimeNumber(num) {
    let isPrime = true;
    for (let i = 2; i < num; i++) {
        if (num % i === 0) {
            isPrime = false;
        }
    }
    return isPrime;
}

function solution(nums) {
    var answer = 0;
    
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            for (let k = j + 1; k < nums.length; k++) {
                const sum = nums[i] + nums[j] + nums[k];
                if (checkPrimeNumber(sum)) {
                    answer++;
                }
            }
        }
    }
    return answer;
}

Problem(lev.1) : 없는 숫자 더하기

  • 0부터 9까지의 숫자 중 일부가 들어있는 정수 배열 numbers가 매개변수로 주어집니다. numbers에서 찾을 수 없는 0부터 9까지의 숫자를 모두 찾아 더한 수를 return 하도록 solution 함수를 완성해주세요.
    • 제한사항
      • 1 ≤ numbers의 길이 ≤ 9
      • 0 ≤ numbers의 모든 원소 ≤ 9
      • numbers의 모든 원소는 서로 다릅니다.

Solution

function solution(numbers) {
    var answer = 0;
    for (num = 0; num < 10; num++) {
        if (numbers.includes(num)) {
            continue;
        }
        answer += num;
    }
    return answer;
}

Problem(lev.1) 숫자 문자열과 영단어

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

Solution

function solution(s) {
    let answer = '';
    const nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
    const words = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine'];
    const dictionary = {
        'zero': 0,
        'one': 1,
        'two': 2,
        'three': 3,
        'four': 4,
        'five': 5,
        'six': 6,
        'seven': 7,
        'eight': 8,
        'nine': 9
    }
    let word = '';
    for (let i = 0; i < s.length; i++) {
        if (nums.includes(Number(s[i]))) {
            answer += s[i];
            continue;
        }
        word += s[i];
        if (words.includes(word)) {
            answer += dictionary[word];
            word = '';
        }
    }
    return parseInt(answer, 10);
}

0개의 댓글