문제
상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.
출력
첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.
<코드>
n = int(input())
board = [list(input().strip()) for _ in range(n)]
def get_max_length(board, n):
max_len = 1
for i in range(n):
row_len = 1
col_len = 1
for j in range(1, n):
if board[i][j] == board[i][j - 1]:
row_len += 1
else:
row_len = 1
if board[j][i] == board[j - 1][i]:
col_len += 1
else:
col_len = 1
max_len = max(max_len, row_len, col_len)
return max_len
max_candies = 0
for i in range(n):
for j in range(n):
if j + 1 < n:
board[i][j], board[i][j + 1] = board[i][j + 1], board[i][j]
max_candies = max(max_candies, get_max_length(board, n))
board[i][j], board[i][j + 1] = board[i][j + 1], board[i][j]
if i + 1 < n:
board[i][j], board[i + 1][j] = board[i + 1][j], board[i][j]
max_candies = max(max_candies, get_max_length(board, n))
board[i][j], board[i + 1][j] = board[i + 1][j], board[i][j]
print(max_candies)
<풀이과정>
- 최대 연속 길이 계산 함수 (get_max_length):
- board와 n을 입력받아 행과 열에서 최대 연속된 동일 색상의 길이를 계산
- 각 행과 열에 대해 연속된 동일 색상의 최대 길이 찾기
- 사탕 교환 및 최대 연속 부분 계산:
- 이중 for 루프를 사용하여 모든 칸을 순회
- if j + 1 < n은 현재 칸 board[i][j]의 오른쪽에 칸이 존재하는지 확인
- if i + 1 < n은 현재 칸 board[i][j]의 아래에 칸이 존재하는지 확인
- 현재 칸과 오른쪽 칸을 교환하고 최대 연속 길이를 계산한 후 원래 상태로 복구(가능한 상태 모두 계산하기 위해)
- board[i][j], board[i][j + 1] = board[i][j + 1], board[i][j] 에서 복구
- 현재 칸과 아래쪽 칸을 교환하고 최대 연속 길이를 계산한 후 원래 상태로 복구
- 각 교환 후 최대 연속 길이를 갱신하여 최종 결과 출력
'2024 코딩테스트 스터디' 카테고리의 다른 글
[7주_6일차] 백준-1107 리모컨(Python) (0) | 2024.07.21 |
---|---|
[7주_5일차] 백준-1476 날짜 계산(Python) (1) | 2024.07.20 |
[7주_3일차] 프로그래머스-문자열 내림차순으로 배치하기(Python) (0) | 2024.07.19 |
[7주_3일차] 프로그래머스-조건에 맞는 도서 리스트 출력하기(MySQL) (0) | 2024.07.18 |
[7주_2일차] 프로그래머스-내적(Python) (0) | 2024.07.17 |