재미있는 재귀함수, 패스워드를 재귀함수로 만들어보자!

📝 KeyWord

⇢ 재귀 ⇢ 정렬 ⇢ 조합(순서가 정해져있기 때문에)

📌 문제풀이

⇢ 패스워드의 최소 조건인 길이를 만족시켜서 생성 ⇢ 패스워드가 모음 1개이상, 자음 2개이상을 포함하는지 확인 조건 ⇢ 알파벳순으로 패스워드를 어떻게 생성할 것인지?

#1

let input = readLine()!.split(separator: " ").map{Int($0)!}
let passwordArr = readLine()!
   .split(separator: " ")
   .map{String($0)}.sorted()
let l = input[0], c = input[1]

주어진 입력 형식에 맞게 데이터를 입력받는다. (단, 제시된 조건인 "알파벳 순서대로"에 맞게, 입력된 알파벳을 정렬한다.)

#2

extension String{
    var isCorrect: Bool{
        var num = 0
        let vowelArr = ["a" , "i", "e", "o", "u"]
        self.forEach { if vowelArr.contains(String($0)) { num += 1 } }
        if num >= 1 && self.count - num >= 2 { return true }
        else { return false}
    }
}

주어진 조건, 모음 1개 이상, 자음 2개 이상 포함하는지 확인 조건을 구현. (extension 활용을 위해, 위와 같이 구현해보았다.)

#3

func dfs(_ passwordArr:[String], _ passwordLength: Int) -> [String]{
    var answer: [String] = []
    func cycle(_ depth: Int, _ password: String, _ idx: Int){
        if depth == passwordLength && password.isCorrect {
            answer.append(password)
        } else{
            for i in idx..<passwordArr.count
            {
                cycle(depth + 1, password + passwordArr[i], i + 1)
            }
        }
    }
    cycle(0,"", 0)
    return answer
}

(1) 이제 단순히, dfs를 통해 주어진 알파벳 배열을 제시된 길이만큼 패스워드를 생성. (2) 생성된 패스워드가 구현조건을 만족한다면, answer 배열에 추가.

📝 전체코드

extension String{
    var isCorrect: Bool{
        var num = 0
        let vowelArr = ["a" , "i", "e", "o", "u"]
        self.forEach { if vowelArr.contains(String($0)) { num += 1 } }
        if num >= 1 && self.count - num >= 2 { return true }
        else { return false}
    }
}


func dfs(_ passwordArr:[String], _ passwordLength: Int) -> [String]{
    var answer: [String] = []
    func cycle(_ depth: Int, _ password: String, _ idx: Int){
        if depth == passwordLength && password.isCorrect {
            answer.append(password)
        } else{
            for i in idx..<passwordArr.count
            {
                cycle(depth + 1, password + passwordArr[i], i + 1)
            }
        }
    }
    cycle(0,"", 0)
    return answer
}


let input = readLine()!.split(separator: " ").map{Int($0)!}
let passwordArr = readLine()!
    .split(separator: " ")
    .map{String($0)}.sorted()
let l = input[0], c = input[1]

dfs(passwordArr, l).forEach { print($0)}

...

📝 KeyWord

⇢ DFS ⇢ 점화식 [ "Sn = Sn-1 + k" || "Sn = Sn-1 - k" ]

📌 문제풀이

⇢ 순서 변경없이, 해당 숫자들의 부호를 어떻게 변경할지 ⇢ target에 도달하기위해 모든 숫자가 사용되었는지 확인.

(1) 문제 조건 확인, "모든 숫자를 사용하여, 부호를 변경하며 target에 도달" (2) DFS를 통해, depth를 하나씩 증가하며, 배열의 개수와 같고 합이        target과 동일하다면 answer += 1

해당 문제를 풀면서 조건에 따라 "모든 숫자를 활용해야한다"는 사실을 알면서도 단순히, "target 과 sum이 동일하다면" 이라는 조건을 통해 DFS를 구현하다보니 계속 오답이 출력되었다..

📝 전체코드

import Foundation

func dfs(_ target: Int, _ numbers:[Int], _ depth: Int, _ sum: Int , _ answer: inout Int){
    if depth == numbers.count && target == sum { 
        answer += 1 
        return 
    } else if depth < numbers.count
    {
        dfs(target, numbers, depth + 1 , sum + numbers[depth], &answer)
        dfs(target, numbers, depth + 1 , sum - numbers[depth], &answer)
    }
}


func solution(_ numbers:[Int], _ target:Int) -> Int {

    var answer = 0
    dfs(target, numbers,0, 0, &answer)
    return answer
}

문제를 풀면서, 막힌 부분을 결국 해결하지 못해서, 답안을 참고하여 문제를 풀이하였다. sort()메소드를 단일 "$0 < $1" 과 같은 조건에 벗어나지 못했던 것 같다.

