문제
상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)
다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.
사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.
출력
첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.
예제 입력 1
3
CCP
CCP
PPC
Plain Text
복사
예제 출력 1
3
Plain Text
복사
예제 입력 2
4
PPPP
CYZY
CCPY
PPCC
Plain Text
복사
예제 출력 2
4
Plain Text
복사
예제 입력 3
5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ
Plain Text
복사
예제 출력 3
4
Plain Text
복사
힌트
예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.
My solution
1.
N x N에서 인접한 두 칸을 선택해서 스왑해야 한다.
for ( i : 0 ~ N )
for ( j : 0 ~ N )
if( abs( i - j ) === 0 )
[graph[i], graph[j]] = [graph[j], graph[i]]
JSON
복사
2.
스왑하고 나면 가장 긴 연속 부분을 찾아 먹는다.(최대 개수를 구한다.)
JSON
복사
1. 교환 전에 먼저 모든 행과 열을 한 번씩만 탐색해주며 최댓값을 찾는다.
2. 사탕을 교환하고 그때 값이 바뀌는 행과 열에서 가장 긴 연속 부분을 탐색한 뒤
교환 전으로 다시 되돌려 놓는 방식을 반복해서 최댓값을 찾는다.
교환은 두 가지 종류를 해줘야 하는데,
첫 번째는 행 교환이다.
이때 값이 바뀌는 열 2개랑 행 1개를 탐색해서 최댓값을 업데이트한다.
두 번째는 열 교환이다.
마찬가지로 이때 값이 바뀌는 열 1개랑 행 2개를 탐색해서 최댓값을 업데이트한다.
이 문제는 node.js로 풀 수 없다. 맞춘 사람의 코드를 그대로 내도 틀렸다고 나온다.
Code
const solution = function (i) {
const [E, S, M] = i.toString().trim().split(' ').map(Number);
let year = 0;
while (++year) {
// year를 1로 만들지 않고 비교하기 위해 E, S, M 범위를 0 ~ N으로 변경, E : 0 ~ 15, S : 0 ~ 28, M : 0 ~ 19
if (
(year - E) % 15 === 0 &&
(year - S) % 28 === 0 &&
(year - M) % 19 === 0
) {
break;
}
}
console.log(year);
return year;
};
describe('날짜계산', () => {
it('TC1', () => {
expect(solution(`1 16 16`)).toStrictEqual(16);
});
it('TC2', () => {
expect(solution(`1 1 1`)).toStrictEqual(1);
});
it('TC3', () => {
expect(solution(`1 2 3`)).toStrictEqual(5266);
});
it('TC4', () => {
expect(solution(`15 28 19`)).toStrictEqual(7980);
});
});
JavaScript
복사
