✅ BOJ Implementation
🎈 10988 팰린드롬인지 확인하기
팰린드롬이란 앞으로 읽든 뒤로 읽든 같은 단어를 의미한다.
ex) level, noon 등입력값으로 단어가 주어지고 해당 단어가 팰린드롬이면 1을, 아니면 0을 출력하는 문제
word = list(input())
if list(reversed(word)) == word:
print(1)
else:
print(0)< 풀이 과정 >
주어진 단어를 애초에 list로 받아들여준다.
- 만일 입력값에 숫자가 포함된다면 list(str(input()))을 사용했겠지만, 문자만 포함되므로 list(input())을 사용해 준다.
- 이후 list 자료구조의 reversed 함수를 이용해 리스트 역순과 리스트가 같은 경우, 팰린드롬이므로 1을, 아닌 경우 0을 출력한다
-> 추가적으로 stack자료구조를 활용해 해당 문제를 해결할 수도 있다.
🎈 12100 2048 (Easy)
2048 게임은 4X4 크기의 보드에서 블록을 상하 좌우로 이동시켜 최대 5번 이동시켜 만들 수 있는 가장 큰 블록을 출력하는 문제. (단, 블록이 추가되는 경우 X)
- 입력값은 다음과 같다 : 첫줄에 보드 크기 N, 둘째 줄부터 N줄 만큼 게임판 초기 상태가 주어진다. 블록에 쓰여진 수의 범위는 [2,1024]이고 0은 빈칸을 의미한다.
from copy import deepcopy
# Input setting
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
# 주어진 보드판 내 숫자 이동 시 변화하는 move함수 생성
def move(board, dir):
# 북쪽으로 이동
if dir == 0:
for j in range(n):
# 제일 위쪽에 있는 0번째 행 지정
size = 0
for i in range(1, n):
# 보드 내 빈칸이 아닌 것들에 한해 원래값 val로 저장, 현 위치 0처리
if board[i][j]:
val = board[i][j]
board[i][j] = 0
# 0번째 행의 빈칸이 있으면 val로 대체
if board[size][j] == 0:
board[size][j] = val
# 값이 동일하다면 2배 처리 후 아래 값과 병합 처리 X위해 size + 1
elif board[size][j] == val:
board[size][j] = val*2
size += 1
# 값이 동일하지 않다면 size+1로 병합처리 X 후 원래 값 그대로 냅두기
else:
size += 1
board[size][j] = val
# 동쪽으로 이동
elif dir == 1:
for i in range(n):
# 제일 동쪽에 있는 n-1번째 열 지정
size = n-1
for j in range(n-2, -1, -1):
# 보드 내 빈칸이 아닌 것들에 한해 원래값 val로 저장, 현위치 0처리
if board[i][j]:
val = board[i][j]
board[i][j] = 0
# n-1번째 열이 빈칸인 경우 val로 대체
if board[i][size] == 0:
board[i][size] = val
# 값이 동일하면 2배처리 후 size는 n-2로 대체
elif board[i][size] == val:
board[i][size] = val*2
size -= 1
# 값이 동일하지 않으면 size n-2 처리 후 원래값 그대로 냅두기
else:
size -= 1
board[i][size] = val
# 남
elif dir == 2:
for j in range(n):
size = n-1
for i in range(n-2, -1, -1):
if board[i][j]:
val = board[i][j]
board[i][j] = 0
if board[size][j] == 0:
board[size][j] = val
elif board[size][j] == val:
board[size][j] = val*2
size -= 1
else:
size -= 1
board[size][j] = val
# 서
else:
for i in range(n):
size = 0
for j in range(1, n):
if board[i][j]:
val = board[i][j]
board[i][j] = 0
if board[i][size] == 0:
board[i][size] = val
elif board[i][size] == val:
board[i][size] = val*2
size += 1
else:
size += 1
board[i][size] = val
return board
def search(graph, cnt):
# 전역변수 처리
global answer
# 5번 이동이 끝난 경우 answer에 보드 내 최대값 저장 후 리턴
if cnt == 5:
for i in range(n):
for j in range(n):
answer = max(answer, graph[i][j])
return
# 각 direction 별로 재귀 탐색 진행
# 이때 deepcopy로 graph를 복사해주어야 기존 주어진 보드판 내 숫자를 고정시킬 수 있다.
for direction in range(4):
tmp = move(deepcopy(graph), direction)
search(tmp, cnt+1)
answer = 0
search(board, 0)
print(answer)< 풀이 과정 >
약 1시간 정도 걸렸던 문제.
풀이 방식은 bruteforce라고 판단한다.
우선 5번의 동서남북 이동과정 총 4^5의 경우의 수를 모두 확인하여 그 중 보드판 내 최대값을 골라야 하는 문제.
- 동서남북 방향을 탐색하는 함수를 생성한다. 이때 블록 이동 시 블록 내 숫자 변화에 유의한다.
- 이후 search함수로 재귀 탐색을 진행하여 주어진 board를 움직여 최대값을 탐색해준다.
🎈 주의할 점.
- 1024라는 경우의 수를 체킹해주기 위해선 deepcopy로 원본을 유지하는 것이 중요.
- board를 북동남서 방향으로 이동시켜주면서 값의 변화에 유의
To be a DataScientist