📝 KeyWord

⇢ sort{ } ⇢ String

처음에 단순하게 문자열로 sort를 진행하여, 앞 자리수가 큰 숫자로 정렬했음에도, **"자릿수가 다른 경우에 어떻게 정렬을 진행할지" 해결하지 못했다. **

📌 문제풀이

⇢ 0 이라는 숫자가 포함되어, 문자열로 변환시 "0000" 같은 문제가 발생. ⇢ "[3, 30, 34, 5, 9]" 인 경우, -> [ "3" 과 "30"] 자릿수가 다른 정렬 문제.

(1) String 타입으로 리턴할 정답 "answer" 선언 (2) 숫자 배열을 String으로 맵핑. (3) 💡 문자열을 정렬 -> { $0 + $1 > $1 + $0}

📝 전체코드

import Foundation


func solution(_ numbers:[Int]) -> String {

    var answer = ""
    var strNumbers = numbers.map{String($0)}
    strNumbers.sort{ ($0 + $1) > ($1 + $0) }
    if strNumbers.first! == "0" { answer = "0"}
    else{ strNumbers.forEach{answer += $0}   }

    return answer
}

💪 주차 요금 계산이 이렇게 어려웠나..?

📝 KeyWord

⇢ Dictionary ⇢ String

본 문제는 어려운 알고리즘이 요구되기 보다는, 정말 주어진 조건을 얼마나 잘 구현할 수 있는지 묻는 문제라고 생각한다.

📌 문제풀이

⇢ "IN, OUT" 자동차의 주차 상태를 어떻게 기록할 것인가? ⇢ 자동차의 주차시간을 어떻게 정수로 계산할 것인가? ⇢ "IN"상태에서 기록이 없는 자동차의 주차요금 계산은 어떻게 할 것인가?

우선 다음과 같이 접근해 볼 수 있다. (1) answer, 각각의 차량의 주차요금을 저장할 [Int] 배열 (2) inToOut, 최종 주차상태가 IN인 자동차의 시간 계산을 위한 변수 (3) carInfo, 자동차 번호를 키값으로, 주차 시간과 주차 상태를 기록하는 Dictionary

다음으로, 주어진 각각의 자동차 주차 정보를 토대로 필요한 값들을 추출한다. (1) time -> 주차시간을 계산 [시간 : 분] -> " 시간*60 + 분 " (2) carNumber -> 자동차 번호 (3) carState -> 현재 자동차의 주차 상태, "In Out" (4) carInfo에서 현재 자동차 번호를 대입하며, 주차시간 및 주차상태를 수정.

마지막으로, 차량 번호 순으로 정렬하여 각각의 차량의 주차요금을 계산한다 (1) Dictionary의 경우, sort()함수가 따로 없다는 점을 주의!!     (1-1) 구체적인 이유는 잘 모르겠으나, sorted()함수를 통해, 정렬

(2) 정렬된 차량 정보에서, 각각의 차량 별 주차 상태를 확인.     (2-1) "OUT"인 경우 그냥 계산.     (2-2) "IN"인 경우, inToOut을 통해 시간 계산.

(3) 주차 시간을 토대로, 주차 요금을 계산하여 answer 배열에 저장

📝 전체코드

import Foundation

func solution(_ fees:[Int], _ records:[String]) -> [Int] {

    var answer: [Int] = []
    var inToOut = 23*60 + 59
    var carInfo: [String:(time: Int, state: String)] = [:]

    records.forEach{
        let recordArr = $0.components(separatedBy: " ")
        var time = { () -> Int in 
            var timeInfo = recordArr[0].components(separatedBy: ":")
            var hour = Int(timeInfo[0])!
            var min = Int(timeInfo[1])!
            return hour * 60 + min
        }()
        var carNumber = recordArr[1]
        var carState = recordArr[2]
        if carInfo[carNumber] == nil{ carInfo[carNumber] = (time: time, state: carState) } 
        else{ carInfo[carNumber]! = (time: time - carInfo[carNumber]!.time , state: carState) }
    }

    var sortedCarInfo = carInfo.sorted{ $0.key < $1.key }

    sortedCarInfo.forEach{
        var car = $0
        if car.value.state == "IN"{ car.value.time = inToOut -  car.value.time}
        var parkingTime: Float = Float(car.value.time) - Float(fees[0])
        if parkingTime <= 0 { answer.append(fees[1]) }
        else{ 
           var moneyPerT:Int  = Int(ceil(parkingTime/Float(fees[2])))
            answer.append(fees[1] + moneyPerT * fees[3])
        }
    }


    return answer
}

💪 작심삼일도 삼일에 한번씩하면 꾸준히..!

