[LeetCode] Find Lucky Integer in an Array

🔒 문제

🧠 생각의 흐름

1. 내림차순 정렬을 해서
   앞에서부터 계산해야 가장 큰 행운의 숫자를 더 빠르게 구할 수 있겠다.

2. 검사 대상 숫자와 숫자의 갯수, break 탈출 'index' 만 킵하면 되겠다.
   검사 대상숫자 == 숫자의 갯수 일 때 그 번호가 행운의 번호

3. index 가 len 을 넘어갈 경우 -1 을 return

🔑 풀이 (Go)

import (
	"sort"
	"testing"
)
type Numbers []int

func (numbers Numbers) Len() int 			{ return len(numbers) }
func (numbers Numbers) Swap (i, j int)  	{ numbers[i], numbers[j] = numbers[j], numbers[i] }

// 우선순위 더 낮은대로 정렬 이미 된 상태인지 확인.
// 더 크면 편-안한 상태,
// 작거나 같으면 불편한 상태 Swap() 호출
// 그냥 이름 신경쓰지 말고 Less == 앞 i 가 j 보다 먼저 와야 하는대로 배치되 있는 상태니? 임.
func (numbers Numbers) Less (i, j int) bool { return numbers[i] > numbers[j] }

func (numbers Numbers) getNumCount(startIndex int) (bool, int) {

	count := 0
	// 자신과 다를 때 까지 만나야함.
	targetNumber := numbers[startIndex]

	for i := startIndex; i < len(numbers) && targetNumber == numbers[i]; i++ {
		count++
	}

	if count == targetNumber {
		return true, targetNumber
	} else {
		return false, count
	}

}

func findLucky(arr []int) int {
	numbers := Numbers(arr)
	sort.Stable(numbers)

	for totalCount := 0; totalCount < len(numbers); {
		isLucky, count := numbers.getNumCount(totalCount)
		totalCount += count

		if isLucky { return count }
	}

	// Not found
	return -1
}

🧪 Test Code

func TestLucky1(test *testing.T) {
	result := findLucky([]int{2, 2, 3, 4})

	if result != 2 {
		test.Errorf("Failed! %v\n", result)
	}
}

func TestLucky2(test *testing.T) {
	result := findLucky([]int{1, 2, 2, 3, 3, 3})

	if result != 3 {
		test.Errorf("Failed! %v\n", result)
	}
}

결과

속도는 32.26 % 더 빠르고 메모리는 45.16 % 덜 쓰고
^^기모링딩동