Goni's dev_log

문제

https://www.acmicpc.net/problem/10808

코드

//브론즈2 알파벳 개수
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\r\n");
 
//각 문자열과 a의 아스키코드 차이 수를 return하는 함수
function getASCIInum(str) {
  return str.charCodeAt() - "a".charCodeAt();
}
 
const str = input.shift();
let alphabet = new Array(26).fill(0); //a-z 까지 담을 배열 생성
 
for (let i = 0; i < str.length; i++) {
  let index = getASCIInum(str[i]); //각 문자열과 a의 아스키 코드 차이를 통해 인덱스를 얻음
  alphabet[index]++; //해당 인덱스에 +1
}
 
console.log(alphabet.join(" "));

문제

https://programmers.co.kr/learn/courses/30/lessons/12943

코드

function solution(num) {
  let answer = 0; //정답 변수
  if (num === 1) return 0; //num이 1이면 코드를 실행할 필요가 없으니 0 return
  while (true) {
    if (num % 2 === 0) {
      num = num / 2;
      answer++;
    } else {
      num = num * 3 + 1;
      answer++;
    }
 
    if (num === 1) break; //num이 1이 되면 break
    if (answer > 500) return -1; //500번반복해도 안되면 -1 return
  }
  return answer;
}

후기

• 문제는 쉽게 풀었지만 히든 테스트케이스 13번에 막힌 분들이 조금 있을 것 같다
• num이 1로 주어졌을 때를 예외처리 해주면 바로 해결할 수 있을 것이다

문제

https://programmers.co.kr/learn/courses/30/lessons/12921

코드

function solution(n) {
  let arr = Array(n + 1)
    .fill(true)
    .fill(false, 0, 2); //처음 두 요소만 false로 fill하기
 
  //2부터 n까지의 수 중에서(1은 이미 소수가 아님) 루트n 이하의 수들만 봐주면 됨
  for (let i = 2; i * i <= n; i++) {
    //각 i에 대한 배수들을 판단해 해당 수는 false로 만들기(소수가 아니므로)
    for (let j = i * i; j <= n; j += i) {
      arr[j] = false;
    }
  }
  return arr.filter((i) => i).length;
}

후기

• 프로그래머스 Level1문제의 '소수 만들기'문제에서 소수를 판별하는 법을 익혔기 때문에 쉽게 풀어서 제출했는데, 왠지 채점시간이 엄청 길어지더니 결국 시간초과가 뜨고, 효율성 테스트에서 탈락했다
• 다른 분들도 시간초과나 효율성 때문에 고난을 겪으신는 것 같았다. 찾아보니 '소수 만들기'문제와 달리 이 문제는 1부터 n까지의 수 중에서 소수가 몇 개인지 찾는 문제이기 때문에 (소수 만들기 문제는 숫자하나에대한 소수판별만 하면 됐다) n이 커지면 커질수록 나의 원래 코드는 비효율적일 수 밖에 없었다
• 그래서 찾아보니, 소수를 찾아내는 알고리즘으로 "에라토스테네스의 체"라는 공식이 있었다. 현재까지도 이 공식이 소수를 찾는 데 가장 효율적인 공식이라고 한다.
• 에라토스테네스의 체 : 쉽게 말해, 소수는 1과 자기자신으로만 나누어 떨어지는 수이다. 그렇다면, 어떤 배수는 소수가 아니라는 뜻이다. n까지의 수 중에서 배수들을 제외하면 소수가 된다는 것이다.
• https://themarketer.tistory.com/73 처음에 이론만 봤을 때는 이해가 잘 안돼서 이 분의 블로그를 보니 쉽게 이해가 됐다. 공식이 간단하기도 한데 정말 큰 효율성을 자랑하는 것같다.

문제

https://programmers.co.kr/learn/courses/30/lessons/12930

코드

