[プログラマー]不良ユーザー:フルナビゲーション

質問する

https://programmers.co.kr/learn/courses/30/lessons/64064

概要

「*」処理を受けた不良ユーザーと実際のユーザーのIDリストを入力します.
次に、不良ユーザとなる可能性のあるユーザのIDを照合し、異なる可能な組み合わせの個数を算出する問題である.
たとえば、[a*cd、ab*d]、[abcd、abxd、abvd]と入力した場合、可能な組み合わせの数は次のようになります. 
(abcd,abxd)(abcd,abvd)(abxd,abvd)の3つ.

問題を解く

最初から逆追跡の解決策を思いついた.△ここまで来ればよかった.
しかし,解くと問題点(ABC,XYZ)と(XYZ,ABC)は同じデータであるため,重複を解消する必要がある.
これはDFSプールでよく見られるタイプです.
順序が逆転しているが、内容が同じである場合は、ビットマスクとバイナリデータを使用します.  解決しました.
例えば、user idの長さは3であり、user id[0]およびuser id[1]が不良ユーザ候補となる場合は「011」と表す.順序に関係なく、同じIDを入力すれば結果値の重複は解消されます.
しかし、私のソースには重複除外結果値よりも大きな問題があります.
テストケース5ではTLEを受信し続け,コードを長時間修正した.
逆トレース機能があり、重複結果値を消去する機能もありますが、逆トレース再帰関数内部論理では不要な場合の数が多すぎます.
バックグラウンドトラッキングロジックでは,コールスタックごとに二重砲口を用い,すべてのブロックID->すべてのユーザIDの順序で探索した.
しかし、このようにすると、callスタックごとに不要な探索が繰り返されます.
あるcallスタックで、不良ユーザとユーザのアイデンティティが一致し、次のcallスタックに移動すると、callスタックは最後まで無条件にアイデンティティ[0]を再試行します.ここで条件文をうまく処理しても,既に使用されているブロックIDの探索に時間を費やす.
では、二重砲口で、ブロックコード砲口のrange開始インデックス+1を、次のコールスタックで無条件にインデックス上に、ブロックコードから検索してもいいですか? 
この問題とは異なり、簡単な例を挙げて説明します.
[a,b,c,d,e,f]にはリストXがある.
検索Xのfor文をbacktrackingロジックに書くと、呼び出しスタックごとにa~zを検索する必要があります.
深さ優先ナビゲーションであるため、インデックスを調整しました. abcdefは最初に戻り、次いでe->fとなり、次のcallスタックに移動します. abcdffを 回復します.
ここで問題が発生しました.
1.すべての遮蔽されたアイデンティティが一致しなければならない(eの喪失)
2.インデックスを調整したが、最終的には検索範囲を調整したので、1回のコールスタックで不要な複数のIDを検索する.
私が欲しいのは、Call StackでブロックIDを受け取ると、ブロックIDはそのCall Stackでしか管理されず、他のCall Stackでは別のブロックIDしか管理されない方式で、rangeの開始インデックスを調整しても最終的にはforゲートなので、1つのCall Stackで複数のブロックIDを検索します. 
したがって、この問題は、最初から二重砲口を使用する問題ではなく、idリストを無効にするインデックスとしてcallスタックの深さを利用して、1つのcallスタックで1つのブロックIDしか閲覧できないことを実現する.(再帰関数では、callスタックは深さで区切られているため、callスタックの深さはunique valueです.)
また,この方式は組合せの問題と考えられるが,実際には並べ替え問題であり,並べ替えをDFSとして実現する.
したがって、itertoolsライブラリの 置換で解いても、この問題は解決できます.
整理すると、
1つの不良ユーザ情報は、複数のユーザIDに一致することができる.
順序を考慮する必要があるという意味では、ソートではなく、1つの不良ユーザ情報にすべてのユーザIDが一致するのがソートの問題である.
これは,ユーザのアカウントがすべての位置に一度入ることができれば,数を考慮し,いずれの場合もすべてのユーザのIDが不良ユーザと一致するか否かを判断することを意味する.
「位置」は「不良ユーザ」であり、「ユーザID」はどの「位置」に入ることができるか分からないので、全ての「位置」にユーザIDを置いて探索する.    
今後DFS/backtracking問題でCall Stackでfor文を使用する場合は、新しいCall Stackでは常に新しいfor文で最初から始め、問題を解決することをよく考えなければなりません.
そしてソートを順番のある順序と見なすよりも.
配列自体は,ある値がすべての位置に1回入ることができると考えられる数である.
最後に,DFSでシーケンスを求めると,callスタックの深さをプレースホルダとする.
そして,入力値のみを返すfor文は,入力した値を例外的に処理し,最後に基本条件から返すことを実現する.

コード#コード#

from collections import defaultdict

def find(banned,user):
  if len(banned) != len(user):
    return False
  for i in range(len(banned)):
    if banned[i]=="*":continue
    elif user[i]!=banned[i]:
      return False
  return True

def backtrk(d, bidx, user_id, banned_id, vistB, vistU, avoidDup, avoidDupDict):
  global ans

  if d == len(banned_id):
    if avoidDupDict[avoidDup]==0:
      avoidDupDict[avoidDup]=1
      ans+=1
    return

    # 순열 : 한명의 불량 사용자당 가능한 아이디를 탐색, 깊이가 불량사용자의 인원수만큼 들어가게 되면 모든 불량 사용자의 아이디 매칭 완료 됐다는 의미
    # 백트래킹으로 다시 빠져 나와서 한명의 불량 사용자에 대한 또 다른 가능한 유저 아이디 추출함.
    # 하나의 콜스택에서는 하나의 불량 사용자만 다뤄야 함. 하나의 콜스택에서 여러명의 불량사용자를 다루면 안됨. 이러면 거듭제곱꼴 형태가 됨.

  bb=banned_id[bidx]
  for u in range(len(user_id)):
    if not vistU[u] and find(bb, user_id[u]): # 이미 사용된 아이디, 아이디 형식 확인
      vistU[u]=1
      backtrk(d+1, bidx+1, user_id, banned_id, vistB, vistU, avoidDup|(1<<u), avoidDupDict)
      vistU[u]=0

def solution(user_id, banned_id):
  global ans
  ans = 0
  vistU=[0]*len(user_id)
  vistB=[0]*len(banned_id)
  avoidDupDict = defaultdict(int)
  backtrk(0, 0, user_id, banned_id, vistB, vistU, 1<<len(user_id), avoidDupDict)
  return ans

print(solution(["aaaaaaaa", "bbbbbbbb", "cccccccc", "dddddddd", "eeeeeeee", "ffffffff", "gggggggg", "hhhhhhhh"],
               ["********","********","********","********","********","********","********","********"]))
print(solution(["frodo", "fradi", "crodo", "abc123", "frodoc"], ["fr*d*", "abc1**"]))
print(solution(["frodo", "fradi", "crodo", "abc123", "frodoc"], ["*rodo", "*rodo", "******"]))
print(solution(["frodo", "fradi", "crodo", "abc123", "frodoc"], ["fr*d*", "*rodo", "******", "******"]))