위클리 챌린지3주차: 퍼즐 조각 채우기

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

코딩테스트 연습 - 3주차_퍼즐 조각 채우기

파이썬

생각의 흐름에 따라...

def solution(game_board, table):
    answer = 0
    blanks = find_pieces(game_board, 0)
    pieces = find_pieces(table, 1)
    for piece, piece_num in pieces:
        for blank, blank_num in blanks:
            if piece_num != blank_num:
                continue
            broken = False
            for _ in range(4):
                if piece == blank:
                    blanks.remove([blank, blank_num])
                    answer += blank_num
                    broken = True
                    break
                piece = turn_piece(piece)
            if broken:
                break
    return answer


def turn_piece(piece):
    length_y, length_x = len(piece), len(piece[0])
    new_piece = [[0 for _ in range(length_y)] for _ in range(length_x)]
    for i in range(length_y):
        for j in range(length_x):
            new_piece[j][length_y - i - 1] = piece[i][j]
    return new_piece


def find_pieces(board, num):
    pieces = []
    for y in range(len(board)):
        for x in range(len(board[0])):
            piece = set()
            check_point(num, x, y, board, piece)
            if piece:
                min_x, min_y, max_x, max_y = 50, 50, 0, 0
                for px, py in piece:
                    if min_x > px:
                        min_x = px
                    if min_y > py:
                        min_y = py
                    if max_x < px:
                        max_x = px
                    if max_y < py:
                        max_y = py
                new_piece = [[0 for _ in range(max_x - min_x + 1)] for _ in range(max_y - min_y + 1)]
                for px, py in piece:
                    new_piece[py - min_y][px - min_x] = 1
                pieces.append([new_piece, len(piece)])
    return pieces


def check_point(num, x, y, board, piece):
    if board[y][x] != num:
        return
    piece.add((x, y))
    board[y][x] = 1 if num == 0 else 0
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        if 0 <= x + dx < len(board[0]) and 0 <= y + dy < len(board) and board[y + dy][x + dx] == num:
            check_point(num, x + dx, y + dy, board, piece)
    return

테스트 1 〉	통과 (0.22ms, 10.4MB)
테스트 2 〉	통과 (0.22ms, 10.2MB)
테스트 3 〉	통과 (0.27ms, 10.3MB)
테스트 4 〉	통과 (0.24ms, 10.2MB)
테스트 5 〉	통과 (0.25ms, 10.2MB)
테스트 6 〉	통과 (2.77ms, 10.2MB)
테스트 7 〉	통과 (2.06ms, 10.3MB)
테스트 8 〉	통과 (1.97ms, 10.3MB)
테스트 9 〉	통과 (2.20ms, 10.2MB)
테스트 10 〉	통과 (15.96ms, 10.4MB)
테스트 11 〉	통과 (5.55ms, 10.3MB)
테스트 12 〉	통과 (8.54ms, 10.5MB)
테스트 13 〉	통과 (10.25ms, 10.3MB)
테스트 14 〉	통과 (0.19ms, 10.3MB)
테스트 15 〉	통과 (0.06ms, 10.2MB)
테스트 16 〉	통과 (0.09ms, 10.3MB)
테스트 17 〉	통과 (0.12ms, 10.4MB)
테스트 18 〉	통과 (0.12ms, 10.3MB)
테스트 19 〉	통과 (0.05ms, 10.2MB)
테스트 20 〉	통과 (0.06ms, 10.4MB)
테스트 21 〉	통과 (0.04ms, 10.3MB)
테스트 22 〉	통과 (0.05ms, 10.2MB)

조금 더 줄이려면... 이런 방법도 있다... 

https://comdoc.tistory.com/entry/Python-Zip-2%EC%B0%A8%EC%9B%90-%EB%B0%B0%EC%97%B4-%ED%9A%8C%EC%A0%84

Python Zip 2차원 배열 회전

