제로베이스 코딩테스트

// https://school.programmers.co.kr/learn/courses/30/lessons/258712

// 1. 친구들 키 값 저장.
// 2. 선물 주고받은 내역 기록
// 3. 기록을 바탕으로 선물 지수 계산
// 4. 다음 달 받을 선물 계산
// 5. 최댓값 반환

function solution1(friends, gifts) {
  const len = friends.length
  const nameMap = new Map()
  const giftTable = new Array(len).fill(0).map((_) => new Array(len).fill(0))
  const rankInfo = new Array(len).fill(0)
  const nextMonth = new Array(len).fill(0)

  friends.forEach((name, idx) => {
    nameMap.set(name, idx)
  })

  gifts.forEach((info) => {
    const [from, to] = info.split(' ')
    giftTable[nameMap.get(from)][nameMap.get(to)]++
  })

  for (let i = 0; i < len; i++) {
    rankInfo[i] = giftTable[i].reduce((acc, cur) => (acc += cur), 0)

    for (let j = 0; j < len; j++) {
      rankInfo[i] -= giftTable[j][i]
    }
  }

  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      if (i === j) continue
      if (giftTable[i][j] > giftTable[j][i]) nextMonth[i]++
      if (giftTable[i][j] < giftTable[j][i]) nextMonth[j]++
      if (giftTable[i][j] === giftTable[j][i]) {
        if (rankInfo[i] > rankInfo[j]) nextMonth[i]++
        if (rankInfo[i] < rankInfo[j]) nextMonth[j]++
      }
    }
  }

  return Math.max(...nextMonth)
}

/*
문자열 배열 arr가 있습니다.
이 문자열의 공통된 문자를 오름차순으로 출력하세요.
arr은 영어 소문자로 이루어져 있으며, 공통 문자는 중복 없이 출력합니다.
 */

function solution2(arr) {
  let answer = []
  let set = new Set(arr[0]) // a, p, l, e

  for (let i = 1; i < arr.length; i++) {
    let curr = new Set(arr[i])
    set = new Set([...set].filter((e) => curr.has(e))) // 교집합
  }

  if (set.length !== 0) {
    answer = Array.from(set).sort()
  } else {
    return answer
  }
  return answer
}

/*
n개의 문자를 보여주는 크기가 n인 전광판이 있습니다. 전광판의 문자는 오른쪽에서 왼쪽으로 반복해서 흘러가며, 1초에 한 글자씩 흘러갑니다.
예를 들어, 크기가 5인 전광판에 "Snowball" 노출한다고 가정할 때, 시간 t의 변화에 따른 노출 예시는 다음과 같습니다.
0s : '.....' 1s : '....S' 5s : 'Snowb' 10s : 'all..' 15s : '...Sn'

전광판의 크기 n과 전광판에 노출할 문자 s 그리고 시간 t가 주어질 때, t 초 후의 전광판에 표시될 문구를 출력하는 함수, solution을 완성해주세요.

제한 사항
전광판의 문자는 1초부터 흐르기 시작합니다.

입력 형식
n은 1 이상 50 이하의 정수입니다.
s는 길이가 1 이상 100 이하의 문자열입니다.
s는 알파벳 대/소문자와 숫자로 구성됩니다.
t는 1 이상 1000 이하의 정수입니다.

출력 형식
t 초 후, 주어진 전광판에 노출되는 문자를 출력합니다.
전광판의 공백은 마침표(".")로 대체하여 출력합니다.
 */

function solution3(n, s, t) {
  let answer = ''

  const text = '.'.repeat(n) + s + '.'.repeat(n - 1) // 전광판을 초기화 (ex)= .....Snowball....
  const duration = n + s.length // 초기화 할때랑 값을 같게 할 필요 X > 초기화를 위한 "."은 생략
  const time = t % duration // 나머지로 처리

  answer = text.substr(time, n) // substr로 반복

  return answer
}

