[스터디] 알고리즘#1 - 노란불신호등

 

결국은 웬만하면, 매일 알고리즘 1문제씩은 풀어야겠다고 다짐했다..

 

예전에는 프로그래머에게 알고리즘은 크게 중요하지 않다고 생각했다.

실무 경험과 연차가 쌓이면서 더더욱 그런 생각이 커졌었다.

알고리즘은 신입이나 주니어 개발자가 더잘하는것이라고 생각했고,

실무에서는 알고리즘보다는 실무경험에서 오는 트러블슈팅의 노하우와 경험이 더 많은 도움이 될것이라고 생각했다.

하지만, 최근에는 생각이 조금 바뀌었다.

AI시대가 성큼 다가오고 나서, 더욱 생각이 바뀐것 같다.

 

알고리즘은 다양한 사고를 할수있게 해준다는것이다.  

이 부분이 프로그래머에게는 상당한 도움이 된다고 생각한다. 

해당 알고리즘 문제를 풀이를 보고 외우거나, AI에 질문하면서 푸는게 아닌,

끝까지 내가 고민하고 생각해서 푼다는 가정하에 말이다.

 

 

이런 생각으로 매일 1문제의 알고리즘을 풀려고 한다. 

물론 하루안에 풀수없는 문제는 몇일이 걸리겠지만...

풀지못하는 알고리즘은 해답지를 찾지는 않겠다.

(조용히 덮어두었다가...다시 풀어야지 ㅎㅎ)

 

내가 이렇게 하고싶은건, 순수한 나의 성장을 위해서다.

(40대라고 성장을 하지말라는 법은 없다, 특히 프로그래머는 은퇴하는 날까지 실력을 닦아야하는 고달픈 직업이다)

취업의 관문을 위한 스터디가 아니고,

나 잘해요라고 하는 자랑을 위해서도 아니고,

나의 성장을 위해서, 알고리즘 스터디를 해보려고 하기에, 해답지를 보는 행위는 안하기로 했다...(무섭네;;;)

 

오늘 1문제를 풀었는데...1시간 걸린거 같다..ㅠㅠ

역시.. 알고리즘은 어렵다..

꾸준히 하면 실력이 늘겠지

 

알고리즘은 문제를 잘 파악하면 50%는 먹고 들어간다. 그 문제의 파악이 어려워서 그렇지;

오늘 진행한 알고리즘 문제는 '노란불신호등' 문제!!!

 

문제는 링크에 있다. 

https://school.programmers.co.kr/learn/courses/30/lessons/468371%EF%BB%BF

프로그래머스

 

처음 문제를 접했을때, 여러개의 신호등에서 노란불이 겹치는 시간을 구하라고 했을때, 

바로 이건, 최대 공배수를 이용한 것이라고 직감이 왔다.

 

우선 신호등들의 최대 공배수를 구한다. 해당 최소공배수안에서 겹치는 노란불이 존재할수 있기 때문이다.

그리고 그 최소공배수안에서 신호등별로 노란불이 존재하는 시간을 계산해서, 각각의 list에 넣어두고, 

해당 list들에서 노란불이 켜지는 초가 동일하게 존재하는 값을 뽑아낸다.

없으면, 겹치지 않는걸로 판단하면 된다.

 

코드는 아래와 같다.

class Solution {
    fun gcd(a: Long, b: Long): Long {
        return if (b == 0L) a else gcd(b, a % b)
    }

    fun lcm(a: Long, b: Long): Long {
        return a / gcd(a, b) * b
    }

    fun lcmOfNumbers(numbers: List<Int>): Long {
        return numbers
            .map { it.toLong() }
            .reduce { acc, num ->
                lcm(acc, num)
            }
    }

    fun solution(signals: Array<IntArray>): Int {
        if (signals.size !in 2..5) return -1

        var answer = -1

        val lcm = lcmOfNumbers(signals.map { it.sum() }).toInt()
        println("lcm = $lcm")

        val lists = signals.mapIndexed { index, signal ->
            val result = mutableSetOf<Int>()
            for (cnt in (0..lcm)) {
                for (i in 1..signal[1]) {
                    result.add((signal[0] + i) + signal.sum()*cnt)
                }
            }
            result
        }

        println("res = $lists")
        val common = lists
            .map { it.toSet() }
            .reduce { acc, set ->
                acc intersect set
            }

        if (common.isNotEmpty()) {
            answer = common.first()
            println("answer = $answer")
        }
        return answer
    }
}

fun main(args: Array<String>) {
    val a = arrayOf(intArrayOf(2,1,2),intArrayOf(5,1,1))
    val b = arrayOf(intArrayOf(2,3,2),intArrayOf(3,1,3),intArrayOf(2,1,1))
    val c = arrayOf(intArrayOf(3,3,3),intArrayOf(5,4,2),intArrayOf(2,1,2))
    Solution().solution(a)
}

 

개선사항이 하나 있는데 이건 그냥 넘어갈려고 했는데.. (귀찮네;;;)

지금은 최소공배수까지 모든 노란불의 시간을 모두 구하고 신호등들에서 같은 시간을 판단하는데,

최대 공배수까지 가지 않고도 노란불 시간이 겹칠수있기에, 모든 노란불 시간을 최소공배수까지로 모두 구할필요는 없다고 생각한다.

이럴려면, 앞에서 구한 노란불 시간을 누적해서 갖고있게 만들고, 최대공약수까지 가기전에 매번 판단을 하면된다.

 

class Solution {
    fun gcd(a: Long, b: Long): Long {
        return if (b == 0L) a else gcd(b, a % b)
    }

    fun lcm(a: Long, b: Long): Long {
        return a / gcd(a, b) * b
    }

    fun lcmOfNumbers(numbers: List<Int>): Long {
        return numbers
            .map { it.toLong() }
            .reduce { acc, num ->
                lcm(acc, num)
            }
    }

    fun solution(signals: Array<IntArray>): Int {
        if (signals.size !in 2..5) return -1

        var answer = -1

        val lcm = lcmOfNumbers(signals.map { it.sum() }).toInt()
        println("lcm = $lcm")

        var sList = mutableListOf<MutableSet<Int>>()
        signals.forEach { sList.add(mutableSetOf()) }

        for (cnt in (0..lcm)) {
            signals.mapIndexed { index, signal ->
                for (i in 1..signal[1]) {
                    sList[index].add((signal[0] + i) + signal.sum() * cnt)
                }
                sList
            }

            println("res = $sList")

            val common = sList
                .map { it.toSet() }
                .reduce { acc, set ->
                    acc intersect set
                }

            if (common.isNotEmpty()) {
                answer = common.first()
                println("answer = $answer")
                break
            }
        }

        return answer
    }
}

fun main(args: Array<String>) {
    val a = arrayOf(intArrayOf(2,1,2),intArrayOf(5,1,1))
    val b = arrayOf(intArrayOf(2,3,2),intArrayOf(3,1,3),intArrayOf(2,1,1))
    val c = arrayOf(intArrayOf(3,3,3),intArrayOf(5,4,2),intArrayOf(2,1,2))
    Solution().solution(a)
}

 

 

그런데, 큰 성능상의 이득은 없어보이긴한다.. (다만 메모리를 좀더 아낄수있다 정도?!)

 

그런데... 이문제 푸는데, 1시간정도 걸렸는데..

저런걸 요즘 신입들은 제한된 시간에 몇문제씩 푼다는건가;; ㅠㅠ

어렵다 쩝.

 

그런데 정답률 29%네.. 어려운 문제긴 한가본다.. 그런데 레벨1 문제로 되있던데;;;