Jenikeju

문제 설명

내가 푼 풀이

등급별 갯수를 저장할 수 있는 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
}

문제 설명

내가 푼 풀이

1. Dictionary에 [약관명: 유효기간] 을 저장한다.

2. 개인정보 배열을 순회해서 개인정보의 약관 유효기간을 계산해 현재 시간과 비교한다.

3. 유효기간이 현재시간보다 빠르다면( 현재시간보다 이전의 시간이라면), 배열의 인덱스 추출해서 출력한다.

문제를 어떻게 접근해야 할지는 금방 생각이 났는데, 날짜를 계산하는 과정에서 쉽게 빈틈이 생겼다.

month = month + 유효기간

만약 month > 12이 참이면  ->  year = year + month / 12 , month 는 13보다 작을때 까지 12를 계속 빼줬다.

이렇게 날짜를 계산했는데 테스트문제 14, 17 에서 자꾸 실패가 떴다.

생각하지 못한 곳에서 계산을 놓친것이 있다는건데 역시나 month + 유효기간이 만약 12로 나누어 떨어지는 경우를 생각하지 못했다.

month % 12 == 0 -> year = year + month / 12 - 1

month % 12 != 0 -> year = year + month / 12 

년도를 계산할땐 더 정확하고 세심하게 계산알고리즘을 짜야겠다..

import Foundation

func solution(_ today:String, _ terms:[String], _ privacies:[String]) -> [Int] {
    var todayTime = today.split(separator:".").map{Int($0)!}
    var termsArr = terms
    var priv = privacies
    var dict = [String: Int]()
    var result = [Int]()
    
    for i in 0..<terms.count {
        var arrs = terms[i].split(separator: " ").map{ String($0)}
        dict[arrs[0]] = Int(arrs[1])
    }
    
    for i in 0..<priv.count {
        var arr = priv[i].split(separator: " ").map{ String($0)}
        var date = arr[0].split(separator: ".").map{ Int($0)!}
        var term = dict[arr[1]]!
        
        date[1] += term
        if date[1] > 12 {
            if date[1] % 12 == 0 {
                date[0] = date[0] + date[1] / 12 - 1 
            } else {
                date[0] = date[0] + date[1] / 12
            }
            while date[1] > 12 {
                date[1] -= 12
            }            
        }
        if date[0] < todayTime[0] {
            result.append(i + 1)
            continue
        } else if date[0] == todayTime[0] {
            if date[1] < todayTime[1] {
                result.append(i + 1)
                continue
            } else if date[1] == todayTime[1] {
                if date[2] <= todayTime[2] {
                    result.append(i+1)
                    continue
                }
            }
        }
        

    }
    
    return result
}

문제 설명

풀이

1. 문자열 s를 배열로 만든다.

2. 각 문자의 아스키코드를 index만큼 증가시키면서 skipArr에 포함되면 더 건너뛰면서 증가한다.

3. 증가된 아스키코드의 문자를 출력

처음에는 index만큼 증가시킨 문자가 skip에 있는경우 건너뛰는줄 알았다.

문제를 잘 읽어보니 index만큼 증가시키되, 그 과정에서 skip에 있는 알파벳이면 index를 카운팅 하지 않고 건너뛴다는 점이다.

그래서 index를 불러서 계속 증가시키는 중에 skip에 포함되어있지 않으면 횟수를 올리고 그 횟수가 index가 되면 출력하는 방식으로

풀었다.

유니코드로 문자열 변환할땐 옵셔널로 반환된다

import Foundation

func solution(_ s:String, _ skip:String, _ index:Int) -> String {
    var strArr = s.map{String($0)}
    var skipArr = skip.map{String($0)}
    var result = [String]()
    
    for i in 0..<strArr.count {
        var str = strArr[i]
        var asciiNum = Int(UnicodeScalar(str)!.value)
        var checkNum = index
        var isDone = false
        while !isDone {
            asciiNum += 1
            if asciiNum > 122 {
                asciiNum -= 26
            }
            if !skipArr.contains(String(UnicodeScalar(asciiNum)!)) {
                checkNum -= 1
            }
            
            if checkNum == 0 {
                isDone = true
            }
        }
        result.append(String(UnicodeScalar(asciiNum)!))
    }

    return result.joined(separator: "")
}