/*
문제 설명
여름을 맞아 가족들과 함께 해수욕장을 방문했습니다. 코로나로 인해서 많은 사람이 각자의 파라솔 아래에서 마스크를 쓰고 둘러앉아 모래 뺏기 게임을 하고 있습니다. 흥민이와 흥민이의 누나는 `num`kg의 모래를 쌓아두고 게임을 시작합니다. 모래성 중앙의 깃발이 쓰러지지 않도록 하는 모래성의 무게는 `1kg`입니다. 흥민, 누나의 순서대로 게임이 진행됩니다. 한사람이 한 번에 가져갈 수 있는 모래의 양은 최소 `1kg`, 최대 `3kg`입니다. 여기에서 모래의 양 `num`을 입력하여 흥민이가 이길 수 있는 경우를 `true, false`로 출력하는 함수를 작성해 보세요.

제한 사항
- 최소 `1kg`, 최대 `3kg`의 모래를 가져갈 수 있습니다.
- 흥민, 누나의 순서대로 게임이 진행됩니다.
- 모래성은 `1kg` 미만으로 남게 되면 쓰러집니다.
- 즉, `1kg`이 자기 차례에 남으면 승리합니다.

### 입력 형식
- num은 1 이상 100,000 이하의 정수입니다.

출력 형식
- 흥민이가 이길 수 있는 경우를 `true, false`로 출력합니다.

 */

function solution1(num) {
  if (num % 4 === 1) {
    return false
  } else {
    return true
  }
}

/*
문제 설명
배열 A는 십만전자의 일단위 주식가격이 들어있습니다. 해당 주식 가격 기준으로 매수와 매도를 1회씩 진행했을 때 가능한 최대 수익을 구하는 함수를 작성하세요. 이때 매도는 항상 매수 이후에 이루어지며 수익을 낼 수 없는 경우 0을 리턴하세요.

입력 형식
주식의 일단위 주가 정보 배열
 */
function solution2(A) {
  let minPrice = A[0]
  let answer = 0

  for (let i = 1; i < A.length; i++) {
    answer = Math.max(answer, A[i] - minPrice)
    minPrice = Math.min(minPrice, A[i])
  }

  return answer
}

/*
문제 설명
블록으로 피라미드 모양의 탑을 쌓으려고 합니다.
피라미드 모양의 탑은 꼭대기는 1개의 블록을 사용하고,
그 아래는 2개의 블록, 그 아래에는 3개의 블록의 방식으로 쌓습니다. `n` 층의 피라미드 모양의 탑을 쌓을 때, 필요한 블록의 수를 구하는 함수,
 `solution`을 완성해주세요.

 입력 형식
- `n`은 1 이상 1,000 이하의 정수입니다.

출력 형식
- 피라미드 모양의 탑을 쌓는데 필요한 블록의 총수를 구합니다.
 */

function solution3(n) {
  let answer = 0
  for (let i = 0; i <= n; i++) {
    answer += i
  }
  return answer
}

// 문제 1: 정수 n의 이진 표현에서 1과 1 사이의 최대 간격 구하기
// 정수 n이 주어질 때, n의 이진 표현에서 1과 1 사이의 최대 간격을 구하는 함수를 작성하세요.
// 최대 간격은 두 1 사이에 있는 0의 수를 나타냅니다. 이 함수는 이진 표현의 각 자리를 순회하면서 1 사이의 간격을 계산하고, 그 중 가장 큰 간격을 반환해야 합니다.
// 입력: 정수 n (1 ≤ n ≤ 2^31 - 1)
// 출력: n의 이진 표현에서 1과 1 사이의 최대 간격을 나타내는 정수
function solution1(n) {
  // n의 이진 표현을 문자열로 변환합니다.
  const binaryString = n.toString(2)

  // 이전 1의 위치를 추적할 변수입니다.
  let previousIndex = -1
  let maxGap = 0

  // 이진 문자열을 순회합니다.
  for (let i = 0; i < binaryString.length; i++) {
    if (binaryString[i] === '1') {
      if (previousIndex !== -1) {
        // 현재 1과 이전 1 사이의 거리를 계산합니다.
        const gap = i - previousIndex
        // 가장 긴 거리를 업데이트합니다.
        maxGap = Math.max(maxGap, gap)
      }
      // 이전 1의 위치를 현재 위치로 업데이트합니다.
      previousIndex = i
    }
  }

  return maxGap
}

