1/9 ~ 1/15

Question

1/9 ~ 1/15

Closed this issue 2 years ago · 6 comments

Answer 1 · 2023-01-09T08:59:02.000Z

Day 1(8)

K번째 수 ~ 소수 만들기(대략 3-4시간 정도 공부한 것 같다.)

오늘 푼 문제들은 전부 단순 구현이었다. Lv 1. 문제들이라서 그런 것 같다. PS 공부한지 오래돼서 감을 다 잃었었는데 조금씩 회복되는 느낌이다.
단순 구현에 있어서는 확실히 문제를 작게 분해해보는 접근이 정말 중요하다는 생각이 든다. 문제를 작게 분해해보고 순차적으로 접근하는 것을 차근차근 몸에 체화시켜야한다.
구현 문제 같은 경우는 풀이 흐름이 잡혔을 경우 빠르게 아는 문법(if, for, while, map 등)으로 빨리 접근해서 구현하는 것이 중요하다고 생각이 든다. 좀 더 나은 풀이에 대해서는 문제를 풀고 난 뒤에 생각해보고 확인해보자.
자잘한 문법들은 중간중간 잘 정리해야 할 것 같다. 문법 숙지 부분에서 1~2분씩 단축되는 것이 생각보다 크다. 특히 String, Array 관련한 문법은 확실히 숙지하자.

◾️ k번째 수

map 이용하면 되는 문제
이전 풀이보다는 라인 수가 늘어났는데 가독성이 더 높아진 것 같다.
Array에 접근할 때 Range로 접근 가능 : Slicing 효과

◾️ 키패드 누르기

해당 문제는 작은 문제 단위로 분해해서 접근하면 나름 쉽게 풀리는 문제였다.
주요하게 생각해야 했던 부분은 역시나 거리 계산 부분이었고, 절대값을 이용해서 거리를 잘 판단하면 됐다.
키패드의 경우 0~9까지 고정이기 때문에 이 부분도 잘 사용해야 했다.

else {
    let ld = distance(point(lp), point(num))
    let rd = distance(point(rp), point(num))
    if ld == rd { 
        if hand == "left" { lp = num }
        else if hand == "right" { rp = num }
        return hand.capitalized.map { String($0) }[0] 
    }
    if ld > rd {
        rp = num
        return "R"
    } else {
        lp = num
        return "L"
    }
}

2, 5, 8, 0의 경우 거리 계산 후 좌, 우 손가락을 움직이는 부분을 잘 재설정 해주어야 했다. (나 같은 경우에도 실수를 한 부분이었음)

hand.capitalized.map { String($0) }[0]
// "right" -> "RIGHT" -> "R"
// "left" -> "LEFT" -> "L"

다음과 같이 쓰기 위해서 capitalized 이용함
prefix를 쓰려고 했는데 return type이 맞지 않아서 map, subscript로 접근

키패드 누르기 문제같은 경우는 가독성을 좀 더 높일 수 있도록 리팩토링하는 것도 괜찮아 보임

◾️ 체육복

그리디로 유형이 분리되어 있기는 하지만 직관에 의해서 풀리는 문제였다.

// 좌
if index - 1 >= 0 && array[index - 1] == 0 {
    array[index - 1] += 1
    array[index] -= 1
} 
// 우
else if index + 1 < n && array[index + 1] == 0 {
    array[index + 1] += 1
    array[index] -= 1
}

첫번째 원소와 마지막 원소의 경우 array boundary를 넘어가는 경우가 생기므로 조건을 잘 신경써줘야 했다.

◾️ 인형뽑기

Stack 자료구조가 너무나 선명하게 떠오른 문제였다. Array로 접근했어도 문제는 없었다. (가장 끝에 있는 원소만 제거하는 식이었기 때문)
row 기준으로 되어 있는 board를 column 형태로 바꿔서 접근했었는데, 해당 접근 방식은 이후에도 쓰일 수 있는 가능성이 높다고 생각한다. 다시 정리해보도록 하자.

removeLast, dropLast

removeLast
dropLast

◾️ 모의고사

