곽로그
[백준 3085, Java] 사탕 게임 본문
반응형
문제
3085번: 사탕 게임
첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.
www.acmicpc.net
최신버전 alwaysbemoon.tistory.com/241
풀이
1. 행을 순회하면서 인접한/같은 색의 칸을 탐색한다
2. 인접한/ 같은 색의 칸의 색깔 위치를 바꾼다
3. 바꾼 위치에 대해서 가장 긴 연속하는 색의 갯수를 구한다
의 순서로 문제를 풀면된다. 이때 "인접한"의 조건은 한 칸을 기준으로 오른쪽 칸/ 아래칸과 비교를 한다. 이와같이 할 경우 시간복잡도는 N의 4제곱이 된다.
여기서 시간복잡도를 줄이는 방법은 바뀐 위치의 행, 열에 대해서만 가장 긴 연속하는 색의 갯수를 구하는 거다. 그럴경우, 가장 긴 연속하는 색의 갯수를 구하는 시간복잡도가 N제곱에서 3N으로 줄어든다. 근데 이거 내가 한 코드는 너무 조잡해서 맞는 풀이인지는 모르겠다. 204 -> 168ms만큼 줄기는 한다.
코드
1. 맵을 복사
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
public static int N;
public static char[][] map;
public static char[][] switchedMap;
public static int maxCount;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
map = new char[N][N];
switchedMap = new char[N][N];
for(int row = 0 ; row<N; row++) {
String line = br.readLine().trim();
for(int column = 0; column<N; column++) {
map[row][column] = line.charAt(column);
}
}
selectCandy();
bw.write(String.valueOf(maxCount));
bw.flush();
}
public static void selectCandy() {
for(int r= 0 ;r<N; r++) {
for(int c=0; c<N; c++) {
char pickCandy1 = map[r][c];
char pickCandy2 = ' ';
if(c+1<N) {
pickCandy2 = map[r][c+1];
if(pickCandy1 != pickCandy2) {
//색깔다른 인접한 사탕 자리 바꾸기
copyMap();
switchedMap[r][c] = pickCandy2;
switchedMap[r][c+1] = pickCandy1;
calculateMax();
}
}
if(r+1<N) {
pickCandy2 = map[r+1][c];
if(pickCandy1 != pickCandy2) {
//색깔다른 인접한 사탕 자리 바꾸기
copyMap();
switchedMap[r][c] = pickCandy2;
switchedMap[r+1][c] = pickCandy1;
calculateMax();
}
}
}
}
}
public static void calculateMax() {
for(int r = 0 ; r<N; r++) {
int count = 1;
for(int c= 1; c<N; c++) {
if(switchedMap[r][c] == switchedMap[r][c-1]) {
++count;
maxCount = Math.max(maxCount, count);
}
else {
count =1;
}
}
}
for(int c=0; c<N; c++) {
int count = 1;
for(int r=1; r<N; r++) {
if(switchedMap[r][c] == switchedMap[r-1][c]) {
++count;
maxCount = Math.max(maxCount, count);
}
else {
count =1;
}
}
}
}
public static void copyMap() {
for(int row = 0 ; row<N; row++) {
for(int column = 0; column<N; column++) {
switchedMap[row][column] = map[row][column];
}
}
}
}
2. 맵을 복사하지 않음
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
public static int N;
public static char[][] map;
public static int maxCandy = 0;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
map = new char[N][N];
for(int r = 0; r<N; r++){
String line = br.readLine();
for(int c=0; c<N; c++){
map[r][c] = line.charAt(c);
}
}
//상근이는 사탕의 색이 다른 인접한 두 칸을 고른다
for(int r=0; r<N; r++){
for(int c=0;c<N; c++){
//좌 -우인접
if(c<N-1){
if(map[r][c] !=map[r][c+1]){
//그 다음 고른 칸에 들어있는 사탕을 서로 교환한다.
switchCandy(r,c,r,c+1);
//모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
findMaxCandy();
switchCandy(r,c,r,c+1);
}
}
//상-하인접
if(r<N-1){
if(map[r][c]!= map[r+1][c]){
switchCandy(r,c,r+1,c);
findMaxCandy();
switchCandy(r,c,r+1,c);
}
}
}
}
bw.write(String.valueOf(maxCandy));
bw.flush();
}
public static void switchCandy(int r1, int c1, int r2, int c2){
char tempCandy = map[r2][c2];
map[r2][c2] = map[r1][c1];
map[r1][c1] = tempCandy;
}
public static void findMaxCandy(){
//행
for(int r= 0; r<N; r++){
int candy = map[r][0];
int sameCandyCount = 1;
for(int c=1; c<N;c++){
if(map[r][c] == candy){
++sameCandyCount;
}
else{
candy = map[r][c];
sameCandyCount = 1;
}
maxCandy = Math.max(maxCandy,sameCandyCount);
}
}
//열
for(int c= 0; c<N; c++){
int candy = map[0][c];
int sameCandyCount = 1;
for(int r=1; r<N;r++){
if(map[r][c] == candy){
++sameCandyCount;
}
else{
candy = map[r][c];
sameCandyCount = 1;
}
maxCandy = Math.max(maxCandy,sameCandyCount);
}
}
}
}
3. 시간복잡도 줄이기
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
public static int N;
public static char[][] map;
public static int maxCandy = 0;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
map = new char[N][N];
for(int r = 0; r<N; r++){
String line = br.readLine();
for(int c=0; c<N; c++){
map[r][c] = line.charAt(c);
}
}
findMaxCandy();
//상근이는 사탕의 색이 다른 인접한 두 칸을 고른다
for(int r=0; r<N; r++){
for(int c=0;c<N; c++){
//좌 -우인접
if(c<N-1){
if(map[r][c] !=map[r][c+1]){
//그 다음 고른 칸에 들어있는 사탕을 서로 교환한다.
switchCandy(r,c,r,c+1);
//모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
findMaxCandy(r,c,r,c+1);
switchCandy(r,c,r,c+1);
}
}
//상-하인접
if(r<N-1){
if(map[r][c]!= map[r+1][c]){
switchCandy(r,c,r+1,c);
findMaxCandy(r,c,r+1,c);
switchCandy(r,c,r+1,c);
}
}
}
}
bw.write(String.valueOf(maxCandy));
bw.flush();
}
public static void switchCandy(int r1, int c1, int r2, int c2){
char tempCandy = map[r2][c2];
map[r2][c2] = map[r1][c1];
map[r1][c1] = tempCandy;
}
public static void findMaxCandy(){
//행
for(int r= 0; r<N; r++){
int candy = map[r][0];
int sameCandyCount = 1;
for(int c=1; c<N;c++){
if(map[r][c] == candy){
++sameCandyCount;
}
else{
candy = map[r][c];
sameCandyCount = 1;
}
maxCandy = Math.max(maxCandy,sameCandyCount);
}
}
//열
for(int c= 0; c<N; c++){
int candy = map[0][c];
int sameCandyCount = 1;
for(int r=1; r<N;r++){
if(map[r][c] == candy){
++sameCandyCount;
}
else{
candy = map[r][c];
sameCandyCount = 1;
}
maxCandy = Math.max(maxCandy,sameCandyCount);
}
}
}
public static void findMaxCandy(int r1, int c1, int r2, int c2){
if(r1==r2){
//행
char candy = map[r1][0];
int sameCandyCount = 1;
for(int c=1; c<N;c++){
if(map[r1][c]==candy){
++sameCandyCount;
}
else{
candy = map[r1][c];
sameCandyCount = 0;
}
maxCandy = Math.max(maxCandy,sameCandyCount);
}
for(int c = c1; c<=c2; c++){
candy = map[0][c];
sameCandyCount = 1;
for(int r=1; r<N;r++){
if(map[r][c]==candy){
++sameCandyCount;
}
else{
candy = map[r][c];
sameCandyCount = 0;
}
maxCandy = Math.max(maxCandy,sameCandyCount);
}
}
}
if(c1==c2){
char candy = map[0][c1];
int sameCandyCount = 1;
for(int r=1; r<N;r++){
if(map[r][c1]==candy){
++sameCandyCount;
}
else{
candy = map[r][c1];
sameCandyCount = 0;
}
maxCandy = Math.max(maxCandy,sameCandyCount);
}
for(int r = r1; r<=r2; r++){
candy = map[r][0];
sameCandyCount = 1;
for(int c=1; c<N;c++){
if(map[r][c]==candy){
++sameCandyCount;
}
else{
candy = map[r][c];
sameCandyCount = 1;
}
maxCandy = Math.max(maxCandy,sameCandyCount);
}
}
}
}
}
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| [백준 2579, Java] 계단 오르기 (0) | 2020.11.27 |
|---|---|
| [백준 1905, Java] 01타일 (0) | 2020.11.27 |
| [백준 1476, Java] 날짜 계산 (0) | 2020.11.27 |
| [백준 1107, Java] 리모컨 (0) | 2020.11.27 |
| [백준 9461, Java] 파도반 수열 (0) | 2020.11.27 |
Comments