// 문제 2: 문자열에서 가장 많이 등장하는 숫자 찾기
// 문자열 s가 주어질 때, 문자열에 포함된 숫자(0-9) 중 가장 많이 등장하는 숫자를 찾는 함수를 작성하세요.
// 가장 많이 등장하는 숫자가 여러 개일 경우, 그 중에서 가장 작은 숫자를 반환합니다.
// 입력: 문자열 s (1 ≤ s.length ≤ 1000): 숫자 문자로만 구성된 문자열
// 출력: 문자열 s에 가장 많이 등장한 숫자를 나타내는 정수
function solution2(s) {
  // 각 숫자의 빈도를 저장할 배열을 초기화합니다.
  const frequency = new Array(10).fill(0)

  // 문자열을 순회하면서 각 숫자의 빈도를 증가시킵니다.
  for (let char of s) {
    const digit = parseInt(char)
    frequency[digit]++
  }

  // 가장 많이 등장한 숫자를 찾습니다.
  let maxFrequency = 0
  let result = 9

  for (let i = 0; i < 10; i++) {
    if (frequency[i] > maxFrequency) {
      maxFrequency = frequency[i]
      result = i
    } else if (frequency[i] === maxFrequency && i < result) {
      result = i
    }
  }

  return result
}

// 문제 3: 배열에서 조건을 만족하는 쌍의 개수 찾기
// 정수 배열 nums와 정수 d가 주어질 때, 배열에서 d로 나누어 떨어지는 값이 동일한 쌍의 개수를 찾는 함수를 작성하세요.
// 쌍 (i, j)는 nums[i] === nums[j]이고, nums[i] % d === 0일 때 유효합니다. 여기서 i < j입니다.
// 입력: 정수 배열 nums (1 ≤ nums.length ≤ 1000), 정수 d (1 ≤ d ≤ 100)
// 출력: 조건을 만족하는 쌍 (i, j)의 개수를 나타내는 정수
function solution3(nums, d) {
  // 조건을 만족하는 쌍의 개수를 저장할 변수
  let answer = 0

  // 배열을 이중 반복문으로 순회하면서 쌍을 찾습니다.
  for (let a = 0; a < nums.length; a++) {
    for (let b = a + 1; b < nums.length; b++) {
      // 조건을 만족하는지 확인
      if (nums[a] === nums[b] && nums[a] % d === 0) {
        answer++
      }
    }
  }

  return answer // 조건을 만족하는 쌍의 개수 반환
}

// 문제 1: 중복되지 않은 문자로 이루어진 가장 긴 부분 문자열의 길이 구하기
// 주어진 문자열에서 중복되지 않은 문자로 이루어진 가장 긴 부분 문자열의 길이를 구하는 함수를 작성하세요.
// 입력: 문자열 s는 알파벳 대소문자와 숫자로 이루어져 있습니다. (0 ≤ s.length ≤ 10,000)
// 출력: 중복되지 않은 문자로 이루어진 가장 긴 부분 문자열의 길이를 반환합니다.
function solution1(s) {
  // 고유한 문자를 추적하기 위한 Set
  let seen = new Set()

  // 최대 길이를 저장하는 변수
  let maxLength = 0

  // 왼쪽 포인터
  let left = 0

  // 문자열 s를 한 문자씩 오른쪽 포인터로 순회
  for (let right = 0; right < s.length; right++) {
    // 현재 문자가 이미 seen에 있다면, 중복이 없는 부분 문자열을 만들기 위해
    // 왼쪽 포인터를 오른쪽으로 이동하고 seen에서 문자 제거
    while (seen.has(s[right])) {
      seen.delete(s[left])
      left++
    }

    // 현재 문자를 seen에 추가
    seen.add(s[right])

    // 현재 부분 문자열의 길이를 계산하고, 최대 길이와 비교하여 갱신
    maxLength = Math.max(maxLength, right - left + 1)
  }

  // 최대 길이를 반환
  return maxLength
}