처음에는 zip으로 접근하려고 했으나 실패했다. answers의 길이가 5 이하인 경우에는 문제가 없었으나, 그보다 큰 경우에는 길이 비교 시 answers의 전체 길이가 잘리기 때문이었다.
그래서 % 연산자를 이용하는 접근으로 다시 생각해보니 훨씬 짧게 풀렸다.

◾️ 로또의 최고순위와 최저순위

딕셔너리 이용함 (순위 같은 경우 1~6까지 밖에 없으므로 해당 자료구조 이용하는 것이 효율적이라고 판단)
나름 코드 짰는데 좀 더 짧게 줄일 수 있을 것 같음 -> 고민해보거나 다른 풀이 참고해보기

◾️ 음양 더하기

음양 더하기는 그냥 zip 메서드 이용하면 됨

◾️ 소수 만들기

조합에 대한 부분을 3중 for문으로 완전탐색해서 접근했는데 시간 초과가 떴다. (뭔가 당연하게 뜰 줄 알았는데 우선 그렇게 접근함)
그래서 뭔가 소수 판별 부분이 시간이 더 드는 건가하고 생각해서 에라토스테네스 체 방식으로 접근했는데 시간이 줄지가 않음
역시 조합이 문제구나라고 결론
조합에 대한 함수를 구현하는 방식에 대해 학습 - https://inuplace.tistory.com/1189 (인우형 블로그 참고)
재귀함수로 구현(안보고 구현할 수 있게 공부 -> 나중에 다시 구현해봐야 할 것 같다.)
이전에 코테 응시할 때 순열과 조합 이용해야 하는 경우를 종종 봤었는데 Python이 아니다보니 직접 구현해야 하는 경우가 생긴다. 잘 숙지해놓도록 하자.

Answer 2 · 2023-01-10T05:22:35.000Z

Day 2

◾️ 오픈채팅방(20m)

구현만 잘하면 되는 문제였음
uid 관리는 딕셔너리를 활용해야겠다는 생각이 들었음
문법적 디테일을 잘 숙지해야한다는 생각이 들었음

components(separatedBy: " ")
updateValue(_:forKey:)
replacingOccurrences(of:with:)

◾️ 멀쩡한 사각형(1h 30m ~)

개인적으로는 이런 문제 같은 경우는 사고력 자체를 길러야 하는 문제라서 오래 잡고 있는 것도 중요한 것 같다. (유형별 문제랑은 다르게)
오랜만에 문제 푼 것에 대해 희열이 느껴졌다.

처음 1시간 넘게 고민했을 때 아이디어 자체가 생각이 안나가지고 skip 하고 오픈채팅방부터 품
밥 먹고 다시 차분히 생각해보니까 아이디어가 떠올랐다.
대각선 자체가 선분이고, 기울기가 존재하니까 블록의 우측 꼭짓점이 기울기보다 위에 있으면 블록은 사용할 수 없는 상태가 된다. 그렇기에 그런 방식으로 멀쩡한 사각형을 파악하면 되는데 더 자세한 내용은 좌표를 하나씩 대입해서 생각해보면 된다.
역시 레벨 2 문제라 그런지 노트에 끄적거리면서 규칙이나 아이디어를 찾지 않으면 아직 풀기가 어렵다.
아이디어는 맞았으나, 한 번은 시간초과가 났는데 완전탐색으로 풀면 시간초과가 난다. 그러니까 불필요한 연산은 줄여주어야 한다는 이야기다.
pointY라는 변수를 두어가지고 계산할 필요가 없는 y좌표는 건너뛰도록 하면 문제를 해결할 수 있다.
그리고 대각선을 기준으로 멀쩡한 사각형이 대칭이기 때문에 x2를 해서 최종 값을 도출해낸다.

◾️ 짝지어 제거하기

Stack 자료형 만들어서 구현했을 때는 시간 초과나고 그냥 Array로 풀면 효율성 통과함(왜지..?)

Answer 3 · 2023-01-11T06:43:38.000Z

Day 3

◾️ 기능개발(약 55m)

