Jenikeju

문제 설명

내가 푼 풀이

처음에는 배열을 순회해서 빵(1) 을 만나면 빵부터 index+3 까지 빼서 햄버거가 완성되는지 확인을 했다.

햄버거가 만들어지면 카운트하고 배열에서 뺴고 인덱스를 다시 0부터 시작해서 순회했다.

이 방법으로 시도를 했지만 시간초과가 떴다

배열의 최대 크기가 1,000,000 이고, 햄버거가 만들어지려면 정해진 순서가 있다.

위의 방법은 대충 짐작하면 시간복잡도 O(N^2) 가 걸리고 이보다 더 빠른방법을 이용해야한다.

또한 빵이 아닌 재료들이 지나가도 재사용이 가능하다는 점을 이용해야 해서 스택(Stack)을 이용하려고 한다.

Swift 에서 스택을 구현하려면 직접 코딩을 해야하지만 스택의 FILO만 이용하기로 한다

1. 재료배열을 순회해서 스택에 넣는다.

2. 스택의 양이 4 이상이면, 스택의 마지막인덱스로부터 4 범위의 배열을 검사한다.

3. 검사한 배열이 [1,2,3,1] 인 햄버거 만드는조건을 충족하는경우, popLast() ( O(1) ) 를 이용해서 스택에 쌓인 재료를 빼낸다.

4. 만들어진 햄버거 수 출력한다.

Swift의 배열은 첫번째 원소를 뺄 땐 배열의 모든 원소를 순회해야하지만, 마지막 원소를 뺄땐 마지막 원소만 접근한다.

이는 배열의 특징인 연속적으로 원소가 존재하기 때문이다.

임의의 위치에 원소를 추가하는 경우, 삽입되는 위치 이후의 원소들을 한칸씩 뒤로 밀어내야 하고

임의의 위치에 원소를 삭제하는 경우, 삭제되는 위치 이후의 원소들을 한칸씩 앞당겨야 하기 때문이다.

최악의 경우 O(N) 만큼 걸린다.

또한 contains 역시 배열 원소 값 하나하나 체크해야하므로 최악의 경우 O(N) 만큼  걸린다.

import Foundation

func solution(_ ingredient:[Int]) -> Int {
    var stack = [Int]()
    var result = 0
    var check = [1,2,3,1]
    
    for i in 0..<ingredient.count {      // 재료 순회
        stack.append(ingredient[i])
        if stack.count >= 4 {            // 스택에 재료 4개가 쌓이면
            var arr = [Int]()
            for i in stack.endIndex-4..<stack.endIndex { // 스택에 맨위로부터 4개 추출
                arr.append(stack[i])
            }
            if arr == check {            // 추출한 재료가 햄버거만드는 조건을 충족하는 경우
                result += 1
                for i in 0..<4 {
                    stack.popLast()     //재료 빼기
                }
            }
        }
    }
    return result
}

문제 설명

내가 푼 풀이

준비 한 음식의 양이 2의 배수여야 사용이 가능하다는 점을 이용해서 주어진 음식 배열을 전부 2로 나눈 몫으로 바꾼다.

나눈 배열을 순회하면서 각 인덱스의 양만큼 문자열을 더해 출력하고, 0을 기준으로 반대로 출력한다

import Foundation

func solution(_ food:[Int]) -> String {
    var foods = food.map{$0 / 2}
    var str = ""
    for i in 1..<foods.count {
        for j in 0..<foods[i] {
            str = str + "\(i)"
        }
    }
    str = str + "\(0)" + str.map{String($0)}.reversed().joined(separator: "")

    return str
}

문제 설명

내가 푼 풀이

등급별 갯수를 저장할 수 있는 Dictionary에 저장한다 [Int: Int]

등급 내림차순으로 높은 등급부터 상자에 최대한 담아서 최대 이익을 계산한다.

이익 계산이 상자에 들어있는 가장 낮은 점수의 곱이라서 내림차순으로 높은 점수부터 넣어야 최대 이익이 나올꺼라 생각했다.

