[leetcode] 2352. Equal Row and Column Pairs 파이썬 코드

https://leetcode.com/problems/equal-row-and-column-pairs/

 

시간 초과가 났다.

class Solution(object):
    def equalPairs(self, grid):
        row = []
        col = []

        for i in range(len(grid)):
            tempRow = grid[i]
            row.append(tempRow)

        for i in range(len(grid)):
            tempCol = []
            for j in range(len(grid)):
                tempCol.append(grid[j][i])
            col.append(tempCol)
            # print(row)
            # print(col)

            comb = []

            for i in range(len(row)):
                rowChosen = row[i]
                for j in range(len(col)):
                    if col[j] == rowChosen:
                        combTemp = [i, j]
                        if combTemp not in comb:
                            comb.append(combTemp)
        
        return len(comb)

 

 

흐음. 

 

고민을 하다가 hashmap (딕셔너리)에 넣을 때 r1 : [3, 2, 1] 이렇게 row와 col 번호를 key에, 배열을 value에 넣지 말고, 반대로 배열을 key에, row와 col 번호를 value에 집어넣는 아이디어를 생각해냈다. 그런 arrayDict을 만들고 나서, arrayDict의 key, value를 돌리면서 value의 길이가 1개라면 pair가 없다는 것이니까 넘어간다 (continue). 만약 길이가 2 이상이라면, row와 col 개수를 세서 곱하면 pair의 개수가 나온다.

 

class Solution(object):
    def equalPairs(self, grid):
        arrayDict = defaultdict(list)

        for i in range(len(grid)):
            tempRow = tuple(grid[i])
            arrayDict[tempRow].append("r{}".format(i))

        for i in range(len(grid)):
            tempCol = []
            for j in range(len(grid)):
                tempCol.append(grid[j][i])
            arrayDict[tuple(tempCol)].append("c{}".format(i))

        pairCount = 0
        for key, value in arrayDict.items():
            if len(value) < 1:
                continue
            rCount, cCount = 0, 0
            for v in value:
                if v[0] == 'r':
                    rCount += 1
                else:
                    cCount += 1
            pairCount += rCount * cCount

        return pairCount