// 문제 2: 이진수 문자열을 0으로 만들기 위한 최소 연산 횟수
// 주어진 이진수 문자열을 0으로 만들기 위한 최소 연산 횟수를 구하는 함수를 작성하세요.
// 사용할 수 있는 연산: 현재 수가 짝수면 2로 나눕니다. 홀수면 1을 뺍니다.
// 입력: 이진수 문자열 s (1 ≤ s.length ≤ 1000)
// 출력: 이진수 문자열 s를 0으로 만들기 위한 최소 연산 횟수를 반환합니다.
function countOperations(s) {
  // 이진수 문자열을 정수로 변환
  let num = parseInt(s, 2)
  let operations = 0

  // num이 0이 될 때까지 연산 수행
  while (num > 0) {
    if (num % 2 === 0) {
      // 짝수인 경우 2로 나눈다
      num /= 2
    } else {
      // 홀수인 경우 1을 뺀다
      num -= 1
    }
    operations++
  }

  return operations
}

// 문제 3: 문자열이 회문인지 확인하기
// 주어진 문자열이 회문(앞뒤가 똑같은 문자열)인지 확인하는 함수를 작성하세요.
// 입력: 문자열 S (1 ≤ S.length ≤ 1000, 알파벳 소문자로만 이루어짐)
// 출력: 문자열 S가 회문이면 1을 반환하고, 아니면 0을 반환합니다.
function solution3(S) {
  const reversedChar = S.split('').reverse().join('')
  if (reversedChar === S) {
    return 1
  } else {
    return 0
  }
}

// 추가 사항
// 진수 ?
// 1. 진수 변환 방법
// 10진수를 다른 진수로 변환하는 방법
function decimalToOtherBases(n) {
  console.log(`10진수: ${n}`)
  console.log(`2진수: ${n.toString(2)}`)
  console.log(`8진수: ${n.toString(8)}`)
  console.log(`16진수: ${n.toString(16)}`)
}

// 다른 진수를 10진수로 변환하는 방법
function otherBasesToDecimal() {
  console.log(`2진수 "1010" -> 10진수: ${parseInt('1010', 2)}`)
  console.log(`8진수 "52" -> 10진수: ${parseInt('52', 8)}`)
  console.log(`16진수 "2a" -> 10진수: ${parseInt('2a', 16)}`)
}

// 2. 회문(팰린드롬) 관련 함수
// 문자열이 회문인지 확인
function isPalindrome(s) {
  const reversed = s.split('').reverse().join('')
  return s === reversed
}

// 숫자가 회문인지 확인 (10진수 기준)
function isNumericPalindrome(n) {
  const str = n.toString()
  return isPalindrome(str)
}

// 숫자가 특정 진수에서 회문인지 확인
function isPalindromeInBase(n, base) {
  const converted = n.toString(base)
  return isPalindrome(converted)
}

// 3. 응용 문제: 진수와 회문 관련 문제 예제
// 문제 1: 주어진 숫자가 10진수와 2진수에서 모두 회문인지 확인
function isDoublePalindrome(n) {
  const isDecimalPalindrome = isNumericPalindrome(n)
  const isBinaryPalindrome = isPalindromeInBase(n, 2)
  return isDecimalPalindrome && isBinaryPalindrome
}

