1/16 ~ 1/22

Question

1/16 ~ 1/22

Closed this issue 2 years ago · 7 comments

Answer 1 · 2023-01-16T07:20:48.000Z

Day 1

내적

// ex
let arr = [1, 2, 3, 4, 5]
let negativeArr = arr.map(-)
print(negativeArr) // [-1,-2,-3,-4,-5]

단항 연산자를 고차함수의 인자로 넘겨줄 수 있음
https://mariusschulz.com/blog/passing-swifts-operator-functions-to-higher-order-functions

예산

func solution(_ d:[Int], _ budget:Int) -> Int {
    var rest = budget
    return d.sorted(by: <).filter { num in
        rest -= num
        return rest >= 0
    }.count
}

작은것부터 구매해야 최대한 예산안에서 많이 구매할 수 있다는 아이디어
고차함수의 활용이 포인트

실패율

func solution(_ N:Int, _ stages:[Int]) -> [Int] {
    var rate = [Double]()
    for i in 1...N {
        let arr = stages.filter { $0 >= i }.count
        let count = stages.filter { $0 == i }.count
        if arr > 0 { rate.append(Double(count) / Double(arr)) }
        else if arr == 0 { rate.append(0) }
    }
    return rate.enumerated().sorted { lhs, rhs in
        if lhs.1 == rhs.1 {
            return lhs.0 < rhs.0
        }
        return lhs.1 > rhs.1
    }.map { $0.0 + 1 }
}

시간 초과 나는 것이 포인트 : 고차함수를 여러개 체이닝해서 사용해서 그런 듯 하다. 가독성도 별로 안 좋다.
접근 방식은 맞는 것 같아서 코드만 다듬으면 될 것 같다.

func solution(_ N:Int, _ stages:[Int]) -> [Int] {
    var rate = [(Int, Double)]()
    var failure: [Int: Int] = [:]
    
    // Failure
    for val in stages {
        failure[val, default: 0] += 1
    }

    // Calculate
    var arrived = stages.count
    for i in 1...N {
        let notClear = failure[i, default: 0]

        if arrived == 0 { rate.append((i, 0)) }
        else { rate.append((i, Double(notClear) / Double(arrived)))}
        
        arrived -= notClear
    }
    
    // Sort
    return rate.sorted { lhs, rhs in
        if lhs.1 == rhs.1 {
            return lhs.0 < rhs.0
        }
        return lhs.1 > rhs.1
    }.map { $0.0 }
}

이전 풀이에서 문제였던 부분은 반복문 안에서 filter를 걸어서 숫자를 계산하는 부분이었다. stages의 길이는 최대 200,000개가 들어오는데 최악의 경우에는 반복문 안에서 1억 회의 연산을 수행하게 된다. 일반적으로 1억 회의 연산 시에 1초 정도의 시간이 걸린다고 하는데(파이썬의 경우 2000만번의 연산 시에 1초 정도의 시간 소요) 제한 시간이 1초라고 한다면 시간 초과가 나는 것이다. 이전의 풀이로 TC를 돌려보면 6000ms가 나오는 경우가 있는데 이 경우에는 6초가 걸린다...
그래서 해당 부분을 고치려고 했는데 떠올랐던 것이 딕셔너리를 이용해서 스테이지의 실패자 수를 계산하는 것이었다. 그럼 상수의 시간으로 실패자 수에 접근이 가능하기 때문에 시간 효율을 많이 개선할 수 있다고 판단했다.

기억할 문법

dictionary default value
sort multiple criteria

3진법 뒤집기

.init(_, radix:) : String과 Radix가 주어졌을 때 정수를 반환해주는 인스턴스 메서드
Int, String에 대한 생성자가 모두 존재한다. String의 경우 기본 radix가 10이다.
pow(float, float) -> float
그리고 중간에 숫자를 뒤집어 줄 필요가 없는 이유는 진수와 인덱스 개념을 이해하면 쉽게 파악할 수 있다. 진수는 오른쪽부터, 인덱스는 왼쪽부터 0에서 시작하기 때문에 어차피 계산만 해야 하는 것이라면 숫자를 뒤집을 필요가 없다.
진법 변환과 거듭제곱에 대한 메서드를 잘 사용할 수 있는지에 대한 문제이고, 문법에서 실수할 수 있는 요소들이 있으므로 그것만 잘 정리해두면 유용하게 사용할 수 있을 것 같다.

