[ํ๋ก๊ทธ๋๋จธ์ค] ๐งฑ ํ๋ ์ฆ 4 ๋ธ๋ก - [1์ฐจ] 2018 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ์ฑ์ฉ / Python
๐งฑ ํ๋ ์ฆ 4 ๋ธ๋ก ๋ฌธ์ ํ์ด๋ณด๊ธฐ
๐ ๋์ ์ฝ๋
dx = [0, 1, 0, 1]
dy = [0, 0, 1, 1]
def safe(width, height, c_idx, r_idx):
for x, y in zip(dx,dy):
if width-1 < x+c_idx or x+c_idx < 0 or height-1 < y+r_idx or y+r_idx < 0:
return False
return True
def del_check(board, c_idx, r_idx):
square_set = set()
for x, y in zip(dx,dy):
square_set.add(board[y+r_idx][x+c_idx])
if len(square_set) == 1 and square_set != {" "}:
return True
return False
def del_block(board, c_idx, r_idx):
for x, y in zip(dx,dy):
board[y+r_idx][x+c_idx] = ""
return board
def total_del_block(board):
total = 0
for row in board:
for block in row:
if block == ' ':
total += 1
return total
def drop_block(width, height, board):
for x_idx in range(width):
tmp_lst = []
for y_idx in range(height):
tmp_lst.append(board[y_idx][x_idx])
col_str = "".join(tmp_lst)
col_str = (height-len(col_str))*" " + col_str
for y_idx in range(height):
board[y_idx][x_idx] = col_str[y_idx]
return board
def solution(height, width, board):
board = [[block for block in row] for row in board]
answer = 0
while True:
del_lst = []
for r_idx in range(height):
for c_idx in range(width):
if safe(width, height, c_idx, r_idx):
if del_check(board, c_idx, r_idx):
del_lst.append([c_idx, r_idx])
if len(del_lst) == 0:
break
for del_pos in del_lst:
board = del_block(board, del_pos[0], del_pos[1])
board = drop_block(width, height, board)
return total_del_block(board)
์ด ๋ฌธ์ ๋ฅผ ํธ๋ ๊ณผ์ ์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
- ๊ฐ์ ๋ชจ์์ 2 X 2 ๋ธ๋ก์ ์ฐพ๋๋ค.
- ๊ทธ ๋ธ๋ก์ ์ ๊ฑฐํ๋ค.
- ๋ธ๋ก์ ์๋๋ก ๋จ์ด๋จ๋ ค ๋น ๊ณต๊ฐ์ ์ฑ์ด๋ค.
- ๋ ์ด์ ์ง์ธ ๋ธ๋ก์ด ์์ ๋๊น์ง ์ํ์ ๋ฐ๋ณตํ๋ค.
์ด๋ฐ ์ํ์ด ์ ์ ๋ฆฌ๋๊ณ ๊ฐ ์ํ๋ณ๋ก ์ฝ๋๊ฐ ๊ธด ๋ฌธ์ ๋ ๊ฐ๊ฐ์ ์ํ์ ํจ์๋ก ๋ง๋ค์ด์ ์งํํ๋ฉด ์ฝ๋๊ฐ ๋ ๋ณต์กํ๊ฒ ์งค ์ ์์ต๋๋ค. ๋ฌธ์ ํ์ด์ ์์ ํธ์๋ฅผ ์ํด
board = [[block for block in row] for row in board]
๋ฅผ ํตํด board
๋ฅผ 2์ฐจ์ ๋ฐฐ์ด๋ก ๋ฐ๊ฟ์ค๋๋ค.
del_lst = []
for r_idx in range(height):
for c_idx in range(width):
if safe(width, height, c_idx, r_idx):
if del_check(board, c_idx, r_idx):
del_lst.append([c_idx, r_idx])
์ฐ์ ๊ฐ์ ๋ชจ์์ 2 X 2 ๋ธ๋ก์ ์ฐพ๋ ๊ณผ์ ์
๋๋ค. ์ฌ๊ธฐ์ ๋ฏธ๋ฆฌ ๋ง๋ค์ด๋ dx
์ dy
๋ฅผ ์ด์ฉํฉ๋๋ค. dx
์ dy
๋ ๊ฐ๊ฐ x
์ y
์ ๋ํด์ ๋ธ๋ก์ ๊ฒ์ฆํ๋ ์ญํ ์ ํฉ๋๋ค.
def safe(width, height, c_idx, r_idx):
for x, y in zip(dx,dy):
if width-1 < x+c_idx or x+c_idx < 0 or height-1 < y+r_idx or y+r_idx < 0:
return False
return True
์ฐ์ ํต๊ณผํ ๊ฒ์ safe()
ํจ์์
๋๋ค. dx
์ dy
๋ฅผ ๋ํ๋ ๊ณผ์ ์์ board
์ index
๋ฅผ ๋๋ ๊ฒฝ์ฐ๋ฅผ ๋ฏธ๋ฆฌ ๋ฐฉ์งํด์ฃผ๋ ์ญํ ์ ํฉ๋๋ค.
def del_check(board, c_idx, r_idx):
square_set = set()
for x, y in zip(dx,dy):
square_set.add(board[y+r_idx][x+c_idx])
if len(square_set) == 1 and square_set != {" "}:
return True
return False
๋ค์์ 2 X 2 ๋ธ๋ก์ด ์ง์์ง ์ ์๋ ์ง๋ฅผ ๊ฒ์ฆํ๋ del_check()
ํจ์์
๋๋ค. ๊ฐ ๋ธ๋ก์ set
์๋ฃํ์ ์ถ๊ฐํ์ฌ ๋ชจ๋ ๊ฐ์ ๋ชจ์์ด๋ผ๋ฉด set
์ ํฌ๊ธฐ๊ฐ 1์ด๊ณ , ๊ทธ ๋ชจ์์ด ๋น ๊ณต๊ฐ์ด ์๋ ์ True
๋ฅผ ๊ทธ ์ธ์๋ False
๋ฅผ ๋ฐํํฉ๋๋ค. del_check()
์ ํตํด ๊ฒ์ฆ๋ c_idx
์ r_idx
๋ del_lst
์ ์ ์ฅ๋ฉ๋๋ค.
def del_block(board, c_idx, r_idx):
for x, y in zip(dx,dy):
board[y+r_idx][x+c_idx] = ""
return board
del_lst
์ ์์๋ฅผ ์ด์ฉํ์ฌ board
์ ๋ธ๋ก์ ์ ๊ฑฐํด์ค๋๋ค. ๋ง์ฝ del_lst
์ ํฌ๊ธฐ๊ฐ 0
์ด๋ผ๋ฉด ์ง์ธ ๋ธ๋ก์ด ์๋ค๋ ๋ป์ด๊ธฐ ๋๋ฌธ์ ๋ฌดํ ๋ฃจํ๋ฅผ break
ํด์ค๋๋ค.
def drop_block(width, height, board):
for x_idx in range(width):
tmp_lst = []
for y_idx in range(height):
tmp_lst.append(board[y_idx][x_idx])
col_str = "".join(tmp_lst)
col_str = (height-len(col_str))*" " + col_str
for y_idx in range(height):
board[y_idx][x_idx] = col_str[y_idx]
return board
๋ธ๋ก์ ๋จ์ด๋จ๋ ค ๋น ๊ณต๊ฐ์ ์ฑ์ฐ๋ ๊ณผ์ ์
๋๋ค. ์ฌ๋ฌ ๋ฐฉ๋ฒ์ด ์๊ฒ ์ง๋ง ์ ๋ ๋ฌธ์์ด์ ์ด์ฉํ์์ต๋๋ค. ์ผ์ชฝ๋ถํฐ ์ธ๋ก ๋ฐฐ์ด์ ๋ฐ์ tmp_lst
์ ์ ์ฅํฉ๋๋ค. ๊ทธ ๋ฐฐ์ด์ join์ ์ด์ฉํ์ฌ ๋น ๊ณต๊ฐ์ ์์์ค๋๋ค. ๋ฌธ์์ด ๊ธธ์ด๋ฅผ ๋ค์ ๋์ด์ ๋ง์ถ๊ธฐ ์ํด ์์ ๋น ์นธ์ ์ ์ ํ ์ถ๊ฐํฉ๋๋ค. ์ด๋ฅผ ๋ฐํ์ผ๋ก ๋ค์ board
๋ฅผ ์
๋ฐ์ดํธํด์ค๋๋ค. ์ด ๊ณผ์ ์ ์ฌ๋ผ์ง ๋ธ๋ก์ด ์์ ๋๊น์ง ๋ฐ๋ณตํฉ๋๋ค.
def total_del_block(board):
total = 0
for row in board:
for block in row:
if block == ' ':
total += 1
return total
๊ฒฐ๊ณผ๊ฐ์ ์ ์ฒด์์ ์ฌ๋ผ์ง ๋ธ๋ก์ ๊ฐฏ์๋ฅผ ๊ตฌํ๋ ๊ฒ์ด๊ธฐ ๋๋ฌธ์ board
๋ฅผ ํ์ธํ๋ฉด์ ๋น ์นธ์ธ ๋ธ๋ก์ ๊ฐฏ์๋ฅผ ์ธ๋ฉด ๋ฌธ์ ๋ ๋ง๋ฌด๋ฆฌ๋ฉ๋๋ค.
Written with StackEdit.
'Algorithm > Problem Solving' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๋๊ธ
์ด ๊ธ ๊ณต์ ํ๊ธฐ
-
๊ตฌ๋
ํ๊ธฐ
๊ตฌ๋ ํ๊ธฐ
-
์นด์นด์คํก
์นด์นด์คํก
-
๋ผ์ธ
๋ผ์ธ
-
ํธ์ํฐ
ํธ์ํฐ
-
Facebook
Facebook
-
์นด์นด์ค์คํ ๋ฆฌ
์นด์นด์ค์คํ ๋ฆฌ
-
๋ฐด๋
๋ฐด๋
-
๋ค์ด๋ฒ ๋ธ๋ก๊ทธ
๋ค์ด๋ฒ ๋ธ๋ก๊ทธ
-
Pocket
Pocket
-
Evernote
Evernote
๋ค๋ฅธ ๊ธ
-
[ํ๋ก๊ทธ๋๋จธ์ค] โ ์ ํ๋ฒํธ ๋ชฉ๋ก / Python
[ํ๋ก๊ทธ๋๋จธ์ค] โ ์ ํ๋ฒํธ ๋ชฉ๋ก / Python
2019.02.14 -
[ํ๋ก๊ทธ๋๋จธ์ค] ๐ทโโ๏ธ ์ ๋ง๋๊ธฐ / Python
[ํ๋ก๊ทธ๋๋จธ์ค] ๐ทโโ๏ธ ์ ๋ง๋๊ธฐ / Python
2019.02.14 -
[ํ๋ก๊ทธ๋๋จธ์ค] ๐ฉโ๐ผ ๋ด์ค ํด๋ฌ์คํฐ๋ง - [1์ฐจ] 2018 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ์ฑ์ฉ / Python / KAKAO BLIND RECRUITMENT
[ํ๋ก๊ทธ๋๋จธ์ค] ๐ฉโ๐ผ ๋ด์ค ํด๋ฌ์คํฐ๋ง - [1์ฐจ] 2018 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ์ฑ์ฉ / Python / KAKAO BLIND RECRUITMENT
2019.02.14 -
[ํ๋ก๊ทธ๋๋จธ์ค] ๐จโ๐ป ์บ์ - [1์ฐจ] 2018 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ์ฑ์ฉ / Python
[ํ๋ก๊ทธ๋๋จธ์ค] ๐จโ๐ป ์บ์ - [1์ฐจ] 2018 ์นด์นด์ค ๋ธ๋ผ์ธ๋ ์ฑ์ฉ / Python
2019.02.13