import Foundation

func solution(_ k:Int, _ m:Int, _ score:[Int]) -> Int {
    var result = 0
    var dict = [Int: Int]()
    var good = k
    var count = m
    
    for i in 1...k {
        dict[i] = score.filter{$0 == i}.count
    }
    
    while good > 0 {
        if count > 0 {
            if dict[good]! > 0 {
                var num = count
                if dict[good]! >= count {
                    dict[good]! -= count
                    count = 0
                } else {
                    count -= dict[good]!
                    dict[good]! = 0
                }
            } else {
                good -= 1
            }
        } else {
            result = result + good * m 
            count = m
        }

    }
    return result
}

문제 설명

내가 푼 풀이

약수의 갯수를 구해서 limit을 초과하면 기본공격력 power 만큼 더하고, 초과하지 않으면 약수의 갯수만큼 더해서 출력한다.

이 문제에서 주어지는 number는 100,000 까지 제공한다.

일반적인 약수의 갯수를 구하는방법은 

숫자 n 이 주어졌을때, 1부터 n까지 나누어 떨어지면 약수이고 그 갯수를 구하는것이 일반적인 방법이다

하지만 이 방법은 2중 반복문 안에서 갯수를 구하므로 ( O(n^2) ) 시간초과가 날 경우가 많다.

이 문제 역시 모든 숫자를 순회해서 약수를 구하는 방법을 이용하면 시간초과가 뜬다.

그래서 약수를 구하는 더 효율적인 방법을 이용해야한다.

여러가지가 있겠지만 그 중 하나는 범위를 좁히는것이다. 

숫자 n 이 주어졌을때, n의 제곱근까지 확인한다.

이전에 소수를 효율적으로 구하는 과정이랑 비슷한데,

10의 약수 2 는 2 x 5 = 10이지만 10의 약수 5 도 역시 5 x 2 = 10 이다.

갯수는 2개지만 표현식은 앞뒤만 다를뿐 결국 같다는것을 이용하는 것이다

그리고 제곱근이 정수로 딱 떨어지는 경우, ex) 100

1 x 100 = 100 

2 x 50 = 100

4 x 25 = 100

5 x 20 = 100

10 x 10 = 100

20 x 5 = 100

25 x 4 = 100

50 x 2 = 100

100 x 1 = 100 

10 x 10 을 기준으로 대칭을 이루고 있다.

정수 n의 제곱근이 정수로 떨어지는 경우 num * num == n 인경우 횟수 증가한다.

이 방법의 시간복잡도는 O(√N) 으로 이전에 쓰는 일반적인 방법보다 시간이 훨씬 단축된다.

import Foundation

func solution(_ number:Int, _ limit:Int, _ power:Int) -> Int {
    var result = 0
    
    for i in 1...number {
        var num = 1
        var count = 0
        
        while num * num <= i {
            if (num * num) == i {
                count += 1
            } else if i % num == 0 {
                count += 2
            }
            num += 1
        }
        if count > limit {
            result += power
        } else {
            result += count
        }
    }
    return result
}

약수의 개수 구하기 알고리즘 참고:

https://chwan.tistory.com/entry/Java-%EC%95%BD%EC%88%98%EC%9D%98-%EA%B0%9C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0

문제 설명

"명예의 전당"이라는 TV 프로그램에서는 매일 1명의 가수가 노래를 부르고, 시청자들의 문자 투표수로 가수에게 점수를 부여합니다. 매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올려 기념합니다. 즉 프로그램 시작 이후 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게 됩니다. k일 다음부터는 출연 가수의 점수가 기존의 명예의 전당 목록의 k번째 순위의 가수 점수보다 더 높으면, 출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됩니다.

이 프로그램에서는 매일 "명예의 전당"의 최하위 점수를 발표합니다. 예를 들어, k = 3이고, 7일 동안 진행된 가수의 점수가 [10, 100, 20, 150, 1, 100, 200]이라면, 명예의 전당에서 발표된 점수는 아래의 그림과 같이 [10, 10, 10, 20, 20, 100, 100]입니다.