두개 뽑아서 더하기

func solution(_ numbers:[Int]) -> [Int] {
    var sets = Set<Int>()
    for i in numbers.indices {
        for j in numbers.indices {
            if i == j { continue }
            else { sets.insert(numbers[i] + numbers[j]) }
        }
    }
    return sets.sorted()
}

✨ set에도 정렬이 가능하다는 점

예상 대진표

나름 아이디어 잘 생각해서 푼 것 같음
while문 사용
2의 배수의 특징을 이용해서 풀이

Answer 2 · 2023-01-16T15:54:21.000Z

Day2

뉴스 클러스터링

스스로 품
확실히 레벨 2랑 레벨 1 난이도 차이 크다고 또 느꼈음
빡구현 문제라고 생각했음 (이정도의 구현 문제를 어렵다고 느끼지 않고 자연스럽게 푸는 순간이 오면 성장했다고 할 수 있을 것 같다.) 차근차근 풀어서 맞추긴 했지만 약간 버벅이는 느낌이 들었다. 40분 정도 걸렸는데 중간에 함정 같은 것은 없어서 처음에 잘 설계하고, 문법 잘 숙지한 뒤, 순차적으로 구현만 한다면 30분 이내로 충분히 풀 수 있는 문제라고 생각한다.
해당 문제는 구현 문제라서 문제 분해 능력, 그리고 아이디어 도출이 가장 중요했다.
문법적으로는 asciiValue가 쓰였고(Swift 5 이상부터 사용가능), Set을 이용해서 쉽게 풀려고 했으나 중복된 조합이 제거되면 안되는 이슈가 있어서(이게 함정이라면 함정일 것 같다.) 그냥 배열로 만들어서 직접 계산해주었다. (집합 Set을 쓸 수 있었다면 좋았을 부분은 교집합과 합집합을 쉽게 구할 수 있다는 점이다.)
확실히 초반에 메서드 명만 쭉 적어놓고 설계한 다음에 구현으로 들어가니까 머릿속이 정리가 되고 방향을 잃지 않을 수 있었던 것 같다.
자료형의 변환이 잦았음

신규 아이디 추천

이 문제의 해결책은 꺾이지 않는 마음 ..
진짜 Swift 문자열은 .. 쉽지 않다...

메뉴 리뉴얼

풀긴 풀었는데 시간이 오래걸렸다. 집중을 잘 못한 것도 있고, 문법적으로 매끄럽게 바로바로 쓰지 못했다. 시간 많이 걸렸으니까 틀렸다고 봐도 무방할 것 같다.
dictionary도 collection 타입이라 filter, map 등등을 쓸 수 있었다.
보자마자 조합이 떠오르는 문제였는데, 조합에 대한 코드가 한번에 작성되지 않아서 시간이 좀 걸렸다.
개수 체크에는 dictionary가 적합하다고 생각해서 해당 자료구조를 사용했는데 적절했던 것 같다.
풀고 나니깐 쌩구현 문제였다.

행렬 테두리 회전하기

진짜 이 문제 풀면서 마음이 꺾일 뻔 했다..ㅎ
결론만 생각해보면 어려운 문제는 아니다. 그냥 구현문제다. 시간이 오래 걸렸다는 건 아직 내 구현력이 올라오지 않았다는 소리겠지. 그래도 이전보다 문제에 대한 끈기가 많이 높아져서 굉장히 만족스럽다.
회전을 어떻게 할지에 대한 부분이랑, 숫자를 계속해서 덮어주는 부분에 대한 문제를 어떻게 해결할지가 관건이었다.
좌표에 대한 부분은 정말 많이 나오는 부분이기 때문에 board 생성이나 좌표 이동에 있어서 친근해질 필요가 있어보인다.

타겟 넘버

