Created
December 3, 2018 06:22
-
-
Save livelikeabel/9cb8416c5bf661211d385b9d3c240581 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function getZeroOrOne() { | |
| return Math.floor(Math.random() * 2) | |
| } | |
| function getRandom(n) { | |
| if (!n || n < 1) return | |
| if (n === 1) return 0 | |
| /** | |
| * 중첩 배열 만들기 | |
| */ | |
| // 2의 몇제곱인지 찾기. | |
| let m = 0 | |
| let acc = 1 | |
| while (acc < n) { | |
| acc *= 2 | |
| m += 1 | |
| } | |
| // ex) n == 3, numbers = [0, 1, 2, -1] | |
| // ex) n == 4, numbers = [0, 1, 2, 3] | |
| // ex) n == 5, numbers = [0, 1, 2, 3, 4, -1, -1, -1, -1] | |
| let numbers = [] | |
| for (let i = 0; i < acc; i++) { | |
| if (i < n) { | |
| numbers.push(i) | |
| } else { | |
| numbers.push(-1) | |
| } | |
| } | |
| // [0,1,2, .... ] 배열을 두개씩 계속 병합해서 [[[0, 1], [2, 3], ...]...] 을 만든다. | |
| let depth = 0 | |
| while (depth < m - 1) { | |
| let newNumbers = [] | |
| for (let j = 0; j < numbers.length; j += 2) { | |
| const merged = [numbers[j], numbers[j + 1]] | |
| newNumbers.push(merged) | |
| } | |
| numbers = newNumbers | |
| depth += 1 | |
| } | |
| let result; | |
| do { | |
| let val = numbers; | |
| for (let k = 0; k < m; k++) { | |
| val = val[getZeroOrOne()] | |
| } | |
| result = val | |
| } while(result < 0); | |
| return result | |
| } | |
| // 테스트. | |
| console.log(getRandom(5)) | |
| // 0 or 1 or 2 or 3 or 4 | |
| console.log(getRandom(3)) | |
| // 0 or 1 or 2 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
작성하신 코드의 시간/공간 복잡도가 어떻게되는지 설명해 주세요.