๐Ÿ”ฅTIL๐Ÿ”ฅ์ŠคํŒŒ๋ฅดํƒ€ | ์•ฝ์ˆ˜ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜

hyihyiยท2023๋…„ 11์›” 24์ผ
0

TIL

๋ชฉ๋ก ๋ณด๊ธฐ
5/70
post-thumbnail

์•ฝ์ˆ˜ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜

๋ฌธ์ œ๋งํฌ

์ •์ˆ˜ N์ด ์ž…๋ ฅ๋์„ ๋•Œ N์˜ ์†Œ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์งœ๋ณด์ž.

์•ฝ์ˆ˜๋ž€?

์–ด๋–ค ์ˆ˜๋ฅผ ๋‚˜๋ˆ„์–ด ๋–จ์–ด์ง€๊ฒŒ ํ•˜๋Š” ์ˆ˜
ex) 12์˜ ์•ฝ์ˆ˜๋Š”? 1,2,3,4,6,12

์–ด๋–ป๊ฒŒ ํ’€์–ด์•ผ ํ• ์ง€ ์ƒ๊ฐํ•ด ๋ณด์ž

  1. 12์˜ ์ œ๊ณฑ๊ทผ์ธ 3๊นŒ์ง€, 0์œผ๋กœ ๋‚˜๋ˆ„์–ด ๋–จ์–ด์ง€๋Š” ์ˆ˜๋ฅผ ๊ตฌํ•ด๋ณด์ž
    12 % 1 = 0
    12 % 2 = 0
    12 % 3 = 0
  2. 1,2,3์ด ๊ตฌํ•ด์กŒ๋‹ค
  3. ์ด๋ ‡๊ฒŒ ๊ตฌํ•ด์ง„ ์ˆซ์ž๋“ค๋กœ ๋‹ค์‹œ 12๋ฅผ ๋‚˜๋ˆ„์ž
    12 / 1 = 12
    12 / 2 = 6
    12 / 3 = 4
  4. 12,6,4๊ฐ€ ๊ตฌํ•ด์กŒ๋‹ค
  5. 1,2,3,4,6,12๊ฐ€ ๋‚˜์™”๋‹ค.

ํ’€์ด ์ฝ”๋“œ

import kotlin.math.sqrt

class Solution {
    fun solution(n: Int): Int { 
        
        val N = (sqrt(n.toDouble())).toInt()
        val answerList = mutableListOf<Int>()
        
        for (i in 1..N){
            if(n % i == 0){
                answerList.add(i)
            }
        }
        
        for (i in 0..answerList.size-1){
            if(n % answerList[i] == 0){
                answerList.add(n / answerList[i])
            }
        }
        
        return answerList.distinct().sum()
    }
}

์‚ฌ์šฉํ•œ ๊ฐœ๋…๋“ค

  1. ์ œ๊ณฑ๊ทผ์„ ๊ตฌํ•˜๊ธฐ ์œ„ํ•ด ์‚ฌ์šฉํ•œ math ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ์— ์ •์˜๋œ sqrtํ•จ์ˆ˜
import kotlin.math.sqrt //import ํ•ด์ค˜์•ผ ํ•œ๋‹ค.

print(sqrt(4.0)) 		//Double์ด๋‚˜ Float ์ž๋ฃŒํ˜•์ด ๋“ค์–ด๊ฐ€์•ผ ํ•œ๋‹ค.
>> 2.0
  1. ์ˆ˜์ •๊ฐ€๋Šฅํ•œ ๋ฆฌ์ŠคํŠธ์ธ mutable list
    Collection์—๋Š” List, Map, Set์ด ์žˆ๋‹ค.
    ๋˜ํ•œ Mutable๊ณผ immutable์œผ๋กœ ๊ตฌ๋ถ„๋œ๋‹ค.

์ฝ”ํ‹€๋ฆฐ์˜ List๋Š” ๊ธฐ๋ณธ์ ์œผ๋กœ immutable ์ด๋‹ค.
immutable : ๋ถˆ๋ณ€์˜

val list: List<Int> = List(3,  {i -> i})
val list: List<Int> = listOf(0, 1, 2)

์œ„์ฒ˜๋Ÿผ ์„ ์–ธ๋œ ๋ฆฌ์ŠคํŠธ๋“ค์€ ์ˆ˜์ •์ด ๋ถˆ๊ฐ€๋Šฅํ•˜๋‹ค.

ํ•˜์ง€๋งŒ mutable๋กœ ์„ ์–ธํ•  ๊ฒฝ์šฐ ๊ฐ’์„ ๋ณ€๊ฒฝํ•  ์ˆ˜ ์žˆ๋‹ค.

val answerList = mutableListOf<Int>()
answerList.add(3)
print(answerList)
>> 3
  1. ๋ฆฌ์ŠคํŠธ์—์„œ ์ค‘๋ณต์š”์†Œ ์ œ๊ฑฐ
answerList.distinct()

๋” ์ƒ๊ฐํ•ด ๋ด์•ผ ํ•  ๊ฒƒ

๋‹ค๋ฅธ ์‚ฌ๋žŒ์˜ ํ’€์ด๋ฅผ ๋ดค๋Š”๋ฐ

answer = (1..n).filter { n % it == 0 }.sum()

์ด๋Ÿฐ ํ˜•์‹์œผ๋กœ ํ’€์–ด๋†จ๋‹ค.
๋‚ด๊ฐ€ ํ‘ผ ๋ฐฉ์‹์€ ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ O(โˆšN)์ด ๋˜๋ฏ€๋กœ, 10์–ต์˜ ์ž…๋ ฅ์ด ๋“ค์–ด์˜จ๋‹คํ•ด๋„, ์•ฝ 3๋งŒ๋ฒˆ์˜ ์—ฐ์‚ฐ์œผ๋กœ ์•ฝ์ˆ˜๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.
๊ทผ๋ฐ ์œ„์˜ ํ’€์ด๋Œ€๋กœ ํ’€๋ฉด n๊นŒ์ง€ ํ•˜๋‚˜ํ•˜๋‚˜ 0์œผ๋กœ ๋‚˜๋ˆ ์ง€๋Š”์ง€ ๊ฒ€์‚ฌํ•ด์„œ ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ O(N)์ด์ง€ ์•Š์„๊นŒ??

๐Ÿ˜ฎ๋” ๊ณต๋ถ€ํ•ด์•ผ ํ•  ๊ฒƒ

Collection์— ๋Œ€ํ•ด ๋” ๊ณต๋ถ€ํ•ด ๋ณด์ž
์ฐธ๊ณ  ์ž๋ฃŒ : https://soopeach.tistory.com/62

profile
๋‚ด๊ฐ€ ์ดํ•ดํ•˜๊ธฐ ์‰ฝ๊ฒŒ ์“ฐ๋Š” ๋ธ”๋กœ๊ทธ

0๊ฐœ์˜ ๋Œ“๊ธ€