Taehyeon-Kim/SwiftAlgorithm

2/13 ~ 2/19

Closed this issue · 4 comments

5주차까지 못푼거 모아 풀고 정리하기 + 자체 피드백 + 필요한 개념, 풀이, 코드 모으기

  • 삼각 달팽이
  • 경주로 건설
  • 후보키
  • 조이스틱
  • 큰 수 만들기
  • 모두 0으로 만들기

삼각 달팽이

2/13

import Foundation

func solution(_ n:Int) -> [Int] {
    var ret = Array(repeating: Array(repeating: 0, count: n), count: n)
    var (row, col, num, cnt) = (-1, 0, 1, 0)
    
    // 전체
    for i in stride(from: n, to: 0, by: -1) {
        
        // 한방향
        for j in 0..<i {
            switch cnt % 3 {
            case 0: // down
                row += 1
                ret[row][col] = num
                num += 1
                
            case 1: // right
                col += 1
                ret[row][col] = num
                num += 1
                
            case 2: // up
                row -= 1
                col -= 1
                ret[row][col] = num
                num += 1
            default: break
            }   
        }
        
        cnt += 1
    }
    
    return ret.flatMap { $0.filter { $0 != 0 } }
}
  • 구현 문제(얼마나 반복을 잘할 수 있는가)
  • 규칙성 발견하는 문제 -> 규칙을 발견한다는 것은 나열한다는 것, 나열한 항 사이의 관계를 파악하는 것, 수학의 수열이랑 비슷
  • 코딩 문제에서 규칙을 발견하기 위한 전제 조건을 만들기 위해서는 1차원 또는 2차원 배열을 만들어서 시각화를 해놓아야 한다. (나는 머릿속으로 계산을 할 수 없는 평범한 사람이기 때문)
  • 좌표를 자유자재로 다룰 수 있어야 하는 것 같다.
  • 등차수열의 관계도 자주 사용된다.

큰 수 만들기

import Foundation

func solution(_ number:String, _ k:Int) -> String {
    
    var stack = [Int]()
    var k = k
    var number = number.map { Int(String($0))! }
    
    for n in number {
        while !stack.isEmpty && stack.last! < n && k > 0 {
            _ = stack.popLast()
            k -= 1
        }
        stack.append(n)
    }

    if k > 0 {
        while k != 0 {
            _ = stack.popLast()
            k -= 1
        }   
    }
    
    return stack.map { String($0) }.joined()
}
  • 스택을 사용하는 문제(조합은 시간초과남)
  • 스택을 사용해서 첫번째 원소부터 순차적으로 하나씩만 탐색하면 O(N)의 시간복잡도로 문제를 해결할 수 있다.

0으로 만들기

  • 트리의 특성 파악하기
  • DFS에 대한 이해
  • 어렵다,, 이 문제는 다시 이해가 필요해보인다.
  • 개인적으로 dfs, 재귀에 좀 많이 약한 것 같다.
  • 조이스틱, 후보키는 다음으로 이관