[Algorithm🧬] けんさきょり

質問する / 答えを出す。py
私の答え
最初は最近正規料理が大好きだったので、正規料理を使ってみました.
PPPOPのパターンが出てこないのは知っていますが、
たいかくせんアレイ
PO
XP
OP
PX
XP
PO
PX
OP
PO
OP
つかむ...5*5は2*2に並んで16個に分けてそこで確認…?
時間の複雑さが高すぎてスキップ...
第二に、Pを基準として、人を中心として、距離が2の部分である.

面倒くさい!
最後にプログラマーの質問に入り、アイデアのヒントを得ました.

Pを基準として、上下左右の格の中にPが1つあると距離保持に失敗します.

Oを基準として上下左右の格に2つ以上のPがあると距離を保つことができない.

これを考える人は本当に天才のようだ.しかし,そのような考えがなくてもBFSを利用することは容易であるようであるが,BFSの学習は行われていない.今週は公式最大化の謎を解き、資料構造の再学習を急ぐようになった.
要するに、対応するアイデアに基づいて、以下のコードを書きました!
existNearPersonsはbreakで重ねたいが出られない変数です.
今日の調査の部分はlist(str)です.list("abcde")->['a', 'b', 'c', 'd', 'e']が美しいにチェンジ!!!Pythonは最高です

import re

def solution(places):
    answer = []
    
    place_arr = []
    
    for place in places:
        # 1. 전체 배열에 P가 없는 경우는 거리두기를 지키고 있는 것
        if len(re.findall("P", ''.join(place))) == 0:
            answer.append(1)
            continue
            
        # 가생이는 따지기 귀찮으니까 X 로 채워주는 과정
        place_arr = [['X'] * (len(place) + 2)] 
        for row in place:
            place_arr.append(['X'] + list(row) + ['X'])
        place_arr.append(['X'] * (len(place) + 2))
        
            
        # 3. 세로와 대각선을 거르기 위한 나머지 경우에 대한 검사
        existNearPersons = False    
        for i in range(1, len(place) + 1):
            for j in range(1, len(place[0]) + 1):
                count = 0
                if place_arr[i][j] == "P" or place_arr[i][j] == "O":
                    if place_arr[i-1][j] == "P":
                        count += 1
                    if place_arr[i+1][j] == "P":
                        count += 1
                    if place_arr[i][j-1] == "P":
                        count += 1
                    if place_arr[i][j+1] == "P":
                        count += 1
                
                if place_arr[i][j] == "P" and count >= 1:
                    existNearPersons = True
                    break
                
                if place_arr[i][j] == "O" and count >= 2:
                    existNearPersons = True
                    break
                    
            if existNearPersons:
                answer.append(0)
                break
        else: ## if not existNearPersons: 와 같음
            answer.append(1)
                
    
    return answer

質問する
開発者のJordyがKakaoに面接に来てほしいです.
コロナウイルス感染を予防するために、開発者の面接なので、受験者たちは距離を置いて待つべきだ.
以下のルールに従って、待合室で距離を置いて座るように案内します.
待機室は5つあり、各待機室の大きさは5 x 5である.
距離を保つために、受験者の間でマンハッタン通り1街2以下に座らないでください.
ただし、パーティションが受験者の位置間の距離をブロックしている場合は、このオプションを使用できます.
たとえば、

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

placesの行長(待機室数)=5
-placesの各行は1つの待機室構造を表す.

箇所の熱長(待機室縦長)=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
最初の待機室
No. 0 1 2 3 4
0 P O O O P
1 O X X O X
2 O P X P X
3 O O X O X
4 P O X X P
すべての受験者は距離を保っている.
第2待機室
No. 0 1 2 3 4
0 P O O P X
1 O X P X P
2 P X X X O
3 O X X X O
4 O O O P P
(0,0)位の受験者と(2,0)位の受験者は距離を保たない.
(1,2)位の受験者と(0,3)位の受験者は距離を保たない.
(4,3)座席の受験者と(4,4)座席の受験者は距離を保っていない.
3つ目の待機室
No. 0 1 2 3 4
0 P X O P X
1 O X O X P
2 O X P O X
3 O X X O P
4 P X P O X
すべての受験者は距離を保っている.
4つ目の待機室
No. 0 1 2 3 4
0 O O O X X
1 X O O O X
2 O O O X X
3 O X O O X
4 O O O O O
待合室には受験者がいないので、2つの通りを守っています.
5つ目の待機室
No. 0 1 2 3 4
0 P X P X P
1 X P X P X
2 P X P X P
3 X P X P X
4 P X P X P
すべての受験者は距離を保っている.
配列[1,0,1,1,1,1,1,1]を返します.2番目のラウンジ以外のすべてのラウンジから距離があるからです.
時間制限ガイド
精度テスト:10秒
ストリート
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|である.