명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때, 매일 발표된 명예의 전당의 최하위 점수를 return하는 solution 함수를 완성해주세요.

제한사항

• 3 ≤ k ≤ 100
• 7 ≤ score의 길이 ≤ 1,000
  • 0 ≤ score[i] ≤ 2,000

---

내가 푼 풀이

• 명예전당이 비어있으면 -> 추가
• 명예전당이 k보다 적게있으면 -> 점수크기 상관없이 추가 
• 명예전당이 꽉 차있으면 -> 주어진 점수보다 작은 값이 명예전당에 있다면 순회해서 찾아서 주어진 점수랑 바꾼다 
• 결과 배열은 명예전당 추가와 상관없이 순회할때 마다 명예전당의 최솟값을 추가

import Foundation

func solution(_ k:Int, _ score:[Int]) -> [Int] {
    var points = score
    var glory = [Int]()
    var result = [Int]()
    for i in 0..<points.count {
        if glory.isEmpty {
            glory.append(points[i])
            result.append(points[i])
            continue
        }
        if glory.count < k {
            glory.append(points[i])
            result.append(glory.min()!)
        } else if glory.count >= k {
            var point = points[i]
            if glory.filter{ $0 < point}.count > 0 {
                var min = glory.min()!
                for j in 0..<glory.count {
                    if glory[j] == min {
                        glory[j] = point
                        break
                    }
                }
                result.append(glory.min()!)
            } else {
                result.append(glory.min()!)
            }
        }
    }
    return result
}

문제 설명

내가 푼 풀이

문자열을 배열로만들어서 순회하면서 첫번째 문자의 수와 첫번째 문자가 아닌 수를 비교해서 결과 출력했다.

import Foundation

func solution(_ s:String) -> Int {
    var arr = s.map{String($0)}
    var keepArr = [String]()
    var firstStr = ""
    var result = 0

    for i in 0..<arr.count {
        if keepArr.isEmpty {
            firstStr = arr[i]
            keepArr.append(firstStr)
        } else {
            keepArr.append(arr[i])
            if keepArr.filter{$0 == firstStr}.count == keepArr.filter{$0 != firstStr}.count {
                keepArr.removeAll()
                result += 1
            }
        }
        if i == arr.count - 1 {
            if keepArr.count > 0 {
                result += 1
            }
        }
    }

    return result
}

문제 설명

내가 푼 풀이

1.  주어진 문자열 배열로 변환

2. 문자 배열 순회하면서 Dictionary에 문자와 문자의 인덱스 갱신하면서 result 배열에 추가 (문자 s)

2-1) dict[s] == nil 이면 append(-1) , dict[s] = 현재 인덱스

2-2) dict[s] != nil 이면 append( 현재 인덱스 - dict[s] ) , dict[s] = 현재 인덱스

3. result 배열 출력

import Foundation

func solution(_ s:String) -> [Int] {
    var dict = [String: Int]()
    var arr = s.map{String($0)}
    var result = [Int]()
    for i in 0..<arr.count {
        if dict[arr[i]] == nil {
            dict[arr[i]] = i
            result.append(-1)
            continue
        }
        var idx = dict[arr[i]]!
        result.append(i - idx)
        dict[arr[i]] = i
    }
    return result
}

문제 설명

내가 푼 풀이

1. 문자열 t의 배열을 순회해서 p의 길이만큼 부분 문자열을 뽑아서 배열에 저장한다.

2. 뽑은 배열을 순회하면서 p보다 작거나 같은 문자의 갯수 출력

import Foundation

func solution(_ t:String, _ p:String) -> Int {
    var strArr = t.map{String($0)}
    var count = p.count
    var num = Int(p)!
    var numArr = [Int]()
    
    for i in 0..<strArr.count-count + 1 {
        var arr = [String]()
        for j in i..<i+count {
            arr.append(strArr[j])
        }
        numArr.append(Int(arr.joined(separator: ""))!)
    }
    return numArr.filter{ $0 <= num }.count
}