def solution(game_board, table):
    answer = 0
    blanks = find_pieces(game_board, 0)
    pieces = find_pieces(table, 1)
    for piece, piece_num in pieces:
        for blank, blank_num in blanks:
            if piece_num != blank_num:
                continue
            broken = False
            for _ in range(4):
                if piece == blank:
                    blanks.remove([blank, blank_num])
                    answer += blank_num
                    broken = True
                    break
                piece = turn_piece(piece)
            if broken:
                break
    return answer


def turn_piece(piece):
    return [list(each) for each in reversed(tuple(zip(*piece)))]


def find_pieces(board, num):
    pieces = []
    for y in range(len(board)):
        for x in range(len(board[0])):
            piece = set()
            min_max = {'min_x': 50, 'min_y': 50, 'max_x': 0, 'max_y': 0}
            check_point(num, x, y, board, piece, min_max)
            if piece:
                new_piece = [[0 for _ in range(min_max['max_x'] - min_max['min_x'] + 1)]
                             for _ in range(min_max['max_y'] - min_max['min_y'] + 1)]
                for px, py in piece:
                    new_piece[py - min_max['min_y']][px - min_max['min_x']] = 1
                pieces.append([new_piece, len(piece)])
    return pieces


def check_point(num, x, y, board, piece, min_max):
    if board[y][x] != num:
        return
    piece.add((x, y))
    if min_max['min_x'] > x:
        min_max['min_x'] = x
    if min_max['min_y'] > y:
        min_max['min_y'] = y
    if min_max['max_x'] < x:
        min_max['max_x'] = x
    if min_max['max_y'] < y:
        min_max['max_y'] = y
    board[y][x] = 1 if num == 0 else 0
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        if 0 <= x + dx < len(board[0]) and 0 <= y + dy < len(board) and board[y + dy][x + dx] == num:
            check_point(num, x + dx, y + dy, board, piece, min_max)
    return

 

테스트 1 〉	통과 (0.24ms, 10.3MB)
테스트 2 〉	통과 (0.23ms, 10.2MB)
테스트 3 〉	통과 (0.27ms, 10.3MB)
테스트 4 〉	통과 (0.24ms, 10.2MB)
테스트 5 〉	통과 (0.25ms, 10.2MB)
테스트 6 〉	통과 (1.81ms, 10.2MB)
테스트 7 〉	통과 (1.67ms, 10.3MB)
테스트 8 〉	통과 (1.71ms, 10.3MB)
테스트 9 〉	통과 (1.54ms, 10.3MB)
테스트 10 〉	통과 (8.71ms, 10.5MB)
테스트 11 〉	통과 (6.18ms, 10.5MB)
테스트 12 〉	통과 (7.13ms, 10.5MB)
테스트 13 〉	통과 (7.20ms, 10.2MB)
테스트 14 〉	통과 (0.21ms, 10.3MB)
테스트 15 〉	통과 (0.07ms, 10.3MB)
테스트 16 〉	통과 (0.11ms, 10.3MB)
테스트 17 〉	통과 (0.14ms, 10.3MB)
테스트 18 〉	통과 (0.15ms, 10.2MB)
테스트 19 〉	통과 (0.06ms, 10.2MB)
테스트 20 〉	통과 (0.07ms, 10.2MB)
테스트 21 〉	통과 (0.04ms, 10.3MB)
테스트 22 〉	통과 (0.05ms, 10.2MB)

 

이것도... 

def turn_piece(piece):
    return list(map(list, reversed(tuple(zip(*piece)))))

 

golang

import "reflect"

func solution(game_board [][]int, table [][]int) (answer int) {
	blanks, blank_nums := find(game_board, 0)
	pieces, piece_nums := find(table, 1)
	for pIndex := range pieces {
		for bIndex := range blanks {
			if piece_nums[pIndex] != blank_nums[bIndex] {
				continue
			}
			broken := false
			for i := 0; i < 4; i++ {
				if reflect.DeepEqual(pieces[pIndex], blanks[bIndex]) {
					answer += blank_nums[bIndex]
					blanks[bIndex] = nil
					blank_nums[bIndex] = 0
					broken = true
					break
				}
				pieces[pIndex] = turn(pieces[pIndex])
			}
			if broken {
				break
			}
		}
	}
	return
}

