Jenikeju

문제 설명

내가 푼 풀이

처음에는 그냥 2차원 배열을 구해서 1차원배열로 만들고 그에 해당하는 인덱스의 범위를 출력하려고 했는데

주어지는 n의 최대크기가 10^7 이라서, 2중 for문을 이용하면 무조건 시간초과가 뜨겠다 싶어서 해당하는 인덱스의 범위만 구하고

해당 배열이 만들어지는 규칙을 적용해서 정답을 출력하기로 했다.

이 문제에 적용한 배열이 만들어지는 규칙은 i행 1열부터 i열까지의 원소는 전부 i, i행 i+1열부터는 i+1, i+2 ... 이다.

ex) n = 3 일때 3x3 행렬 3행 1열 부터 3열까지는 전부 3이다.

ex) n = 5 일때 5x5 행렬 3행 1열 부터 3열까지는 전부 3이다. 3행 4열은 3+1 = 4, 3행 5열은 3+2 = 5 이다.

구하고자하는 범위 [left...right] 의 배열

전부 n으로 나눈 나머지 그 행의 순서가 나온다. 

전부 n으로 나눈 몫으로 바꾸면 그 행의 번호가 나온다. 

해당하는 위치의 순서가 행의 번호 보다 작거나 같으면 그 위치의 원소는 행의번호

해당하는 위치의 순서가 행의 번호 보다 크다면 그 위치의 원소는 행의번호 + (행의순서 - 행의번호 )

배열의 원소는 인덱스로 구성되어있으니 출력할때 +1을 해준다.

글로만 봐서는 헷갈리니까 예제문제로 예시를 들어본다.

ex) n = 3 , 3x3 행렬, left = 2, right = 5 

[[1,2,3],

 [2,2,3],

 [3,3,3]]

• 구하고자 하는 범위의 인덱스를 배열로 만든다. :  [2,3,4,5]
• 인덱스 배열을 3로 나눈 나머지 :  [2, 0, 1, 2] ( 행의 순서)
• 인덱스 배열을 2으로 나눈 몫 : [0, 1, 1, 1] (행의 번호)

인덱스배열 첫번째 2

행의 번호: 0 ,행의 순서: 2

행의 순서가 행의번호보다 크다. 결과는 행의번호 + 행의순서 - 행의번호 = 2 

위에 숫자는 전부 배열의 인덱스 이므로 +1 해서 출력한다 -> 3

인덱스배열 두번째 3

행의번호: 1, 행의순서: 0

행의번호가 더 크다. 결과는 행의번호

숫자는 배열의 인덱스이므로 +1을 해서 출력한다 -> 2

인덱스배열 세번째 4

행의번호: 1, 행의순서: 1

행의번호와 행의순서가 같다. 결과는 행의번호

숫자는 배열의 인덱스이므로 +1을 해서 출력한다 -> 2

인덱스배열 세번째 5

행의번호: 1, 행의순서: 2

행의순서가 행의번호 보다 크다. 결과는 행의번호 + 행의순서 - 행의번호 = 2

숫자는 배열의 인덱스이므로 +1을 해서 출력한다 -> 3

이런 규칙을 적용하여 풀었다.

import Foundation

func solution(_ n:Int, _ left:Int64, _ right:Int64) -> [Int] {
    var arr = Array(left...right)
    var rows: [Int64] = arr.map{ $0 % Int64(n)}
    var cols: [Int64] = arr.map{ $0 / Int64(n)}
    var result = [Int]()
    
    for i in 0..<rows.count {
        var num = cols[i] + 1
        if rows[i] <= cols[i] {
            result.append(Int(num))
        }  else {
            result.append(Int(num + (rows[i] - cols[i])))
        }
    }
    return result
}

문제 설명

내가 푼 풀이

주어진 문자열을 2차원 배열로 만들고, 배열의 크기순으로 정렬한 다음 중복되는 값들을 소거하고 출력한다.

replacingOccurrences

split

subtracting

import Foundation