dfs(재귀)를 이용해서 쉽게 풀 수 있는 문제였다.
처음에는 숫자 4개 중 2개, 이런식으로 모든 경우를 생각해서 어렵게 접근했었는데 결국 numbers를 모두 이용해서 만드는 것이라서 최종적인 배열만 신경쓰면 됐다. 조합에 대해서 중복이 생길 수 있기 때문에 Set을 이용했다.
덧셈, 뺄셈만 신경쓰면 돼서 연산자를 신경쓰는게 아니라 4, -4 이런식으로 숫자 자체만 바꿔서 생각해주면 된다.

import Foundation

func solution(_ numbers:[Int], _ target:Int) -> Int {
    var sets = Set<[Int]>()

    func dfs(_ index: Int, _ arr: [Int]) {
        if index == numbers.count {
            sets.insert(arr)
            return 
        }
        
        for val in [numbers[index], -numbers[index]] {
            let elem = arr + [val]
            dfs(index + 1, elem)
        }
    }

    dfs(0, [])
    return sets.filter { $0.reduce(0, +) == target }.count
}

마법의 엘리베이터

TC 확인이 중요했던 문제인 것 같다.
자릿수를 가지고 노는 문제였는데, 어느 정도의 수학적 사고가 필요하다.
그리고 경우를 각각 잘 나누어서 코드를 작성하는 것이 중요했다. (5초과, 5동일, 5미만)

Answer 3 · 2023-01-18T08:55:13.000Z

Day 3

수식 최대화

계산하는 메서드에서 시간을 너무 많이 씀
아이디어 자체는 크게 어렵지는 않았는데 아직 구현력이 많이 떨어지는 것 같다.
Operator의 경우의 수는 6개 밖에 되지 않기에 전역변수로 만들어서 사용했음.
그리고 계산은 Queue를 4개 두어서 진행했음.

func calculate(_ expArr: [String], _ `operator`: [String]) -> Int {
    var queues = Array(repeating: [String](), count: 4)
    queues[0] = expArr
    
    for (i, op) in `operator`.enumerated() {  // ["*", "-", "+"]
        while !queues[i].isEmpty {
            let exp = queues[i].removeFirst()

            if exp == op {
                let num1 = queues[i+1].popLast()!
                let num2 = queues[i].removeFirst()
                let result = cal(num1, num2, op)
                queues[i+1].append(String(result))
                
            } else {
                queues[i+1].append(exp)
            }
        }
    }

    return abs(Int(queues[3][0])!)
}

계산 기능이 참 쉽지 않았다.

Answer 4 · 2023-01-19T01:01:07.000Z

Day 4

네트워크

Set이용해서 방문 여부 체크하는 것보다 2차원배열로 체크하는 것이 속도가 더 빠르다.
bfs 이제 새록새록 기억이 떠오른다.
이전에 풀었었던 bfs 문제를 몰아서 좀 풀어봐야겠다.
https://github.com/Taehyeon-Kim/PS/tree/master/BFS%2BDFS (내가 풀었던 문제 모음)

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    var answer = 0
    var visited = Set<Int>()
    
    func bfs(_ n: Int, _ graph: [[Int]], _ start: Int, _ visited: inout Set<Int>) {
        var queue = [start]
        visited.insert(start)
        
        while !queue.isEmpty {
            let v = queue.removeFirst()
            
            for i in 0..<n {
                if !visited.contains(i) && graph[v][i] == 1 {
                    queue.append(i)
                    visited.insert(i)
                }
            }
        }
    }
    
    for i in 0..<n {
        if !visited.contains(i) {
            bfs(n, computers, i, &visited)
            answer += 1
        }
    }
    
    return answer
}

Answer 5 · 2023-01-19T07:54:03.000Z

1주차와 마찬가지로 레벨3 문제를 쓰윽 보았을 때 든 생각은 알고리즘에 대한 어느 정도 학습이 필요하다는 생각이 강하게 들었다. 무작정 문제를 풀기보다는 어느 정도 지식을 탑재하고 문제를 보는 것이 좋을 듯 하다.

알고리즘 학습하기

bfs vs dfs
플로이드 워셜 vs 다익스트라
우선순위 큐 vs 이진 검색 트리