func turn(piece [][]int) (newPiece [][]int) {
	lenY, lenX := len(piece), len(piece[0])
	for i := 0; i < lenX; i++ {
		var temp = make([]int, lenY)
		newPiece = append(newPiece, temp)
		for j := 0; j < lenY; j++ {
			newPiece[i][lenY-j-1] = piece[j][i]
		}
	}
	return newPiece
}

func find(board [][]int, num int) (pieces [][][]int, piece_nums []int) {
	for y := range board {
		for x := range board[0] {
			piece := map[[2]int]bool{}
			minMax := map[string]int{"minX": 50, "minY": 50, "maxX": 0, "maxY": 0}
			check(num, x, y, board, piece, minMax)
			if len(piece) != 0 {
				newPiece := [][]int{}
				for i := 0; i <= minMax["maxY"]-minMax["minY"]; i++ {
					temp := []int{}
					for j := 0; j <= minMax["maxX"]-minMax["minX"]; j++ {
						temp = append(temp, 0)
					}
					newPiece = append(newPiece, temp)
				}
				for key := range piece {
					px, py := key[0], key[1]
					newPiece[py-minMax["minY"]][px-minMax["minX"]] = 1
				}
				pieces = append(pieces, newPiece)
				piece_nums = append(piece_nums, len(piece))
			}
		}
	}
	return
}

func check(num, x, y int, board [][]int, piece map[[2]int]bool, minMax map[string]int) {
	if board[y][x] != num {
		return
	}
	piece[[2]int{x, y}] = true
	if minMax["minX"] > x {
		minMax["minX"] = x
	}
	if minMax["minY"] > y {
		minMax["minY"] = y
	}
	if minMax["maxX"] < x {
		minMax["maxX"] = x
	}
	if minMax["maxY"] < y {
		minMax["maxY"] = y
	}
	if num == 0 {
		board[y][x] = 1
	} else {
		board[y][x] = 0
	}
	for _, dxy := range [4][2]int{[2]int{1, 0}, [2]int{-1, 0}, [2]int{0, 1}, [2]int{0, -1}} {
		dx, dy := dxy[0], dxy[1]
		if 0 <= x+dx && x+dx < len(board[0]) && 0 <= y+dy && y+dy < len(board) && board[y+dy][x+dx] == num {
			check(num, x+dx, y+dy, board, piece, minMax)
		}
	}
}

테스트 1 〉	통과 (0.08ms, 4.28MB)
테스트 2 〉	통과 (0.07ms, 4.16MB)
테스트 3 〉	통과 (0.09ms, 3.66MB)
테스트 4 〉	통과 (0.07ms, 3.66MB)
테스트 5 〉	통과 (0.08ms, 4.29MB)
테스트 6 〉	통과 (0.62ms, 4.21MB)
테스트 7 〉	통과 (0.54ms, 3.65MB)
테스트 8 〉	통과 (0.57ms, 4.23MB)
테스트 9 〉	통과 (0.56ms, 4.29MB)
테스트 10 〉	통과 (3.53ms, 4.33MB)
테스트 11 〉	통과 (1.27ms, 4.29MB)
테스트 12 〉	통과 (2.29ms, 4.21MB)
테스트 13 〉	통과 (2.60ms, 4.28MB)
테스트 14 〉	통과 (0.06ms, 4.3MB)
테스트 15 〉	통과 (0.02ms, 4.28MB)
테스트 16 〉	통과 (0.04ms, 4.18MB)
테스트 17 〉	통과 (0.04ms, 4.29MB)
테스트 18 〉	통과 (0.05ms, 4.26MB)
테스트 19 〉	통과 (0.03ms, 3.68MB)
테스트 20 〉	통과 (0.02ms, 3.68MB)
테스트 21 〉	통과 (0.01ms, 4.29MB)
테스트 22 〉	통과 (0.01ms, 4.29MB)