비슷한 로직으로 접근하고 있었는데, 어디서 놓치는 부분이 있었는지 TC만 통과하고 실제 제출 했을 때 절반 넘게 틀리더라.
풀이가 좀 정리가 된 순간 결국 통과를 했는데, 음 이 문제도 아이디어를 잘 도출한 후 실제 풀이로 잘 옮기면 풀리는 문제였다. 구현에 가까운 문제였던 것 같다.
자료구조로는 Queue가 떠올랐는데 removeFirst()메서드를 사용해서 풀었다. 맨 앞 원소가 조건을 만족해서 out되지 않는다면 뒤의 원소는 나갈 수 없는 그런 구조였다. Queue의 특성을 완벽하게 지니고 있었다.
zip을 활용하기 적당한 문제였던 것 같다.
추가로 이런 문제가 while문 활용하기 좋은 문제인 것 같다.
주요 문법 zip, ceil, removeFirst, while, for-loop

레벨 3의 경우 아직 풀이를 시작하지는 않았지만 트리랑 그래프를 활용하는 문제가 많이 보였던 것 같다. 
(특히 그래프?) 풀이 전에 간단하게 자료 구조를 정리하고 넘어가는 것도 좋아보인다.

◾️ 문자열 압축

구현의 복잡도가 레벨 1 문제들보다는 올라간 느낌
문제를 분해해서 보는 것을 의식적으로 하다보니 풀리긴 했다. (2일차 때는 무작정 덤벼들었다가 컷 당함)
큼지막하게 나누면 문자열을 컷하는 기능, 중복된 문자열이 나왔을때는 개수를 더해서 반환하는 기능(ab, ab -> 2ab)을 구현하는 것이 관건이었다.
중간에 core dumped 에러가 나왔는데 그동안의 경험상 Index out of error가 주 원인인 듯 하다.
길이가 1일 때의 문자열의 경우 에러가 나는 문제였다. 그나마 빨리 보여서 금방 해결함 -> Bounds에 걸리는 TC를 신경쓰는 것도 중요해보인다.
확실히 코테 문제풀때는 네이밍이나 가독성 고려하는 것이 어렵긴하다. 최소한의 가독성을 높이는 방법은 메서드를 잘게 나누는 것이다. OOP 관점에서는 SRP에 해당할 것 같다.

Answer 4 · 2023-01-12T09:17:19.000Z

Day 4

◾️ 가장 먼 노드

이런 문제는 유형 문제에 가깝기 때문에, 이론이나 대표 예제를 먼저 풀고 접근하면 훨씬 편한 것 같다.
쌩으로 접근해서 맞추기가 어렵다고 생각한다.

노드(정점, 방문 ...) + 최단 경로(가장 멀리 떨어진) => BFS
한창 Python으로 BFS 문제 몰아 풀 때에는 문제 잘 풀렸는데 확실히 오래 공부를 안하다보니까 이론적인 내용도 다 잊게 된다. 근데 잠깐 다시 공부하니까 금방 복기 되는 것 보니까 뼈대 풀이만 확실히 이해하고 있으면 도움은 되는 것 같다.

Python과의 차이

효율성 때문에 python 풀이에서는 queue대신 deque을 거의 필수적으로 이용했었는데, swift에는 deque이 내장 자료구조로 구현되어 있지 않다보니 이것이 차이점인 것 같다. 우선은 일반 array(queue)로 생각을 하고 문제풀이를 좀 해보고 deque이 반드시 필요하다라고 판단이 되면 deque 자료구조를 통째로 외워서 사용해야겠다. (어차피 중요한 것은 첫번째 원소를 pop 하는 시간 복잡도가 O(N)인지 O(1)인지의 차이이기 때문)
Level, Step => 이렇게 최단 경로가 포함된 문제인 경우에는 몇 단계의 레벨로 BFS 탐색을 진행했는지가 정말 중요하다. 그렇기에 큐에 원소를 삽입하거나 삭제할 때 레벨에 대한 정보를 같이 포함시켜주어야 하는데 튜플 형태로 사용하는 것이 일반적인 형식인 것 같다. 나 같은 경우에도 그렇게 푸는 것이 편했음
이번에 공부하면서 새롭게 알게된 내용은 visited(방문여부)에 대한 데이터 저장을 Array가 아닌 Set을 이용하는 방법이었다. 어차피 특정 노드에 대한 방문 여부를 체크하는 것이기 때문에 중복 여부를 고려할 필요가 없고, 이후에 확인 시에 특정 노드가 Set에 포함되어 있는지만 확인하면 되는 것이었다.