// 문제 2: 특정 범위에서 10진수와 2진수 모두 회문인 숫자를 찾기
function findDoublePalindromesInRange(start, end) {
  const results = []
  for (let i = start; i <= end; i++) {
    if (isDoublePalindrome(i)) {
      results.push(i)
    }
  }
  return results
}

// 실행 예제
console.log('진수 변환 예제:')
decimalToOtherBases(42)
otherBasesToDecimal()

console.log('\n회문 관련 예제:')
console.log(`"abba"는 회문인가? ${isPalindrome('abba')}`)
console.log(`121은 10진수에서 회문인가? ${isNumericPalindrome(121)}`)
console.log(`585은 2진수에서 회문인가? ${isPalindromeInBase(585, 2)}`)

console.log('\n응용 문제:')
console.log(`585은 10진수와 2진수에서 모두 회문인가? ${isDoublePalindrome(585)}`)
console.log(
  `10에서 1000 사이의 숫자 중 10진수와 2진수 모두 회문인 숫자: ${findDoublePalindromesInRange(10, 1000)}`
)

// 문제 1: 가장 긴 회문 부분 문자열 찾기
function longestPalindrome(s) {
  let start = 0,
    maxLength = 0

  function expandAroundCenter(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--
      right++
    }
    return right - left - 1
  }

  for (let i = 0; i < s.length; i++) {
    const len1 = expandAroundCenter(i, i) // 홀수 길이
    const len2 = expandAroundCenter(i, i + 1) // 짝수 길이
    const len = Math.max(len1, len2)
    if (len > maxLength) {
      maxLength = len
      start = i - Math.floor((len - 1) / 2)
    }
  }
  return s.substring(start, start + maxLength)
}

// 문제 2: 최소 삽입 연산으로 회문 만들기
function minInsertionsForPalindrome(s) {
  const n = s.length
  const dp = Array.from({ length: n }, () => Array(n).fill(0))

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1
      if (s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1]
      } else {
        dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1
      }
    }
  }

  return dp[0][n - 1]
}

// 문제 3: 회문 부분 문자열 개수
function countPalindromeSubstrings(s) {
  let count = 0

  function expandAroundCenter(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      count++
      left--
      right++
    }
  }

  for (let i = 0; i < s.length; i++) {
    expandAroundCenter(i, i) // 홀수 길이
    expandAroundCenter(i, i + 1) // 짝수 길이
  }

  return count
}

// 문제 4: 진법 변환과 회문 확인
function isPalindromeInBase(n, base) {
  const converted = n.toString(base)
  const reversed = converted.split('').reverse().join('')
  return converted === reversed
}

// 문제 5: 회문 순열 확인
function canFormPalindrome(s) {
  const charCount = {}
  for (const char of s) {
    charCount[char] = (charCount[char] || 0) + 1
  }
  let oddCount = 0
  for (const count of Object.values(charCount)) {
    if (count % 2 !== 0) oddCount++
  }
  return oddCount <= 1
}

// 실행 예제
console.log('Longest Palindrome: ', longestPalindrome('babad')) // "bab" 또는 "aba"
console.log('Min Insertions: ', minInsertionsForPalindrome('abca')) // 1
console.log('Count Palindrome Substrings: ', countPalindromeSubstrings('aaa')) // 6
console.log('Is Palindrome in Base 2: ', isPalindromeInBase(585, 2)) // true
console.log('Can Form Palindrome: ', canFormPalindrome('civic')) // true

// 문제 1: 패턴과 문자열 매핑 여부 확인
// 주어진 패턴과 문자열이 조건을 만족하는지 확인하는 함수
function solution1(p, s) {
  const words = s.split(' ')
  if (p.length !== words.length) {
    return false
  }

  const pMap = {}
  const usedWords = new Set()

  for (let i = 0; i < p.length; i++) {
    const char = p[i]
    const word = words[i]

    if (pMap[char]) {
      if (pMap[char] !== word) {
        return false
      }
    } else {
      if (usedWords.has(word)) {
        return false
      }
      pMap[char] = word
      usedWords.add(word)
    }
  }

  return true
}