Answer 6 · 2023-01-21T07:53:30.000Z

Day 6

디스크 컨트롤러

아이디어를 생각해내지 못함
어렵다
SJF(Shortest Job First) 알고리즘을 직접 구현하는 것과 동일함
작업을 수행하는 동안 도착하는 작업, 작업이 없는 동안에 들어오는 작업에 대한 구분을 얼추했지만 명확하게 그러한 조건을 나누지 못했음. -> 무작정 문제를 파악하기 보다는 좀 더 조건을 명시적으로 나누어 보는 것도 좋을 듯 하다. (그러니까, 어떤 경우(A), 어떤 경우(B) 이런 식으로 명확히 나눈 후에 글로 작성해보자. 머릿속으로 추상적으로 생각하지 말고.)

Answer 7 · 2023-01-22T02:44:26.000Z

Day 7

디스크 컨트롤러

결국 주말동안 고민하다가 블로그 풀이를 보고 문제 해결
어디서 막힌 걸까 곰곰히 생각해보면 일단 아이디어를 완전하게 떠올리지 못했다. 그래서 구현은 당연하게 실패할 수 밖에 없었다.
차분하게 정리하지 못했던 것 같다.
작업시간이 짧은 것부터 처리해야 한다는 부분까지는 생각했으나 정렬을 해야하는 것은 떠올리지 못했고, 작업이 끝나는 시점을 기준으로 들어온 작업(이전 작업의 종료 시간보다 요청 시점이 빠른 작업)에 대해서 가장 짧은 수행시간의 작업을 선택해야 한다는 부분을 떠올리지 못했다. 대략 30% 정도만 떠올렸던 것이다. 여기서 느낀 것은 아직 문제 사고력 자체에 대한 능력이 많이 부족한 것 같다는 것이다.

어떻게 해결할 수 있을까?

Job Scheduling, Shortest Job First Algorithm 등의 배경지식을 알았다면 조금 더 쉽게 접근가능 -> 배경 지식을 키우는 방법
명확하게 조건을 적는 연습
- ex. 1. 수행 시간이 짧은 것부터 처리 / 2. 작업이 끝나는 시점을 기준으로 상황이 나눠질 수 있을 것 같으니까 이 기준으로 생각해보자 등..
문제 많이 풀어보기 -> 가장 현실성 있을 듯

참고

Job Scheduling

ATT(Average Turnaround Time)이 가장 작아지는 스케줄링 알고리즘은 SJF 알고리즘. Job Scheduling 문제는 Greedy 알고리즘으로 최적해를 찾을 수 있다. (아.. 운체시간에 과제 열심히 했던 것 같은데)
Ready Queue(준비 큐) : 프로세스는 CPU를 할당받을 때(dispatch)까지 Ready Queue에서 대기한다.

순위

플로이드 워셜 알고리즘 유형의 문제인지는 전혀 중요하지가 않은 것 같다.
아이디어를 잘 떠올리는 것이 중요한 문제다. 문제를 풀면서 계속 드는 생각은 문제의 아이디어를 떠올리는 것이 가장 중요한 것 같다는 것이다.

순위를 결정짓기 위해서는 자기 자신을 제외한 나머지 선수와의 이기고 지는 관계만 파악하면 된다는 아이디어
자기 자신(S)이 이긴 선수(A)가 다른 선수(B)를 이긴다면, S도 자연스레 B를 이긴 것이 된다는 아이디어

1/16 ~ 1/22

LV1(6)

LV2(6 + 1)

LV3(3)

Day 1

내적

예산

실패율

기억할 문법

3진법 뒤집기

두개 뽑아서 더하기

예상 대진표

Day2

뉴스 클러스터링

신규 아이디 추천

메뉴 리뉴얼

행렬 테두리 회전하기

타겟 넘버

마법의 엘리베이터

Day 3

수식 최대화

Day 4

네트워크

알고리즘 학습하기

Day 6

디스크 컨트롤러

Day 7

디스크 컨트롤러

어떻게 해결할 수 있을까?

참고

Job Scheduling

순위