20230401 TIL

오늘은 날씨가 너무 좋아서

산책을 잔뜩 했습니다. 꽃구경도 하고 ~..

그래도 늦게 나마 부랴부랴 스터디 카페 왔어요.

 

1. 프로그래머스 - 땅따먹기 

프로그래머스

- DP 문제였습니다. DP는 역시 점화식 찾는게 꽤나 시간이 걸리네요..

- 처음에는 DFS나 BFS로 풀어보려고 했는데 행의 최대 수가 10만이라, 무조건 시간초과..ㅎ

- 사고력(?)을 더 길러야하는데 단기간에 되는게 아니라 쉽지않네요 ㅠㅠㅠ뿌엥

func solution(_ land:[[Int]]) -> Int{
    
    // dp
    
    var dp = land
    
    for i in 1..<land.count {
        for j in 0..<4 {
            for k in 0..<4 {
                if j == k { continue } // 같은 열은 건너뛰기
                
                // 5에 다가 2, 3, 5 더한 것 중 가장 큰 값을 갱신하게 됨.
                dp[i][j] = max(dp[i][j], dp[i-1][k] + land[i][j])
                
            }
        }
    }
    
    return dp.last!.max()!
}

다른풀이에서 아래 풀이도 발견했는데요 !

딱 봤을때 DP 반복문이 이해 안된다면 이 코드로 하나씩 이해해볼 수 있을 것 같아요

다음 행의 0번째 열에는 이전 행의 1번째 , 2번째, 3번째 열의 값들 중에

가장 큰 값을 더해주면서 최댓값을 구해주는 방식입니다 ! 

( 0번째 열은 어차피 같은 열이라 제외됨. )

func solution(_ land:[[Int]]) -> Int{
    var answer = 0
    var land = land
    for i in 0..<(land.count-1) {
        land[i+1][0] += max(land[i][1], land[i][2], land[i][3])
        land[i+1][1] += max(land[i][0], land[i][2], land[i][3])
        land[i+1][2] += max(land[i][0], land[i][1], land[i][3])
        land[i+1][3] += max(land[i][0], land[i][1], land[i][2])
    }
 
    guard let last = land.last else { return 0 }
    return max(last[0],last[1], last[2], last[3])
}

 

2. 프로그래머스 - 오픈채팅방

프로그래머스

- 기존 풀이

func 풀었는데시간초과나는오픈채팅방(_ record:[String]) -> [String] {

    var NicknameDic: [String: String] = [:]
    var chatState: [(id: String, nickname: String, state: String)] = []

    for i in record {
        let input = i.split(separator: " ").map { String($0) }
        let (state, id) = (input[0], input[1])

        switch state {
            case "Enter":
                let nickname = input[2]

                if NicknameDic[id] != nil {
                    // 기존에 닉네임이 있는데, 이름 바꾸고 들어옴 바꿔준다.
                    NicknameDic[id] = nickname
                    chatState.indices.filter { chatState[$0].id == id }.forEach { chatState[$0].nickname = nickname }
                } else {
                    // 없으면 추가해준다.
                    NicknameDic[id] = nickname
                }
                chatState.append((id: id, nickname: nickname, state: "들어왔습니다"))
            case "Leave":
                let leaveName = NicknameDic[id]!
                chatState.append((id: id, nickname: leaveName, state: "나갔습니다"))
            case "Change":
                let changeName = input[2]
                NicknameDic[id]! = changeName
                chatState.indices.filter { chatState[$0].id == id }.forEach { chatState[$0].nickname = changeName }

            default:
                break
        }
    }

    var result: [String] = []

    for i in chatState {
        result.append("\(i.nickname)님이 \(i.state).")
    }

    return result
}

- 처음에는 채팅방 상태를 배열로 만들고 닉네임이 바뀔 때마다 배열에서 indices 메서드를 호출해서 id랑 일치하는 인덱스를 찾고,

