TIL. 알고리즘 문제풀이

seul_velog·2023년 2월 8일
TILalgorithm
0

TIL_algorithm

목록 보기
13/26

분수의 덧셈

문제 설명

첫 번째 분수의 분자와 분모를 뜻하는 denum1, num1, 두 번째 분수의 분자와 분모를 뜻하는 denum2, num2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.

▣ 제한사항
0 < numer1, denom1, numer2, denom2 < 1,000

▣ 입력설명
1 / 2 + 3 / 4 = 5 / 4입니다. 따라서 [5, 4]를 return 합니다.

▣ 출력설명
9 / 2 + 1 / 3 = 29 / 6입니다. 따라서 [29, 6]을 return 합니다.

▣ 입출력 예

numer1denom1numer2denom2denom2
1234[5, 4]
9213[29, 6]

최소 공약수 구해보기

📌 일반적으로 최소 공약수 구해보기 🧐

function solution(num1, num2) {
  let answer = 1; // 1)
  for (let i = 2; i <= Math.min(num1, num2); i++) {
    if (num1 % i === 0 && num2 % i === 0) {
      answer = i;
    }
  }
  return answer;
}
console.log(solution(9, 18)); // 9
  • 1) 전부 해당하지 못할경우 1을 리턴한다. 해당할 경우 계속 업데이트 된다.

유클리드 호제법으로 구하기

function solution(n, m) {
  const 최대공약수 = (a, b) => (a % b === 0 ? b : 최대공약수(b, a % b)); // 1)
  const 최소공배수 = (a, b) => (a * b) / 최대공약수(a, b); // 2)
  return [최대공약수(n, m), 최소공배수(n, m)];
}

console.log(solution(3, 12)); // [3, 12]
console.log(solution(7, 18)); // [1, 126]
  • 1) 최대공약수
  • 2) 최소 공배수 <- 최대공약수()에 최대공약수를 구할 수 있는 함수를 실행, 그 값(최대공약수)로 계산한다.

📌 유클리드 호제법

  • 유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다.
  • 유클리드(Euclid)에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘이다.
  • 호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 말한다.

분수의 덧셈

function solution(numer1, denom1, numer2, denom2) {
  let gcd = (a, b) => {   // 1)
    return a % b === 0 ? b : gcd(b, a % b);
  };

  let topNum = numer1 * denom2 + numer2 * denom1; // 2)
  let botNum = denom1 * denom2; // 3)
  let gcd2 = gcd(topNum, botNum);

  return [topNum / gcd2, botNum / gcd2]; // 4)
}
console.log(solution(1, 2, 3, 4)); // [5, 4]
console.log(solution(9, 2, 1, 3)); // [29, 6]
  • 1) 앞서 살펴본 최대공약수이다.
  • 2) 분자값 구하기(공식)
  • 3) 동일한 분모로 만들기
  • 4) 기약분수로 만들기

✍️ 손으로 풀어보면서 규칙은 발견했는데 이것을 유클리드 호제법을 적용시키고, 코드로 치는것은 또다른 과제인 것 같았다.. 🧐





남은 문자 구하기

문제 설명

주어진 문자에서 입력받은 문자로 이루어진 문자만 제거하여 남은 문자를 구하세요.

▣ 입력설명
ABABCCT 주어진 문자열, ABC가 입력받은 문자라면 ABC(타겟 문자)를 찾아내서 없애고 최종적으로 남은 문자만 return 합니다.

▣ 출력설명
AB'ABC'CT 에서 첫 번째 ABC가 제거되어 'ABC'T가 되고 다시 두 번째 ABC가 제거되면 T만 남고 return 됩니다.
만약 모두 제거되고 남은 문자가 없다면 -1을 return합니다.

▣ 입출력 예

strtargetreturn
ABABCCTABCT
AAAAAABCBCBCABCYYABCAAAYY

풀이

function getFinalString(str) {
  const target = 'ABC'; // 1)
  let answer = str; // 2)
  let index = answer.indexOf(target); // 3)

  while (index >= 0) { // 4)
    // 5)
    answer = answer.slice(0, index) + answer.slice(index + target.length);
    index = answer.indexOf(target); // 6)
  }
  return answer.length > 0 ? answer : '-1'; // 7)
}

const str = 'ABABCCT';
console.log(getFinalString(str)); // T

  • 1) 먼저 target 문자를 설정한다.

  • 2) str을 받아서 answer 변수에 새롭게 저장한다.

  • 3) indexOf 메서드를 사용해서 answer 문자열 안에 target 문자가 몇번째 인덱스에 있는지 확인한다.
    ❗️이때, answer 문자열이 target문자를 포함하고 있지 않으면 -1을 반환한다.
    👉 indexOf-MDN

  • 4) index 값이 0이상이라면, 즉 포함되어 있다면 while문을 돌게된다.

  • 5) 예를들어 첫번째 ABC를 찾기위해 while문에 들어왔다면, index는 2가 되고, answer.slice(0,2) 는 'AB' 가 된다.
    또 , answer.slice(index + target.length) 는 answer.slice(2 + 3) 이므로 'CT' 가 된다.
    따라서 아래 코드의 answer 는 ABCT 가 남게 된다.

    answer = answer.slice(0, index) + answer.slice(index + target.length) // ABCT

  • 6) 다시 target 문자가 있는지 점검한다. 있다면 0 이상의 값이 리턴되므로 while문을 계속해서 돈다.

  • 7) 처음에 주어진 문자열에서 타겟 문자를 모두 제거한 후 문자열이 남아있다면 남은 문자열을 그대로 return, 더이상 문자열이 남아있지 않다면 -1을 return 하도록 한다.

    ✍️ 결국 잘 생각해보면 target 문자열을 찾아서 slice 메서드와 그 특징 (첫 번째 인자부터, 그 인자는 포함 → 두 번째 인자까지 잘라내지만 그 인자 앞까지만 자름) 을 활용해서 계속 잘라내서 답을 구하는 방식이다. 🧐 5) 부분이 핵심! 📌

profile
seul_velog
기억보단 기록을 ✨
이전 포스트

TIL. 알고리즘 문제풀이

다음 포스트

TIL. 완전 탐색(Brute Force) 알고리즘 문제풀이

0개의 댓글