func solution(_ s:String) -> [Int] {
    var arr = s.split(separator: "{").map{String($0)}
    var nums = [[Int]]()
    var result = [Int]()
    arr = arr.map{ $0.replacingOccurrences(of: "}", with: "")}.sorted{$0.count < $1.count}
    for i in 0..<arr.count {
        nums.append(arr[i].split(separator: ",").map{Int(String($0))! })
    }
    result.append(nums[0][0])
    for i in 1..<nums.count {
        var set1 = Set(nums[i])
        var set2 = Set(nums[i-1])
        result += Array(set1.subtracting(set2))
        
    }
    return result
}

내가 푼 풀이

LRU 알고리즘을 모르고 가장 최근에 사용된 캐시가 있다면 hit 없으면 miss 인 줄 알았다.

그래서 캐시의 크기만큼 배열을 만들어서 주어진 도시들을 순회하면서 밀어내기식으로 검사했는데 틀렸다

이 문제의 핵심은 LRU 알고리즘을 알고 있는지 이다.

LRU : Least Recently Used 로 가장 오랫동안 참조하지 않은 원소를 교체하는 방식이다.

여기서 문제풀이의 핵심은 검사배열에 없다면 추가해주고 있으면 순서를 앞으로 당겨줘야한다.

배열에 추가하기 쉽게 배열의 마지막인덱스가 가장 최근에 추가된 원소로 한다.

배열안에 존재할때

• array.contains(city)  = true  -> array.remove(at: city.index) , array.append(city)

배열안에 존재하지 않을때

• array.contains(city)  = false -> array.append(city)
• array.count > cache.count   -> array.removeFirst() , array.append(city)

func solution(_ cacheSize:Int, _ cities:[String]) -> Int {
    var cache = [String]()
    var result = 0
    
    
    for i in 0..<cities.count {
        var city = cities[i].uppercased()
        if !cache.contains(city) {
            result += 5
            cache.append(city)
            if cache.count > cacheSize {
                cache.removeFirst()
            }
        } else {
            for j in 0..<cache.count {
                if cache[j] == city {
                    cache.remove(at: j)
                    cache.append(city)
                    break
                }
            }
            result += 1
        }
    }
    return result
}

문제 설명

내가 푼 풀이

괄호의 규칙에 따르면

• 괄호가 열리자마자 바로 닫히면 올바른 문자열
• 괄호가 괄호안에 품어있다면 올바른 문자열
• 올바른 괄호 문자열이 연속된다면 합쳐도 올바른 문자열

올바른 문자열이 있다면 올바른 문자열이 존재할때 까지 계속 지워서 문자열의 길이가 0이면 올바른 문자열 이다.

이렇게 짠다면 위 세가지의 규칙에 맞기도하고, Swift로 문자열을 다루기엔 머리가 아팠다. 단순하게 생각했다.

하지만 조건이 떠오르지 않아서, 문자열을 순회하면서 스택에 넣어서 첫번째 규칙에 해당되면 바로 지우는 방식으로 풀었다.

이 문제와 같이 조건에 해당하면, 소거해나가는 형식은 앞으로 stack을 이용해야겠다.

더 단순하게 올바른 문자열이 존재하지 않을때까지 지우는 방법은

문자열s를  s.contains("()")  || s.contains("[]")  || s.contains("{}") 조건문에 통과하게 만들고

s.replacingOccurrences()로 세가지 괄호를 다 지우는 것이다

s 문자열이 남아있다면 올바르지 않은 문자열, 남아있지 않다면 올바른 문자열

import Foundation

func solution(_ s:String) -> Int {
    var result = 0
    var check = ["()", "[]", "{}"]
    var string = s
    for i in 0..<string.count {
        var stack = [String]()
        var arr = string.map{String($0)}
        for j in 0..<arr.count {
            stack.append(arr[j])
            if stack.count < 2 {
                continue
            }
            
            while stack.count > 1 {
                var str = "\(stack[stack.endIndex-2])" + "\(stack[stack.endIndex-1])"
                if check.contains(str) {
                    stack.popLast()
                    stack.popLast()
                } else {
                    break
                }
            }
            
        }
        if stack.count < 1 {
            result += 1
        }
        var first = string.removeFirst()
        string = "\(string)" + "\(first)"
        
    }
    return result
}

문제 설명

내가 푼 풀이

귤의 크기별 갯수를 구하고, 갯수가 많은 귤부터 포장에 들어간다.

귤 종류가 바뀌면 result += 1  , result 출력

import Foundation

