[LeetCode] 1394. Find Lucky Integer in an Array

출처: https://leetcode.com/problems/find-lucky-integer-in-an-array/

Find Lucky Integer in an Array - LeetCode

문제

정수 배열 arr에서 행운의 정수는 정수 값과 그 값이 배열 안에서 등장하는 빈도수가 동일한 정수이다.

배열에서 행운의 정수 를 반환하라. 만약 여러개 존재하면 가장 큰 정수를 반환하고, 없다면 -1을 반환하라.

예제

Input: arr = [2,2,3,4]
Output: 2

Explanation: The only lucky number in the array is 2 because frequency[2] == 2.

Input: arr = [1,2,2,3,3,3]
Output: 3

Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them.

풀이

배열에서 행운의 정수를 찾기 전, 배열을 내림차순으로 정렬한다. 배열 내에서 행운의 정수가 여러개 존재하더라도 처음 찾는 행운의 정수를 바로 반환하기 위함.

 

두 변수 val과 freq를 사용하여 행운의 변수를 찾기 시작.

• val: 행운의 정수인지 체크하고자 하는 정수 값
• freq: val의 확인된 빈도 수

val = arr[0], freq = 1로 초기화를 진행하고, 반복문을 이용해서 val와 arr[i]의 값을 비교하여 val과 freq를 업데이트한다.

• val == arr[i]: freq += 1
• val != arr[i]: 행운의 정수 체크 + val = arr[i], freq = 1 설정
  • 이전 단계에서 정렬을 수행했기 때문에, 동일한 정수는 한 곳에 모여 있음.
  • 값이 달라졌다면 이후 인덱스에서는 현재 값이 등장하지 않음을 뜻하기에 이 단계에서 행운의 정수를 체크

function findLucky(arr) {
  arr.sort((a,  b) => b - a);

  let val = arr[0], freq = 1;
  for (let i = 1; i < arr.length; i++) {
      if (arr[i] != val) {
          if (freq == val) return val;
          val = arr[i];
          freq = 0;
      }
      freq +=1;
  }
  if (freq == val) return val;

  return -1;
}

Github: 1394.js

opwe37/Algorithm-Study