// 문제 2: 중복된 단어 제거 후 고유 단어 개수 반환
// 주어진 문자열에서 중복된 단어를 제거한 후, 고유한 단어의 개수를 반환하는 함수
function solution2(s) {
  // 문자열을 공백을 기준으로 나누어 배열로 만듭니다.
  const words = s.split(' ')

  // Set 객체를 사용하여 중복된 단어를 제거합니다.
  const uniqueWords = new Set(words)

  // 중복을 제거한 단어의 수를 반환합니다.
  return uniqueWords.size
}

// 문제 3: 알파벳의 모든 문자가 포함되었는지 확인
// 주어진 문자열이 알파벳의 모든 문자를 포함하는지 확인하는 함수
function solution3(s) {
  // 문자열을 소문자로 변환합니다.
  const lowerCaseString = s.toLowerCase()

  // 알파벳 문자를 저장할 Set 객체를 생성합니다.
  const alphabetSet = new Set()

  // 문자열을 순회하며 알파벳 문자를 Set 객체에 추가합니다.
  for (let char of lowerCaseString) {
    if (char >= 'a' && char <= 'z') {
      alphabetSet.add(char)
    }
  }

  // Set 객체의 크기가 26이면 true, 아니면 false를 반환합니다.
  return alphabetSet.size === 26
}

// 실행 예제
console.log('문제 1:', solution1('abba', 'dog cat cat dog')) // true
console.log('문제 1:', solution1('abba', 'dog cat cat fish')) // false

console.log('문제 2:', solution2('hello world world hello')) // 2
console.log('문제 2:', solution2('a b c a b c')) // 3

console.log('문제 3:', solution3('The quick brown fox jumps over the lazy dog')) // true
console.log('문제 3:', solution3('Hello World')) // false

/*
문제: 주어진 두 배열에서 겹치는 숫자들을 찾아 오름차순으로 정렬된 배열로 반환하는 함수 findCommonElements를 작성하세요.

입력:
두 개의 숫자 배열, arr1과 arr2

출력:
두 배열에 공통으로 존재하는 숫자들을 오름차순으로 정렬한 배열

예시:
입력: arr1 = [1, 2, 4, 5, 6], arr2 = [2, 5, 7, 8] 출력: [2, 5]
입력: arr1 = [10, 20, 30, 40], arr2 = [40, 30, 20, 10] 출력: [10, 20, 30, 40]
입력: arr1 = [3, 3, 3, 2, 2], arr2 = [2, 3, 5, 7] 출력: [2, 3]

주의사항:
두 배열에서 중복되는 숫자가 없으면 빈 배열을 반환해야 합니다.
입력 배열에 중복된 숫자가 있을 수 있지만, 결과 배열은 중복 없이 고유한 숫자만을 포함해야 합니다.
*/

// 두 배열에 동시에 존재하는 숫자들을 찾는 함수
function findCommonElements(arr1, arr2) {
  // 두 배열을 집합(Set)으로 변환
  let set1 = new Set(arr1)
  let set2 = new Set(arr2)

  // 공통 원소를 저장할 배열
  let commonElements = []

  // set1의 원소가 set2에도 존재하면 공통 배열에 추가
  set1.forEach((element) => {
    if (set2.has(element)) {
      commonElements.push(element)
    }
  })

  // 오름차순으로 정렬하여 반환
  return commonElements.sort((a, b) => a - b)
}

/*
문제 설명
주어진 팔로우 관계를 바탕으로 맞팔 관계 쌍의 갯수를 구하는 함수를 작성하세요. 맞팔 관계란 두 사용자가 서로를 팔로우하는 관계를 의미합니다.

입력
하나의 2차원 배열 followPairs가 주어집니다. 각 요소는 두 개의 문자열로 이루어진 배열로, 첫 번째 문자열은 팔로워의 이름, 두 번째 문자열은 팔로우된 사람의 이름을 나타냅니다.
배열 followPairs의 길이는 1 <= followPairs.length <= 1000입니다.

각 문자열의 길이는 1 <= string.length <= 50입니다.

출력
맞팔 관계 쌍의 갯수를 정수로 반환하세요.
 */