📝 KeyWord

⇢ BFS / DFS : [너비 우선 탐색, 깊이 우선탐색] ⇢ String

DFS와 BFS중, 어떤 방식으로 풀어도 해결할 수 있지만, DFS 재귀함수 구현을 Swift로 한번 시도해보고자 DFS, 재귀함수 방식으로 풀이하였다!

📌 문제풀이

⇢ 해당 단어가 다른 단어로 변환될 수 있는지 확인하는 방법은? ⇢ DFS를 통해, 목표 단어까지 최소 횟수를 얻는 방법은?

먼저 단어 변환을 위해서, 해당 단어가 다음 단어로 변환이 가능한지 확인해야한다. (1) Comp1, Comp2와 같이 두 단어를 String으로 전달 받는다. (2) String을 Char단위로 비교하기위해, "map"을 활용한다 (3) map을 통해, 두 단어의 요소를 배열로 만든 후, 요소별 비교를 진행. (4) 서로 다른 요소의 개수가 1개라면 변환 가능한 단어

그 다음으로, DFS를 통해 시작 단어에서 부터 목표 단어까지 완전탐색을 진행한다. (1) DFS (시작단어, 목표 단어, 단어 목록        -> cycle을 통해 DFS 진행 (2) 목표 단어로 변환됬을 경우, answer에 최소값인 경우 기록. (3) 모든 탐색을 종료한 후에, answer 리턴.

(1) 시작 조건문, 변환 하고자 하는 목표 단어가 words 목록에 있는지 확인     (1-1) 있다면, DFS를 통해 탐색하며, 최소 횟수 기록     (1-2) 없다면, 0을 리턴

📝 전체코드

import Foundation

func isConvert(_ to: String, _ from: String) -> Bool {
    var isToConvertFrom: Int = 0
    let comp1 = to.map{ $0 }
    let comp2 = from.map{ $0 }
    for i in 0..<comp1.count{
        if comp1[i] != comp2[i] { isToConvertFrom += 1 }
    }
    return isToConvertFrom == 1
}

func DFS(_ begin: String, _ target: String, _ words: [String]) -> Int{

    var answer:Int = Int.max
    var visit:[Bool] = Array(repeating: false, count: words.count)
    func cycle(_ word:String , _ depth: Int){
        if word == target{
            answer = answer > depth ? depth : answer
            return

        }
        for i in 0..<words.count{
            if !visit[i] && isConvert(word, words[i])
            {
                visit[i] = true
                cycle(words[i], depth + 1)
                visit[i] = false
            }
        }
    }
    cycle(begin, 0)
    return answer

}

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {

    var answer = 0
    if words.contains(target) { answer = DFS(begin, target, words) }
    return answer
}

오늘도 챌린지 성공..! 주말이라 벌써 위기가 찾아왔다...

📝 KeyWord

⇢ BFS : [너비 우선 탐색] ⇢ Graph ⇢ 인접리스트

인접행렬과 인접리스트의 시간복잡도를 체감할 수 있는 문제였다. Edge를 행렬로 표현할 경우, N개의 노드의 연결 상태를 표현하기위해 "NxN" 배열의 완전탐색이 요구된다. 따라서, Dictionary를 활용한 인접리스트를 구현하여 문제를 해결하였다.

📌 문제풀이

⇢ node와 edge의 개수가 큰 범위일 때, 어떻게 해결할 것인가? ⇢ 인접리스트를 어떻게 구현할 것인가?

(1) swift의 인접리스트를, graph : [ 노드 : [연결노드]] 형식으로 구현하였다. (2) 양방향 그래프이므로, "to"와 "from"으로 구분하여 양쪽 노드의 연결관계를 추가. 해당 과정을 통해, 그래프의 인접리스트를 생성하였다. 이제 시작노드부터 인접리스트를 탐색하면서 가장 먼 노드의 개수가 몇 개인지 체크하면 해결할 수 있다.

위의 코드는 인접리스트를 탐색하는 BFS 함수 부분이다. (1) 조건에 따라, 시작노드(startNode)와 초기 거리를 설정한다. (2) 가장 먼 거리를 측정하기 위한, "maxDis"와 "maxCnt"를 설정한다. (3) BFS 탐색을 위한 Queue([노드: 시작노드로 부터의 거리])를 설정한다. (4) 현재 노드로 부터 연결된 노드 거리를 저장하면서, 거리 비교를 통해 노드 개수를 저장. (5) 가장 먼 노드 개수를 반환한다.

📝 전체코드

import Foundation

func BFS(_ graph: [Int:[Int]], _ nodeCnt: Int) -> Int
{
    var startNode = 0 
    var visitCheck: [Bool] = Array(repeating: false, count: nodeCnt)
    var queue: [(node: Int, dis: Int)] = []
    var maxDis = 0
    var maxCnt = 0

    visitCheck[startNode] = true
    queue.append((node: startNode, dis: 0))

    while !queue.isEmpty{
        let temp = queue.removeFirst()
        let startNode = temp.node
        let dis = temp.dis

        if graph[temp.node] == nil { continue }
        for nextNode in graph[temp.node]!{
            if !visitCheck[nextNode]{
                visitCheck[nextNode] = true
                var nextDis = dis + 1
                queue.append((node: nextNode, dis: nextDis))
                if maxDis < nextDis{
                    maxDis = nextDis
                    maxCnt = 1
                } else if maxDis == nextDis{
                    maxCnt += 1
                }
            }
        }
    }
    return maxCnt     
}



func solution(_ n:Int, _ edge:[[Int]]) -> Int {

    var graph: [Int: [Int]] = [:]

    for nodeToNode in edge{
        var to = nodeToNode[0] - 1
        var from = nodeToNode[1] - 1

        if graph[to] == nil{ graph[to] = [from]}
        else{ graph[to]!.append(from)}

        if graph[from] == nil{ graph[from] = [to] }
        else{ graph[from]!.append(to) }

    }


    return BFS(graph, n)
}

💪 오늘도 하루 최소 한 문제 해결!!

📝 KeyWord

⇢ BFS / DFS : [너비 우선 탐색, 깊이 우선탐색] ⇢ Graph

생각보다 간단하게 풀렸다. 동일한 Lv3 문제 중에서 아마 가장 쉬운 난이도로 볼 수 있다. BFS / DFS 라는 개념을 알고 있다면, 쉽게 해결할 수 있다!

📌 문제풀이

⇢ 제시된 Graph의 연결상태를 통해, 어떻게 네트워크를 연결할 것 인가? ⇢ 각각의 노드를 중복해서 방문하지 않도록 어떻게 처리할 것 인가?

먼저, BFS(너비우선탐색)으로 문제를 해결하기 위해 다음과 같은 변수 선언이 필요하다. *(1) 각각의 노드를 방문할 경우, "Visit" 방문 처리를 진행한다 (2) 한 노드에서 탐색이 완료될 때마다, network의 개수를 저장한다. * 최종적으로, 0부터 N-1번까지의 모든 노드를 BFS로 탐색하면서 탐색을 실행 할 때마, 서로 연결되지 않은 네트워크로 간주하여 개수를 1씩 늘려간다.

위의 코드는 단순히, BFS를 구현한 코드이다. C/C++에 익숙한 탓에, 주로 전역변수보다는 포인터를 활용한 매개변수를 사용하였는데, swift로 전환하면서 inout을 많이 활용하게 되는 것 같다..

📝 전체코드

import Foundation

func BFS(_ startNode: Int,_ computers:[[Int]],_ visit: inout [Bool]){

    var Queue: [Int] = []
    Queue.append(startNode)
    visit[startNode] = true
    while !Queue.isEmpty{
        let Node = Queue.removeFirst()
        for  nextNode in 0..<computers.count{
            if computers[Node][nextNode] == 1 && !visit[nextNode] {
                Queue.append(nextNode)
                visit[nextNode] = true
            }
        }
    }
}

func solution(_ n:Int, _ computers:[[Int]]) -> Int {

    var visit:[Bool] = Array(repeating: false, count: computers.count)
    var networkCnt = 0
    for node in 0..<computers.count
    {
        if visit[node] == false
        {
            BFS(node, computers, &visit)
            networkCnt += 1
        }
    }
    return networkCnt
}

알고리즘 챌린지! 꾸준히 한 문제라도 매일 풀어보자!

✏️KeyWord

(1) 문자열 (2) Dictionary (3) tuple

📌 문제풀이

💡 User Id와 User name, 그리고 해당 User의 State 매칭이 핵심!

User이름은 중복되지만, UserId는 중복되지 않는 조건이 있다. 해당 조건에 주목하여, "[User id : User name]"을 매칭한다! 그 다음으로, 해당 유저의 상태 메시지를 위해, 순서대로 "[유저의 상태, 유저아이디]"로 매칭한다 최종적으로, "[유저의 상태, 유저 아이디]" -> "[유저 아이디 : 유저 이름]" 즉, 유저 아이디를 연결고리로 매칭할 수 있다.

위 과정을 통해, stateArr -> [유저 상태, 유저 아이디] userIdToName -> [유저 아이디, 유저 이름] 방식으로 매칭을 진행한다.

최종적으로, stateArr에 저장된 [유저 상태, 유저아이디]를 순서대로 불러오면서, 유저 상태와 현재 유저 이름을 불러와 answer[] 배열에 저장한다.