이후에 각각의 인덱스에 대해 배열 요소를 업데이트 해줬는데요.

- 이렇게 하게 되니까 최대 O(n^2)의 시간복잡도를 가지게 되어 4개정도의 테케에서 시간초과가 나더라구요.

- 그래서 어떻게 개선을 해볼까 고민하다가, 딕셔너리를 쓰려고 했는데 그러면 채팅방 들어온 순서도 꼬이게 되고.. 활용하는게 복잡해질 것 같아서 배열을 이용하면서 최대한 배열을 덜 변경하는 식으로 개선을 해야겠다고 생각했습니다.

- 곰곰히 생각해보니, 가장 마지막에 바뀐 닉네임만 알면되니까 닉네임이 바뀔 때마다 굳이 업데이트를 해주지 않아도 되더라구요

- 닉네임 딕셔너리에만 계속해서 업데이트해주고, 채팅방 상태에 대한 업데이트는 id로 구분해줬습니다. id 1번이 들어왔습니다, 2번이 들어왔습니다, 1번이 나갔습니다.. 이런식으로 ..!

- 그리고 맨 마지막에 id랑 닉네임을 매칭해서 result에 저장했습니다 !

 

func 오픈채팅방코드개선(_ record:[String]) -> [String] {

    var NicknameDic: [String: String] = [:]
    var chatState: [(id: String, state: String)] = []

    for i in record {
        let input = i.split(separator: " ").map { String($0) }
        let (state, id) = (input[0], input[1])

        switch state {
            case "Enter":
                let nickname = input[2]

                if NicknameDic[id] != nil {
                    // 기존에 닉네임이 있는데, 이름 바꾸고 들어옴 바꿔준다.
                    NicknameDic[id] = nickname
                } else {
                    // 없으면 추가해준다.
                    NicknameDic[id] = nickname
                }
                chatState.append((id: id, state: "들어왔습니다"))
            case "Leave":
                let leaveName = NicknameDic[id]!
                chatState.append((id: id, state: "나갔습니다"))
            case "Change":
                let changeName = input[2]
                NicknameDic[id]! = changeName
            default:
                break
        }
    }

    var result: [String] = []

    for i in chatState.indices {
        let id = chatState[i].id

        result.append("\(NicknameDic[id]!)님이 \(chatState[i].state).")
    }

    return result
}

 

다른 사람들 풀이를 보니 더 간결하고 좋은 코드들이 많더라구요. 그 중에서 하나를 살펴봤습니다.

 

func solution(_ record:[String]) -> [String] {
    let actions = ["Enter":"님이 들어왔습니다.", "Leave":"님이 나갔습니다."]
    var a = [String:String]()

    record.forEach {
    let separated = $0.components(separatedBy: " ")
    if separated.count > 2 {
        a[separated[1]] = separated[2]
        }
    }

    return record.filter { !$0.contains("Change") }.map { (value:String) -> String in
        let separated = value.components(separatedBy: " ")
        let newString = a[separated[1]]! + actions[separated[0]]!
        return newString
    }
}

다른 사람 코드를 보니까 제 코드에서 개선해야할 점이 많네요..

처음에 Enter Leave Change를 나눠서 생각하다보니까 switch 문을 그대로 가져간 채로 코드를 수정했는데,

더 간결하게 짤 수 있네욥.

 

가장 큰 건, 어차피 닉네임은 가장 마지막으로 변경된 닉네임만 필요하니까

switch 문으로 나눌 필요 없이 그냥 계속해서 update를 해주면됩니다.

 

그리고 필터를 활용해서 다른 result 배열을 만들 필요없이 순서대로 return 해주는데요.

change가 포함되지 않은 기록들만 필터링해서 그 값을 출력형식에 맞게 바꿔줍니다.

 

이렇게 보니까 되게 간단한 문제같네요.

난 똥그멍그청그이...............................

 

 

오늘의 TIL.

안녕. . . . . . .