func solution(_ k:Int, _ tangerine:[Int]) -> Int {
    var dict = [Int: Int]()
    var size = Set(tangerine).sorted{ $0 < $1 }
    var result = 0
    var num = k

    for i in tangerine {
        if dict[i] == nil {
            dict[i] = 1
        } else {
            dict[i]! += 1
        }
    }
    
    var sortedDict = dict.sorted{ $0.value > $1.value}
    for i in sortedDict {
        result += 1
        num -= i.value
        if num <= 0 {
            break
        }
    }
    return result
}

문제 설명

func solution(_ n:Int) -> Int {
    var num = n
    var arr = Array(repeating: 0, count: n + 1)
    if n == 1 {
        return 1
    }
    arr[0] = 1
    arr[1] = 2
    
    for i in 2..<num {
        arr[i] = (arr[i-1] + arr[i-2]) % 1234567
    }
    return arr[num - 1]
}

문제 설명

내가 푼 풀이

참가자 번호 A,B 

N의 지수를 구하고 지수만큼 반복한다.

지수만큼 반복할 때, N을 2로 나눠서 참가자 A,B가 어디 범위에 있는지 조사한다.

N을 2로 나눴을때 양쪽에 존재하는경우, 현재 지수번째 라운드에서 만나게 된다.'

N을 2로 나눴을때 두 참가자가 나눈 값보다 위에 있을때 참가자의 번호에서 나눈값을 빼서 범위 조사에 용이하게 한다.

ex) N = 8, A= 4, B= 7, n의 지수 count: 3

count = 3 일때)

• N / 2 = 4 , 4 를 기준으로 A는 4보다 같거나 작고, B는 4보다 크다.
• N/ 2 기준으로 양쪽에 참가자가 있으므로 count = 3 인 3번째 라운드에서 만난다.

ex) N = 8, A= 1, B= 2, n의 지수 count: 3

count = 3 일때)

• N / 2 = 4 , 4 를 기준으로 A와 B 둘다 4보다 작다.
• N / 2 = 4 를 기준으로 양쪽에 존재하지 않으므로 count - 1

count = 2 일때)

• N / 2 = 2 , 2 를 기준으로 A와 B 둘다 2보다 작거나 같다.
• N / 2 = 2 를 기준으로 양쪽에 존재하지 않으므로 count - 1

count = 1 일때)

• N / 2 = 1 , 1 를 기준으로 A = 1, B = 2 이므로 A는 1보다 작거나같고, B는 1보다 크다.
• N / 2 = 1 를 기준으로 양쪽에 존재하므로 count  = 1 인 1번째 라운드에서 만난다.

만약 A와 B 둘다 n/2 보다 큰경우, N/2 만큼 빼서 대진표의 왼쪽편으로 이동하게 한다.

결국 A와 B가 몇번째 라운드에서 만나는지가 중요하기 때문에, n/2 만큼 빼서 범위계산하기 더 편하게 한다.

import Foundation

func solution(_ n:Int, _ a:Int, _ b:Int) -> Int
{
    var num = n
    var numA = a
    var numB = b
    var count = 0
    var result = 0
    while num > 0 {
        num = num / 2
        count += 1
    }
    
    num = n
    
    while count > 0 {
        count -= 1
        var arr = [Int]()
        num = num / 2
        arr.append(numA)
        arr.append(numB)
        
        if arr.filter{ $0 <= num }.count == 1 {
            result = count
            break
        }else if arr.filter{ $0 > num}.count == 2 {
            numA = numA - num
            numB = numB - num
        }
        
    }

    return result
}

문제 설명

내가 푼 풀이

문자열을 순회하면서 stack 배열에 넣는다.

배열의 크기가 2 이상이면 순회할때마다 마지막 index의 값과 그 전의 값을 비교해서 같으면 제거

stack에 원소가 남아있으면 0, 없으면 1

import Foundation

func solution(_ s:String) -> Int{
    var stack = [String]()
    for i in s {
        var str = String(i)
        stack.append(str)
        if stack.count >= 2 {
            if stack[stack.endIndex - 1] == stack[stack.endIndex - 2] {
                stack.popLast()
                stack.popLast()
            }
        }
    }
    if stack.count == 0 {
        return 1
    } else {
        return 0
    }
}