[programmers]Breutforce-カーペット(Python)

ソース

Brute Force:カーペット[Lv 2]

問題の説明

Leoはじゅうたんを買いに行きました.格子じゅうたんの列が見えました.真ん中は黄色で、一列は茶色で、下図のように見えます.

Leoは家に帰ってから、さっき見たじゅうたんの黄色と茶色の格子数を覚えたが、じゅうたん全体の大きさは覚えていない.
Leoがこのカーペットに茶色の格子の数茶色、黄色の格子の数黄色をパラメータとして与えた場合、カーペットの横方向と縦方向の寸法を順番に並べて返します.

せいげんじょうけん

茶色の格子の水茶色は8以上5000以下の自然水です.

黄色のメッシュの数は、1以上200000以下の自然数です.

カーペットの横方向の長さは、縦方向の長さ以上である.

I/O例

brownyellowreturn102[4, 3]81[3, 3]2424[8, 6]
 

Solution

説明する

def solution(brown, yellow):
    answer = []
    yellow_area = set()
    for i in range(1, yellow // 2 + 2):
        if yellow % i == 0:
            a, b = i, yellow // i
            tmp = tuple(sorted([a, b]))
            yellow_area.add(tmp)

    yellow_area = list(yellow_area)
    for aliquots in yellow_area:
        len_col = aliquots[0] + 2
        len_row = aliquots[1] + 2
        if len_col * len_row - yellow == brown:
            answer = [len_row, len_col]
            break
    return answer

yellowを1からyellow/2+1に分割し、残りの数が0の場合は、昇順に分割した数と値をtupleに設定し、yellow areaに追加します.つまり、黄色い薬液を貯蔵する.
次にfor文からyellow areaに格納されている値を取得し、カーペットの真ん中の領域を指定して、bownの領域が所定の値と同じかどうかを比較します.

結果

Best Code

def solution(brown, yellow):
    for i in range(1, int(yellow**(1/2))+1):
        if yellow % i == 0:
            if 2*(i + yellow//i) == brown-4:
                return [yellow//i+2, i+2]

原理自体と私が作ったコードの差は多くありません.しかし、私のコードよりも効率的で、長さが圧縮されています.
for文の範囲は黄色//2+2で、このコードでは黄色*(1/2)+1です.
それから私は(黄色の領域の横方向の長さ+2)(黄色の領域の縦方向の長さ+2)-黄色=brownを作成して、このコード
2*(i+黄色//i)=brown-4で検証した.

結果

私のコードに比べて、結果も確かに速いです.