function solution(s) {
  let newS = ""; //정답 변수
  s = s.split(" "); //공백 단위로 나누어 단어별로 나누기
 
  for (let i = 0; i < s.length; i++) {
    //단어의 개수만큼
    for (let j = 0; j < s[i].length; j++) {
      //각 단어의 철자 하나하나에 대해
      if (j % 2 === 0) newS = newS + s[i][j].toUpperCase();
      //짝수면 대문자
      else newS = newS + s[i][j].toLowerCase(); //홀수면 소문자
    }
    if (i < s.length - 1) newS = newS + " "; //마지막 단어의 전까지는 각 단어들 사이에 공백 추가
  }
  return newS;
}

후기

• 처음에 정답풀이와 조금은 다르게 풀이를 했었는데, 히든 테케에서 2번 제외 모두 틀렸다고 나왔다
• 원인을 보니, 문제에 각 단어는 하나 이상의 공백문자로 구분되어 있습니다. 라는 조건이 있었고, 입출력 예시를 예시로 들자면 밑과 같이 각 단어 사이에 한 개 이상의 공백들이 있는 경우를 제대로 처리하지 못했었다

  "try  hello   world"

• 이 점만 유의해서 풀면 쉽게 해결할 수 있겠다!

문제

https://programmers.co.kr/learn/courses/30/lessons/12928?language=javascript 

코드

function solution(n) {
    let answer = 0;
    for (let i=1; i<=n; i++) {
        if (n % i === 0) answer += i;
    }
    return answer;
}

문제

https://www.acmicpc.net/problem/7795

코드

// 실버3 먹을 것인가 먹힐 것인가
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\r\n");
 
//문자열을 숫자로 바꿔주고 배열로 return
function strToNum(str) {
  return str.split(" ").map((i) => parseInt(i));
}
 
//이분탐색 함수
function binarySearch(arr, num) {
  let index = -1; //arr배열(B)의 수 중에서 num(A의 각 요소)보다 크지 않은 수 중에서 제일 큰 index를 return
  let start = 0; //배열의 시작 index
  let end = arr.length - 1; //배열의 끝 index
  let middle = 0; //배열의 중간 index
 
  while (start <= end) {
    middle = Math.floor((start + end) / 2);
 
    //B의 중간값이 A의 요소보다 작다면 답이 될 index는 중간값의 index가 되고, 시작 index를 중간값 다음 수로 해서 num보다 크지 않은 수 중에서 제일 큰 수를 찾을 때까지 반복
    if (arr[middle] < num) {
      index = middle;
      start = middle + 1;
    }
    //반대의 상황에서는 end값만 변경해주고, index는 초기값인 -1 그대로 두기
    else {
      end = middle - 1;
    }
  }
  return index;
}
 
/* 전역변수 초기화 */
let inputIndex = 0; //입력 배열의 index
let testCase = strToNum(input[inputIndex++])[0];
let A, B;
 
//테스트 케이스만큼 반복
while (testCase--) {
  let answer = 0;
  const [numA, numB] = strToNum(input[inputIndex++]);
  A = [...strToNum(input[inputIndex++])].sort((a, b) => a - b); //A의 크기 오름차순 정렬
  B = [...strToNum(input[inputIndex++])].sort((a, b) => a - b); //B의 크기 오름차순 정렬
 
  //A의 각 요소들에 대해
  for (let i of A) {
    answer += binarySearch(B, i) + 1; //index = -1로 초기화 되어있으니 맞춰주기 위해 +1
  }
 
  console.log(answer);
}
 
// 결과
// 7
// 1

후기

• 문제의 알고리즘 분류에 정렬, 이분탐색으로 나와있듯이 두개를 이용하면 딱 풀 수있는 문제였다
• 크게 어려울 건 없었지만 A, B 배열의 수 크기를 비교할 때 어떻게 비교하는 게 최선일까 고민을 하였고 내 방법이 최선인지는 모르겠지만 A의 각 요소들에 대해 B 배열에서 각 요소보다 크지 않은 수 중에서 제일 큰수의 index를 반환하는 것이 가장 큰 포인트였다고 생각한다