분명 풀이를 맞게 접근했었는데 자꾸 틀리길래 확인했더니 문제를 꼼꼼히 읽지 않았다.

몇 단계 level, step으로 들어갔는지 파악하는 것이 아니라
가장 멀리 떨어진(최종 level 까지 떨어진) 노드가 '몇 개'인지를 구하는 것이었다.

인접리스트를 활용한 그래프 형태 표현

좀 더 깔끔하게 코드를 수정할 수는 있을 것 같다.

// 인접 리스트로 구현 + 무방향 그래프
func makeGraph(_ edge: [[Int]]) -> [Int: [Int]] {
    var graph: [Int: [Int]] = [:]
    for v in edge {
        if let e = graph[v[0]] {
            graph[v[0]] = e + [v[1]]
        } else {
            graph[v[0]] = [v[1]]
        }
        
        if let e = graph[v[1]] {
            graph[v[1]] = e + [v[0]]
        } else {
            graph[v[1]] = [v[0]]
        }
    }
    return graph
}

◼️ 입국 심사

순열 활용한 풀이 -> 시간 초과
딱 봐도 제한 조건에서의 입력 값이 너무 크다. (입국 심사대에 사람이 무슨 1억명이 들어와;;)

func permute(_ nums: [Int], _ targetNum: Int) -> [[Int]] {
  var result = [[Int]]()
  var visited = [Bool](repeating: false, count: nums.count)
  
  func permutation(_ nowPermute: [Int]) {
    if nowPermute.count == targetNum {
      result.append(nowPermute)
      return
    }
    for i in 0..<nums.count {
      visited[i] = true
      permutation(nowPermute + [nums[i]])
      visited[i] = false
    }
  }
  permutation([])
  
  return result
}

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    let array = Array<Int>(1...n)
    let arr = permute(array, times.count).filter { $0.reduce(0, +) == n }
    let timeArr = arr.map { [$0[0] * times[0], $0[1] * times[1]] }.map { max($0[0], $0[1]) }
    return Int64(timeArr.min()!)
}

import Foundation

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    var answer: Int64 = 0
    var indices: [Int] = Array(repeating: 0, count: times.count)
    var count = 0
    var index = 0
    var value = indices[0] + times[0]

    while count != n {
        count += 1
        
        index = 0
        value = indices[0] + times[0]
        
        // i => index, val => 7, 10 ...(times)
        for (i, val) in indices.enumerated() {
            if value > val + times[i] {
                index = i
                value = val + times[i]
            }
        }
        
        indices[index] = value
        // print(indices)
    }

    return Int64(indices.max()!)
}

풀이 더 간결해짐. TC 1-3까지만 맞고 나머지 시간 초과
while + for-loop 때문에 그런거 같은데 특히 for-loop? -> 1억번 연산해야하기때문에 이걸 줄여야 할 것 같음

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    
    var start = 1
    var end = times.max()! * n

    while start != end {
        let mid = (start + end) / 2
        let people = times.map { mid / $0 }.reduce(0, +)

        if people >= n {
            end = mid
        }
        
        else if people < n {
            start = mid + 1
        }
    }

    return Int64(start)
}

이분탐색 풀이
사실 카테고리가 상단에 나와있어서 이분탐색으로 풀 수 있겠다라고 생각은 했는데, 기준을 잡는 것이 많이 어려웠다. 처음에 최악의 시간까지는 잘 떠올렸는데 그 이후가 문제였다. 음.. 여기서 얻을 수 있는 것은 이분탐색 자체의 풀이일수도 있겠지만 풀이법 자체는 정형화되어있고 또 어렵지 않아서, 기준을 어떤 것으로 세울지를 다시 떠올려보는 것이 더 나을 것 같다.
결국 여기서 나오는 재료 자체가 (총 걸린 시간, 사람 수) 이기 때문에 이를 잘 조합해보면 실마리를 조금은 찾을 수 있지 않을까 싶다.
또, 이전에도 생각을 해본 내용이지만 입력값이 엄청 큰 경우에는 범위를 크게 좁혀나가야 하기 때문에 이분탐색으로 빠르게 접근하는 것이 더 효율적이라고 생각한다. 이분탐색의 경우에는 문제를 많이 풀어야겠다. start, end, mid, 조건을 잘 정하는 연습이 되어야 할 것 같다.