function countMutualFollows(followPairs) {
  // 팔로우 관계를 저장할 객체
  let followMap = {}

  // 팔로우 관계를 객체에 저장
  followPairs.forEach((pair) => {
    let [follower, followee] = pair
    if (!followMap[follower]) {
      followMap[follower] = new Set()
    }
    followMap[follower].add(followee)
  })

  // 맞팔 관계 쌍의 갯수를 셈
  let mutualCount = 0

  followPairs.forEach((pair) => {
    let [follower, followee] = pair
    // 맞팔 관계인지 확인
    if (followMap[followee] && followMap[followee].has(follower)) {
      mutualCount++
    }
  })

  // 맞팔 관계는 서로 상호작용이 있으므로 2번씩 셈해지므로 2로 나눔
  return mutualCount / 2
}

/*
문제 설명

주어진 배열이 최소 힙(min heap)의 조건을 만족하는지 확인하는 함수를 작성하세요. 최소 힙은 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같은 이진 트리입니다.

입력
하나의 배열 arr이 주어집니다. 배열의 첫 번째 요소는 사용되지 않으며, 인덱스 1부터 시작합니다.
배열 arr의 길이는 1 <= arr.length <= 100입니다.
배열 arr의 요소는 정수입니다.

출력
배열 arr이 최소 힙 조건을 만족하면 "YES"를, 그렇지 않으면 "NO"를 반환하세요.
 */

function isMinHeap(arr) {
  // 배열의 길이를 구함
  let n = arr.length

  // 인덱스 1부터 시작하여 모든 노드가 최소 힙 조건을 만족하는지 확인
  for (let i = 1; i <= Math.floor((n - 1) / 2); i++) {
    // 왼쪽 자식 노드 인덱스
    let leftChild = 2 * i
    // 오른쪽 자식 노드 인덱스
    let rightChild = 2 * i + 1

    // 왼쪽 자식 노드가 존재하고, 부모 노드가 자식 노드보다 큰 경우
    if (leftChild < n && arr[i] > arr[leftChild]) {
      return 'NO'
    }

    // 오른쪽 자식 노드가 존재하고, 부모 노드가 자식 노드보다 큰 경우
    if (rightChild < n && arr[i] > arr[rightChild]) {
      return 'NO'
    }
  }

  // 모든 노드가 최소 힙 조건을 만족하면
  return 'YES'
}

/*
정수 배열 nums가 주어집니다. 이 배열은 1부터 nums 길이까지의 숫자 중 일부만을 포함하고 있습니다. 배열에 포함되지 않은 숫자들을 찾아 오름차순으로 반환하는 함수 solution을 작성하세요.

제약 사항
1 <= nums.length <= 10^5
배열 nums의 원소는 1부터 nums.length 범위 내의 정수입니다.

 */

function solution1(nums) {
  let length = nums.length
  let missingNumbers = []
  let count = new Array(length + 1).fill(false)

  // 배열을 순회하면서 숫자의 존재 여부를 체크
  for (let num of nums) {
    if (num <= length) {
      count[num] = true
    }
  }

  // 1부터 배열의 길이까지의 숫자 중에서 누락된 숫자를 찾기
  for (let i = 1; i <= length; i++) {
    if (!count[i]) {
      missingNumbers.push(i)
    }
  }

  return missingNumbers
}

