[Swift|プログラマーLv.2]距離確認(2021ココア採用連絡型実習)

46835 ワード
コーディングテスト level2 けんさきょり swift プログラマ カカオ色 テキストリンク

質問する


問題の説明


開発者のJordyがKakaoに面接に来てほしいです.
コロナウイルス感染を予防するために、開発者の面接なので、受験者たちは距離を置いて待つべきだ.
以下のルールに従って、待合室で距離を置いて座るように案内します.
  • 待機室は5つあり、各待機室の大きさは5 x 5である.
  • 街を維持するために、受験者の間でマンハッタン街2以下に座らないでください.
  • 段の受験者の位置がパーティションによってブロックされている場合、許可される.
  • マンハッタン街:2つのテーブルT 1、T 2がそれぞれ行列(r 1、c 1)、(r 2、c 2)に位置する場合、T 1とT 2の間のマンハッタン街は|r 1-r 2|+|c 1-c 2|である.
    • たとえば、

    上の図に示すように、位置間にパーティションが存在する場合、マンハッタン距離は2つ以上の距離を維持する.

    上の図に示すように、パーティション間に座っていても距離は保たれます.

    上の図に示すように、位置間がマンハッタン通り2であり、表間が空であれば距離は保たれない.

    受験者が座る位置(P)を表す.

    空のテーブル(O)を表します.

    パーティション(X).
    5つのラウンジを見た後、ジョルディは各ラウンジの受験者たちが良好な距離を保っているかどうかを知りたい.パラメータ化されたのは,各ラウンジに2次元文字列配列位置があり,ここにいる受験者の情報とラウンジ構造が含まれていることである.各待機室が距離を保っている場合は1を完了し、1人で守らない場合は0を配列で返すソルバに入れてください.

    せいげんじょうけん

  • placesの行長(待機室数)=5
  • placesの各行はラウンジ構造を表しています.
  • 箇所の熱長(待機室縦長)=5
  • placesの要素は、P、O、およびXからなる文字列です.
  • places要素長(待機室横長)=5
  • Pは受験者が座る位置を示す.
  • Oは空のテーブルを表します.
  • Xはパーティションを表します.
    • 入力
  • で与えられた5つの待機室の大きさはいずれも5 x 5である.
  • 戻り値フォーマット
  • 次元の整数配列を返します.5つの要素が含まれています.
  • の位置にある5つの待合室の順に、距離を守っているかどうかを順番に並べます.
  • 各ラウンジは、すべての受験者が距離を保っていれば、1、一人も守っていなければ0が含まれています.

    • I/O例


    placesresult[["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]][1, 0, 1, 1, 1]

    I/O例説明


    I/O例#1
    最初の待機室
  • すべての受験者は距離を保っています.
    • 第2待機室
  • (0,0)位の受験者と(2,0)位の受験者は距離を保っていない.
  • (1,2)位の受験者と(0,3)位の受験者は距離を保っていない.
  • (4,3)位の受験者と(4,4)位の受験者は距離を保っていない.
    • 3つ目の待機室
  • すべての受験者は距離を保っています.
    • 4つ目の待機室
  • ラウンジは受験者がいないので街を守っています.
    • 5つ目の待機室
  • すべての受験者は距離を保っています.
    • 配列[1,0,1,1,1,1,1,1]を返します.2番目のラウンジ以外のすべてのラウンジから距離があるからです.

    時間制限ガイド

  • 精度テスト:10秒

    • に答える


    私の答え

    // TODO:
1. P, O, X의 위치 좌표를 담은 딕셔너리(location) 만들기
2. 대기실 별로 거리두기 지키는지 확인하기 - isKeepDistance
  2-1. 응시자(P) 없으면 거리두기 지킴
  2-2. 응시자(P) 있으면 P끼리 맨해튼 거리 구하기
3. 맨해튼 거리가 2 이하면 근처에 파티션 있는지 확인하기 - findPartion
  3-1. 두 좌표의 x가 같으면 y 사이에 파티션이 위치하는지
  3-2. 두 좌표의 y가 같으면 x 사이에 파티션이 위치하는지
  3-3. 두 좌표의 x, y가 모두 다르면 교차하여 확인
    import Foundation

func solution(_ places:[[String]]) -> [Int] {
    var location = [String: [(Int, Int)]]()
    var arr = [(Int, Int)]()
    var result = [Int]()
    
    places.map { place in
        place.indices.map { x in
            let line = place[x].map { String($0) }
            line.indices.map { y in
                // location 딕셔너리에 값 넣기
                // ex) ["P":[(0, 0)], "O":[(0, 1)], "X":[(0, 2)]]
                if location[line[y]] == nil {
                    location[line[y]] = [(x, y)]
                } else {
                    arr = location[line[y]]!
                    arr.append((x, y))
                    location.updateValue(arr, forKey: line[y])
                }
            } // 한 행(줄) 다 돌음
        } // 대기실 한 곳 다 돌음
        
        // 거리두기 확인해서 result 배열에 Int 값 넣기
        result.append(isKeepDistance(location))
        
        // arr, location 초기화
        arr = []
        location = [:]
        
    } // 모든 대기실 다 돌음
    
    return result
}

func isKeepDistance(_ location: [String: [(Int, Int)]]) -> Int {
    var isKeep = 1
    
    // 응시자 없으면 거리두기 지키고 있으므로 1 반환
    guard let p = location["P"] else { return isKeep }
    
    // 재귀로 P(응시자) 좌표 조합 생성
    func getCombination(_ arr: [(Int, Int)], _ r: Int, _ res: inout [[(Int, Int)]], _ now: [(Int, Int)] = [(Int, Int)]()) {
        let n = arr.count
        guard n > 0 else { return }
        
        if r == 0 {
            res.append(now)
        } else if n == r {
            res.append(now + arr)
        } else {
            getCombination(Array(arr[1...]), r - 1, &res, now + [arr.first!])
            getCombination(Array(arr[1...]), r, &res, now)
        }
    }
    var pCombi = [[(Int, Int)]]()   // P(응시자) 좌표 조합
    getCombination(p, 2, &pCombi)
    
    pCombi.forEach {
        // (r1, c1), (r2, c2) = |r1 - r2| + |c1 - c2|
        let distance = ($0[0].0 - $0[1].0).magnitude + ($0[0].1 - $0[1].1).magnitude    // 맨해튼 거리
        if distance < 3 {
            // 맨해튼 거리 2이하이면 findPartion 함수로 근처에 파티션있나 확인
            guard let x = location["X"] else { return isKeep = 0 }
            if !findPartion($0, x) {
                isKeep = 0
            }
        }
    }
    return isKeep
}

func findPartion(_ p: [(Int, Int)], _ x: [(Int, Int)]) -> Bool {
    if p[0].0 == p[1].0 {
        // x가 같은 경우 y 사이에 파티션 확인
        // ex) (2, 1), (2, 3)
        return !(x.filter { $0 == ((p[0].0, p[0].1 + 1)) }.isEmpty)
    } else if p[0].1 == p[1].1 {
        // y가 같은 경우 x 사이에 파티션 확인
        // ex) (1, 3), (3, 3)
        return !(x.filter { $0 == ((p[0].0 + 1, p[0].1)) }.isEmpty)
    } else {
        // xy 둘다 다르면(대각선에 위치한 경우) 교차하여 확인
        // ex) (0, 1), (1, 0)
        // 이때, 두 군데 모두 파티션이 있어야 함 (&&연산자 사용)
        return !(x.filter { $0 == ((p[1].0, p[0].1)) }.isEmpty) && !(x.filter { $0 == ((p[0].0, p[1].1)) }.isEmpty)
    }
}
    正確性試験正確性試験1〉合格(0.74 ms,16.6 MB)試験2〉合格(0.71 ms,16.7 MB)試験3〉合格(0.41 ms,16.6 MB)試験4〉合格(0.45 ms,16.5 MB)試験5〉合格(0.42 ms,16.7 MB)試験6〉合格(0.38 ms,16.6 MB)試験7〉合格(0.51 ms,16.5 MB)試験8〉合格(0.46 ms,16.5 MB)試験8〉合格(0.46 ms,16.5 MB)試験8〉試験10〉(0.55 ms,16.7 MB)試験11〉合格(0.46 ms,16.6 MB)試験12〉合格(0.54 ms,16.5 MB)試験13〉合格(0.42 ms,16.7 MB)試験14〉合格(0.35 ms,16.6 MB)試験15〉合格(0.39 ms,16.7 MB)試験17〉合格(0.55 ms,16.6 MB)試験18〉合格(0.60 ms,16.6 MB)試験19〉(0.51 ms,16.5 MB)試験20〉合格(0.71 ms,16.5 MB)試験21〉合格(0.82 ms,16.6 MB)試験22〉合格(0.41 ms,16.5 MB)試験23〉合格(0.27 ms,16.5 MB)試験24〉合格(2.96 ms,16.6 MB)試験25〉合格(0.23 ms,16.5 MB)試験27〉合格(0.40 ms,16.5 MB)試験28〉合格(0.41 ms,16.4 MB)試験(16.6 MB)試験30〉合格(0.32 ms,16.6 MB)

    他人の解答

    func isManhattanDistance(_ places:[[String]]) -> Bool {
    // (1, 0), (2, 0), (0, 1), (0, 2), (1, 1), (-1, 1)
    let dx = [ 1, 2, 0, 0, 1, -1]
    let dy = [0, 0, 1, 2, 1, 1]
    for x in places {
        print(x)
    }
    for row in 0..<5 {      // 행 5개
        for col in 0..<5 {  // 열 5개
            if places[row][col] == "P" {    // 응시자인 경우
                for i in 0..<6 {
                    let (nx, ny) = (row+dx[i], col+dy[i])
                    
                    // 맨해튼 거리가 2이하인 곳에 다른 응시자(P)가 있을 때
                    if (0..<5).contains(nx) && (0..<5).contains(ny) && places[nx][ny] == "P" {
                        
                        if row == nx {          // 같은 행에 다른 응시자가 있을 때
                            if ny - col == 0 {  // 바로 옆에 있을 때
                                return false
                            } else {            // 한 칸 떨어져 있을 때
                                if places[row][col+1] != "X" {
                                    return false
                                }
                            }
                            
                        } else if col == ny {   // 같은 열에 다른 응시자가 있을 때
                            if nx - row == 0 {  // 바로 옆에 있을 때
                                return false
                            } else {            // 한 칸 떨어져 있을 때
                                if places[row+1][col] != "X" {
                                    return false
                                }
                            }
                        } else {    // 대각선에 다른 응시자가 있을 때
                            if row > nx {
                                if places[row-1][col] != "X" || places[row][col+1] != "X"{
                                    return false
                                }
                            } else {
                                if places[row+1][col] != "X" || places[row][col+1] != "X"{
                                    return false
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return true
}

func solution(_ places:[[String]]) -> [Int] {
    
    // places를 [[[String]]] 형태로 만들기
    // ex) [[["P", "O", "O", "O", "P"], ["O", "X", "X", "O", "X"], ...]]
    let places = places.map {$0.map{$0.map{String($0)}}}
    var res:[Int] = []
    
    for place in places {
        // 대기실 별로 거리두기 확인하기
        res.append(isManhattanDistance(place) ? 1:0)
    }
    
    return res
}
    dxとdyは予め定められたx,y座標であり,下図のようにP(0,0)を基準にマンハッタン距離が2未満の場所に他の受験者(P)がいるか否かを決定する.
    // (1, 0), (2, 0), (0, 1), (0, 2), (1, 1), (-1, 1)
let dx = [ 1, 2, 0, 0, 1, -1]
let dy = [0, 0, 1, 2, 1, 1]

    正確性試験正確性試験1〉合格(0.22 ms,16.4 MB)試験2〉合格(0.33 ms,16.4 MB)試験3〉合格(0.21 ms,16.6 MB)試験4〉合格(0.19 ms,16.6 MB)試験5〉合格(0.19 ms,16.5 MB)試験6〉合格(0.20 ms,16.5 MB)試験7〉合格(0.22 ms,16.4 MB)試験8〉合格(0.21 ms,16.4 MB)試験(16.4 MB)試験10〉(0.21 ms,16.2 MB)試験11〉合格(0.34 ms,16.4 MB)試験12〉合格(0.34 ms,16.4 MB)試験13〉合格(0.37 ms,16.5 MB)試験14〉合格(0.21 ms,16.5 MB)試験15〉合格(0.19 ms,16.5 MB)試験16〉合格(0.21 ms,16.4 MB)試験17〉合格(0.21 ms,16.4 MB)試験18〉合格(0.21 ms,16.4 MB)試験19〉試験20〉(0.20 ms,16.7 MB)試験21〉合格(0.21 ms,16.6 MB)試験22〉合格(0.19 ms,16.3 MB)試験23〉合格(0.21 ms,16.4 MB)試験24〉合格(0.27 ms,16.4 MB)試験25〉合格(0.18 ms,16.6 MB)試験27〉合格(0.19 ms,16.6 MB)試験28〉合格(0.29 ms,16.7 MB)試験(0.36 MB)試験30〉合格(0.21 ms,16.4 MB)

    整理する


    ⏰
    目標解決時間:1時間
    実際の解法時間:3時間46分
    この問題は2021年にKakaoの夏の実習のために出された問題で、5つの問題のうち2番目の問題です.

    解説


    リファレンス
    付与する.×5サイズのスタンバイルームは以下のグラフで表示できます.
  • を頂点とします.
    • 各
  • には上下左右に隣接する幹線があります.
  • 段で、パーティションのあるセルから出たり、パーティションのあるセルに入ったりする幹線はありません.
    • これは、人がいる頂点から2を超えない距離に他の人がいる頂点があるかどうかを調べるためのグラフィックナビゲーションの問題と見なすことができる.
    したがって,有人頂点からの深さ優先ナビゲーション(DFS)や幅優先ナビゲーション(BFS)アルゴリズムを用いて解決できる.距離が2を超えないことを確認するだけです.
    また,距離2以内をチェックするだけで問題を解くことができるため,二重繰り返し文を用いて1つのセルを直接チェックすることも可能である.

    ポスト


    プログラマーの質問からDFSまでの内容が多いので、DFSとは何かと思いますが、これは私が情報処理技術を勉強したときに学んだ深さ優先探索です.
    解説に示すように,これは深さ優先探索または幅優先探索アルゴリズムを用いて解くことができる問題である.
    私は二重の複文で一つ一つ解答を確認して、確かに他の人の解答はもっと簡潔です.(タブレベルが深い)
    問題を解いたが、総試験時間(4時間)は1問だった.🥲 気を取り直そう…!🔥
    ソートアルゴリズム2:直接選択ソート
    チーム内で Unity C# のフォーマットを揃える