hwangheetae · hwangheetae · May 20, 2024 · May 14, 2024 · May 17, 2024 · May 17, 2024
diff --git a/ns0h/week8/240514/삼총사.js b/ns0h/week8/240514/삼총사.js
@@ -0,0 +1,59 @@
+/*
+프로그래머스
+Lv.1 삼총사
+
+한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다.
+예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다.
+또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다.
+
+한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.
+
+제한사항
+3 ≤ number의 길이 ≤ 13
+-1,000 ≤ number의 각 원소 ≤ 1,000
+서로 다른 학생의 정수 번호가 같을 수 있습니다.
+*/
+
+function solution1(number) { // 내가 작성한 코드 (백트래킹X)
+    var answer = 0;
+
+    for(let i = 0; i < number.length-2; i++){
+        for(let j = i+1; j < number.length-1; j++){
+            for(let k = j+1; k < number.length; k++){
+                if(number[i] + number[j] + number[k] == 0) answer++;
+            }
+        }
+    }
+
+    return answer;
+}
+
+console.log(solution1([-2, 3, 0, 2, -5])); // 2
+console.log(solution1([-3, -2, -1, 0, 1, 2, 3])); // 5
+console.log(solution1([-1, 1, -1, 1])); // 0
+
+
+function solution2(number) { // GPT 코드 (백트래킹)
+    let answer = 0;
+    number.sort((a, b) => a - b);
+
+    function backtrack(start, count, sum) {
+        if (count === 3) {
+            if (sum === 0) answer++;
+            return;
+        }
+        for (let i = start; i < number.length; i++) {
+            // 가지치기
+            if (sum + number[i] * (3 - count) > 0) break;
+            backtrack(i + 1, count + 1, sum + number[i]);
+        }
+    }
+
+    backtrack(0, 0, 0);
+    return answer;
+}
+// 키포인트 : 정렬
+
+console.log(solution2([-2, 3, 0, 2, -5])); // 2
+console.log(solution2([-3, -2, -1, 0, 1, 2, 3])); // 5
+console.log(solution2([-1, 1, -1, 1])); // 0
diff --git a/ns0h/week8/240517/소수찾기.js b/ns0h/week8/240517/소수찾기.js
@@ -0,0 +1,47 @@
+/*
+프로그래머스
+Lv.2 소수 찾기
+
+한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
+각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
+
+제한사항
+numbers는 길이 1 이상 7 이하인 문자열입니다.
+numbers는 0~9까지 숫자만으로 이루어져 있습니다.
+"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
+*/
+
+// GPT 코드
+function isPrime(num) {
+  if (num <= 1) return false;
+  if (num <= 3) return true;
+  if (num % 2 === 0 || num % 3 === 0) return false;
+
+  for (let i = 5; i * i <= num; i += 6) {
+    if (num % i === 0 || num % (i + 2) === 0) return false;
+  }
+  return true;
+}
+
+function solution(numbers) {
+  const primeSet = new Set();
+
+  function generateCombinations(s_num, remaining) {
+    if (s_num.length > 0) {
+      const num = parseInt(s_num, 10);
+      if (isPrime(num)) {
+        primeSet.add(num);
+      }
+    }
+    for (let i = 0; i < remaining.length; i++) {
+      generateCombinations(s_num + remaining[i], remaining.slice(0, i) + remaining.slice(i + 1));
+    }
+  }
+
+  generateCombinations("", numbers);
+
+  return primeSet.size;
+}
+
+console.log(solution("17")); // 3
+console.log(solution("011")); // 2
diff --git a/ns0h/week8/240517/연산자끼워넣기.js b/ns0h/week8/240517/연산자끼워넣기.js
@@ -0,0 +1,77 @@
+/*
+백준
+14888번 연산자 끼워넣기
+
+N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
+우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.
+예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다.
+예를 들어, 아래와 같은 식을 만들 수 있다.
+    1+2+3-4×5÷6
+    1÷2+3+4-5×6
+    1+2÷3×4-5+6
+    1÷2×3-4+5+6
+식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다.
+즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.
+    1+2+3-4×5÷6 = 1
+    1÷2+3+4-5×6 = 12
+    1+2÷3×4-5+6 = 5
+    1÷2×3-4+5+6 = 7
+N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.
+
+입력
+첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다.
+(1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.
+
+출력
+첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다.
+연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다.
+또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.
+*/
+
+const fs = require('fs');
+let input = fs.readFileSync('ns0h/week8/240517/input.txt').toString().trim().split('\n');
+// 코드 제출 시 let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
+
+const N = parseInt(input[0].trim());
+const numbers = input[1].trim().split(' ').map(Number);
+const operators = input[2].trim().split(' ').map(Number);
+
+// 최댓값과 최솟값 초기화
+let maxResult = -Infinity;
+let minResult = Infinity;
+
+function calculate(a, b, operator) {
+    switch (operator) {
+        case 0:
+            return a + b;
+        case 1:
+            return a - b;
+        case 2:
+            return a * b;
+        case 3:
+            return ~~(a / b);
+    }
+}
+
+function backtrack(index, currentResult) {
+    if (index === N) {
+        maxResult = Math.max(maxResult, currentResult);
+        minResult = Math.min(minResult, currentResult);
+        return;
+    }
+
+    for (let i = 0; i < 4; i++) {
+        if (operators[i] > 0) {
+            operators[i]--;
+            const nextResult = calculate(currentResult, numbers[index], i);
+            backtrack(index + 1, nextResult);
+            operators[i]++;
+        }
+    }
+}
+
+// 백트래킹 시작
+backtrack(1, numbers[0]);
+
+console.log(maxResult);
+console.log(minResult);