https://www.acmicpc.net/problem/3085
3085번: 사탕 게임
문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하
www.acmicpc.net
방법 1 : 적절
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
char[][] arrCandies = new char[N][N];
// 입력
for (int i = 0; i < N; i++) {
char[] arrTemp = br.readLine().toCharArray();
arrCandies[i] = arrTemp;
}
// 원본 Max연속값 구하기
int Max = countMaxCandiesSquare(arrCandies);
// 위치 바꾼 후 Max연속값 구하기
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// 왼 <-> 오
if ((j + 1) < N) {
swap(arrCandies, i, j, true, false);
// 바꾼 라인에 대해서만 Max연속값 구하기
int tempMax = countMaxCandiesLine(arrCandies, i, j);
swap(arrCandies, i, j, true, true);
Max = (tempMax > Max) ? tempMax : Max;
}
// 위 <-> 아래
if ((i + 1) < N) {
swap(arrCandies, i, j, false, false);
// 바꾼 라인에 대해서만 Max연속값 구하기
int tempMax = countMaxCandiesLine(arrCandies, i, j);
swap(arrCandies, i, j, false, true);
Max = (tempMax > Max) ? tempMax : Max;
}
}
}
System.out.println(Max);
}
private static int countMaxCandiesLine(char[][] arrCandies, int i, int j) {
int Max = 0;
int N = arrCandies.length;
// 가로
for (int a = 0; a < 2; a++) {
if (i + a == N) {
break;
}
int count = 1;
for (int b = 0; b < N - 1; b++) {
if (arrCandies[i + a][b] == arrCandies[i + a][b + 1]) {
count++;
Max = (count > Max) ? count : Max;
continue;
}
count = 1;
}
}
// 세로
for (int b = 0; b < 2; b++) {
if (j + b == N) {
break;
}
int count = 1;
for (int a = 0; a < N - 1; a++) {
if (arrCandies[a][j + b] == arrCandies[a + 1][j + b]) {
count++;
Max = (count > Max) ? count : Max;
continue;
}
count = 1;
}
}
return Max;
}
private static int countMaxCandiesSquare(char[][] arrCandies) {
int Max = 0;
int N = arrCandies.length;
// 가로
for (int i = 0; i < N; i++) {
int count = 1;
for (int j = 0; j < N - 1; j++) {
if (arrCandies[i][j] == arrCandies[i][j + 1]) {
count++;
Max = (count > Max) ? count : Max;
continue;
}
count = 1;
}
}
// 세로
for (int j = 0; j < N; j++) {
int count = 1;
for (int i = 0; i < N - 1; i++) {
if (arrCandies[i][j] == arrCandies[i + 1][j]) {
count++;
Max = (count > Max) ? count : Max;
continue;
}
count = 1;
}
}
return Max;
}
private static void swap(char[][] arrCandies, int i, int j, boolean isRight, boolean isReverse) {
int a = i;
int b = j;
if (isRight) {
b = j + 1;
if (isReverse) {
int temp = j;
j = b;
b = temp;
}
} else {
a = i + 1;
if (isReverse) {
int temp = i;
i = a;
a = temp;
}
}
char temp = arrCandies[i][j];
arrCandies[i][j] = arrCandies[a][b];
arrCandies[a][b] = temp;
}
}
Colored by Color Scripter
|
방법 2
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
char[][] arrCandies = new char[N][N];
// 입력
for (int i = 0; i < N; i++) {
char[] arrTemp = br.readLine().toCharArray();
arrCandies[i] = arrTemp;
}
// 변경 후 Max연속값 구하기
int Max = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if ((j + 1) < N) {
swap(arrCandies, i, j, true, false);
int tempMax = countMaxCandiesSquare(arrCandies);
swap(arrCandies, i, j, true, true);
Max = (tempMax > Max) ? tempMax : Max;
}
if ((i + 1) < N) {
swap(arrCandies, i, j, false, false);
int tempMax = countMaxCandiesSquare(arrCandies);
swap(arrCandies, i, j, false, true);
Max = (tempMax > Max) ? tempMax : Max;
}
}
}
System.out.println(Max);
}
private static int countMaxCandiesSquare(char[][] arrCandies) {
int N = arrCandies.length;
int Max = 0;
// 가로
for (int i = 0; i < arrCandies.length; i++) {
int count = 1;
for (int j = 0; j < N - 1; j++) {
if (arrCandies[i][j + 1] == arrCandies[i][j]) {
count++;
Max = (count > Max) ? count : Max;
continue;
}
count = 1;
}
}
// 세로
for (int j = 0; j < arrCandies.length; j++) {
int count = 1;
for (int i = 0; i < N - 1; i++) {
if (arrCandies[i + 1][j] == arrCandies[i][j]) {
count++;
Max = (count > Max) ? count : Max;
continue;
}
count = 1;
}
}
return Max;
}
private static void swap(char[][] arrCandies, int i, int j, boolean isRight, boolean isReverse) {
int a = i;
int b = j;
if (isRight) {
b = j + 1;
if (isReverse) {
int temp = j;
j = b;
b = temp;
}
} else {
a = i + 1;
if (isReverse) {
int temp = i;
i = a;
a = temp;
}
}
char temp = arrCandies[i][j];
arrCandies[i][j] = arrCandies[a][b];
arrCandies[a][b] = temp;
}
}
Colored by Color Scripter
|
방법 1은 빅O표기법으로 N의 3제곱, 방법 2는 N의 4제곱이다.
당연히 방법 1이 더 빠르다.
TIP
N×N크기의 사탕상자.
사탕의 색이 다른 인접한 두 칸의 사탕을 서로 교환한다.
이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
문제에 힌트 또는 함정(?)이 있다.
인접한 두칸의 사탕을 교환했다면, 교환하지 않은 나머지 칸들의 상태는 어떠할까?
당연하게도,,, 교환하기 전 후가 같다.
즉, 교환할 때마다 사탕 상자 전체를 확인할 필요가 없고 (방법 2),
처음 한번만 전체를 확인하면 된다.
그다음부터는 교환의 영향이 미치는 행, 열만 확인해주면 된다. (방법 1)
사실 왼/오 또는 위/아래를 교환하면
변화되는 행 또는 열은 총 3개 라인이다.
(왼/오 : 행1개 열2개, 위/아래 : 행2개 열1개)
하지만, 이 문제가 코딩테스트에서 나왔다고 생각하면
예외처리를 그렇게 많이 할 겨를이 없을 것 같다.
그래서 약간의 중복을 감수하고
왼/오 위/아래 모두 행2개 열2개씩 확인하도록 했다.
비록 오늘은 하루종일 씨름했지만
실제 코딩 테스트에서 방법1의 문제 분석과 구현 판단만 할 수 있으면 소원이 없겠다:)
'Algorithm > BOJ' 카테고리의 다른 글
| [BOJ]7568번: 덩치 (0) | 2020.01.11 |
|---|---|
| [BOJ]1476번: 날짜 계산(java, c++) (0) | 2020.01.06 |
| [BOJ]2309번: 일곱 난쟁이(java, c++) (0) | 2020.01.04 |
| [BOJ]2225번: 합분해(java) (0) | 2019.10.19 |
| [BOJ]1699번: 제곱수의 합(java, c++) (0) | 2019.10.19 |
댓글