◼️ N으로 표현

아이디어 자체는 떠올렸는데 확신을 갖지 못한 문제
숫자를 만들어가는데 작은 수를 만드는 것부터 시도해보면 되겠다라는 생각을 했었음
예를 들면 12라고 하면, 1부터 만들어보는거지,, 1만들때 몇개 필요한지,,, 2만들때 몇개 필요한지

Answer 5 · 2023-01-13T06:01:51.000Z

Day 5

◼️ N으로 표현

결국 풀이를 봤다.
Swift 풀이로 검색해보면 DFS 풀이만 나오길래, 다른 언어에서 DP로 푼 아이디어를 봤음.
DP라고 해서 반드시 Array Table이 있어야 하는 것은 아님. 이전 값을 기억해서(또는 이용해서) 다음 값을 찾아내는 흐름이면 DP임. 점화식은 어쨌든 도출해내야 함.

DP 문제 중에서도 중 난이도에 속하지 않나 싶음.
일단 N, NN, NNN ... 이거 도출해내야 하고, 점화식으로 (S[j] · S[i-j-1]) 쌍을 찾아내야 하는 것도 쉽지 않음.
8 초과시 -1 반환해야 하는 부분.
Set을 이용하는 부분은 좋았던 것 같음. -> 재료를 얻은 느낌. => 자료구조의 적절한 활용
Set 원소 추가 : insert()메서드

◼️ 추석 트래픽

풀이 참고
시간을 parsing하는 부분에서 1차 고비, ms(Double형)로 모두 통일해서 생각하는 아이디어가 참 좋은 것 같다. 시간 다루는 문제가 종종 나오는데 잘 기억해두고 사용해야겠다.
Struct 형태로 하나의 타입을 만들어서 사용하는 것도 사실 잘 생각해서 쓰지는 않는데 생각의 폭이 넓어진 것 같다.
1초씩 옮기면서 모두 반복해도 시간 초과는 나지 않는 문제였으나 TC를 보면 시간이 많이 걸리는 부분도 있었다. (이게 슬라이딩 윈도우 기법인가, 1초씩 옮기는 과정 자체가)
아이디어를 생각해내는 것도 중요한 문제인 것 같다.
O(N^2) 연산

Ref.

Answer 6 · 2023-01-13T07:24:16.000Z

5일간 17문제를 풀었는데 진짜 생각보다 빡빡하다. 레벨 1 같은 경우는 수월하게 풀었고, 레벨 2는 이전보다는 아이디어를 생각해내고 구현하는 것이 어느정도 쉬워졌다. 레벨 3까지는 아직 조금 버거운 느낌이 든다. 알고리즘도 어느 정도 학습이 필요할 것 같고, 아이디어를 떠올리는 것이 조금 더 까다로운 느낌을 받았다.

Week1 problem list(17)

Day 1(8)

◾️ k번째 수

◾️ 키패드 누르기

◾️ 체육복

◾️ 인형뽑기

removeLast, dropLast

◾️ 모의고사

◾️ 로또의 최고순위와 최저순위

◾️ 음양 더하기

◾️ 소수 만들기

Day 2

◾️ 오픈채팅방(20m)

◾️ 멀쩡한 사각형(1h 30m ~)

◾️ 짝지어 제거하기

Day 3

◾️ 기능개발(약 55m)

◾️ 문자열 압축

Day 4

◾️ 가장 먼 노드

Python과의 차이

분명 풀이를 맞게 접근했었는데 자꾸 틀리길래 확인했더니 문제를 꼼꼼히 읽지 않았다.

인접리스트를 활용한 그래프 형태 표현

◼️ 입국 심사

◼️ N으로 표현

Day 5

◼️ N으로 표현

◼️ 추석 트래픽

Ref.