/*
문자열 s가 주어집니다. 이 문자열은 유효한 수학적 수식을 포함하고 있습니다. 이 수식을 계산하고, 그 결과를 소수점 둘째 자리까지 반올림하여 반환하는 함수 solution을 작성하세요. 수식이 유효하지 않을 경우, 콘솔에 "잘못된 수식입니다."라고 출력하세요.

제약 사항
문자열 s는 공백을 포함하지 않는 유효한 수학적 수식입니다.
수식에는 정수, 실수, 기본 산술 연산자(+, -, *, /)만 사용됩니다.
s의 길이는 1 이상 100 이하입니다.

*/

function solution2(s) {
  try {
    // 수식을 계산
    let result = eval(s)

    // 결과를 소수점 둘째 자리까지 표현
    return result.toFixed(2)
  } catch (e) {
    console.error('잘못된 수식입니다.')
  }
}

/*
문자열 s가 주어집니다. 이 문자열은 숫자와 다른 문자들을 포함할 수 있습니다. 문자열 내의 숫자들의 등장 빈도를 계산하고, 가장 빈번하게 등장하는 숫자부터 가장 적게 등장하는 숫자 순서대로 정렬하여, 결과를 공백으로 구분된 문자열로 반환하는 함수 solution을 작성하세요.

제약 사항
문자열 s는 ASCII 문자만 포함하며, 길이는 1 이상 10,000 이하입니다.
s 내에 숫자가 하나도 없을 경우 빈 문자열을 반환합니다.

*/

function solution3(s) {
  // 각 숫자의 빈도를 저장할 객체 초기화
  let frequency = {}
  for (let i = 0; i <= 9; i++) {
    frequency[i] = 0
  }

  // 문자열을 순회하며 숫자의 빈도 계산
  for (let char of s) {
    frequency[char]++
  }

  // 빈도를 기준으로 숫자들을 정렬
  let sortedNumbers = Object.keys(frequency).sort((a, b) => frequency[b] - frequency[a])

  // 결과를 공백으로 구분하여 출력
  return sortedNumbers.join(' ')
}

// 농장에 다양한 식물들이 심겨져 있는 field가 주어집니다. 이 field는 0과 1로 이루어진 2차원 배열입니다.
// 1은 식물이 심겨져 있는 위치를 나타내고, 0은 빈 공간을 나타냅니다.
// 주어진 field에서 크기가 n x n인 모든 가능한 서브 그리드를 검사하여
// 가장 많은 식물이 심겨져 있는 서브 그리드 안의 식물 개수를 구하는 함수를 작성하세요.

function solution1(field, n) {
  const rows = field.length
  const cols = field[0].length
  let maxPlants = 0

  // r * c 크기의 모든 가능한 n * n 서브 그리드를 검사
  for (let i = 0; i <= rows - n; i++) {
    for (let j = 0; j <= cols - n; j++) {
      let currentPlants = 0

      // 현재 서브 그리드의 1의 개수를 센다
      for (let k = 0; k < n; k++) {
        for (let l = 0; l < n; l++) {
          currentPlants += field[i + k][j + l]
        }
      }

      // 최대값 갱신
      maxPlants = Math.max(maxPlants, currentPlants)
    }
  }

  return maxPlants
}

// 주어진 배열에서 네 개의 숫자를 선택하여 사각형을 만들 수 있는지 확인하세요.
// 만약 만들 수 있다면, 그 네 변의 길이 합을 반환하고, 만들 수 없다면 0을 반환하세요.

function solution2(arr) {
  // 배열의 길이가 4 미만이면 사각형을 만들 수 없습니다.
  if (arr.length < 4) {
    return 0
  }

  // 배열을 내림차순으로 정렬합니다.
  arr.sort((a, b) => b - a)

  // 가장 큰 네 개의 수가 실제로 사각형을 만들 수 있는지 확인
  for (let i = 0; i <= arr.length - 4; i++) {
    if (arr[i] < arr[i + 1] + arr[i + 2] + arr[i + 3]) {
      return arr[i] + arr[i + 1] + arr[i + 2] + arr[i + 3]
    }
  }

  // 만약 사각형을 만들 수 없다면 0 반환
  return 0
}