[BOJ 3085 - Java] 사탕게임 - 구현문제

2024. 10. 15. 17:26·문제 풀이/백준 문제풀이
728x90
반응형
SMALL

문제 정보

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

3
CCP
CCP
PPC

--> 3

4
PPPP
CYZY
CCPY
PPCC

--> 4

슈도 코드

  1. 임포트
  2. 메인 메서드 생성
  3. 입력에 필요한 변수
    1. 순환 횟수 N
    2. 입력받을 배열 char[][] map
    3. 정답 입력할 ans 변수
  4. static 메서드
    1. 전체 행중 가장 높은 점수를 갖는 행
    2. 전체 열중 가장 높은 점수를 갖는 열
    3. 스왑 메서드
  5. 이중 반복문을 진입하여 각 위치에서 조건문 수행
    1. if(해당 위치에서 x+1한 값이 map의 길이보다 작고, x+1값과 x값이 같지 않을때) → 위치 스왑 → ans에 Math.max(ans, Math.max(findMaxRow(),findMaxCol()))의 값을 담음
    2. y값도 위와 동일한 로직으로 수행
  6. ans출력

주요 규칙

  • 색이 칠해진 화살표는 두번 수행되는 구간이다.
  • 그러므로 x값과 y값이 증감되는 구간만 교환해서 비교하면 시간 복잡도를 줄일 수 있다.

시간 복잡도

O(N^4)

import java.util.Scanner;

public class 사탕게임_3085 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[][] map = new char[n][n];
        for (int i = 0; i < n; i++) {
            map[i] = sc.next().toCharArray();
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {  
            for (int j = 0; j < n; j++) {  //N^2
                   if (j + 1 < n && map[i][j] != map[i][j + 1]) {
                    swap(map, i, j, i, j + 1);
                    ans = Math.max(ans, Math.max(findMaxCol(map), findMaxRow(map)));  //2N^2
                    swap(map, i, j, i, j + 1);
                }
                if (i + 1 < n && map[i][j] != map[i + 1][j]) {
                    swap(map, i, j, i + 1, j);
                    ans = Math.max(ans, Math.max(findMaxCol(map), findMaxRow(map)));
                    swap(map, i, j, i + 1, j);
                }
            }
            if(ans==n) break;
        }
        System.out.println(ans);
    }

    public static int findMaxRow(char[][] map) { //N^2
        int N = map.length;
        int maxRow = 0;
        for (int r = 0; r < N; r++) {
            int len = 1;
            for (int c = 1; c < N; c++) {
                if (map[r][c] == map[r][c - 1]) {
                    len++;
                } else {
                    maxRow = Math.max(maxRow, len);
                    len = 1;
                }
            }
            maxRow = Math.max(maxRow, len); //len값이 초기화되기 전에 갱신시켜준다.
        }
        return maxRow;
    }
    public static int findMaxCol(char[][] map) { //N^2
        int N = map.length;
        int maxrow = 0;
        for (int c = 0; c < N; c++) {
            int len = 1;
            for (int r = 1; r < N; r++) {
                if (map[r][c] == map[r-1][c]) {
                    len++;
                } else {
                    maxrow = Math.max(maxrow, len);
                    len = 1;
                }
            }
            maxrow = Math.max(maxrow, len); //len값이 초기화되기 전에 갱신시켜준다.
        }
        return maxrow;
    }
    public static void swap(char[][] map, int r1, int c1, int r2, int c2) {
        char tmp = map[r1][c1];
        map[r1][c1] = map[r2][c2];
        map[r2][c2] = tmp;
    }
}
728x90
반응형
SMALL

'문제 풀이 > 백준 문제풀이' 카테고리의 다른 글

[BOJ 2817 - Java] 알프스식 투표 - 구현문제  (1) 2024.10.18
[BOJ 3085 - Java] 사탕게임 - 구현문제  (1) 2024.10.15
알고리즘 - 위상정렬  (0) 2024.08.09
[BOJ14501 - Java] 퇴사문제 DP로 풀이하기  (0) 2024.07.28
[백준1157- Java] 구현 - 단어 공부  (0) 2024.04.23
'문제 풀이/백준 문제풀이' 카테고리의 다른 글
  • [BOJ 2817 - Java] 알프스식 투표 - 구현문제
  • [BOJ 3085 - Java] 사탕게임 - 구현문제
  • 알고리즘 - 위상정렬
  • [BOJ14501 - Java] 퇴사문제 DP로 풀이하기
공부하고 기억하는 공간
공부하고 기억하는 공간
IT 비전공자로 시작하여 훌륭한 개발자가 되기 위해 공부하고 있는 공간입니다. 틀린 내용이나 부족한 부분이 있으면 댓글로 알려주세요 바로 수정하겠습니다.
    250x250
  • 공부하고 기억하는 공간
    IT - railroad
    공부하고 기억하는 공간
  • 전체
    오늘
    어제
    • 분류 전체보기 (325)
      • 면접 준비 (22)
        • OS (6)
        • Spring Security (0)
        • Java (3)
        • DB (11)
        • Network (3)
      • ElasticSearch (2)
      • Kafka (4)
      • Spring (22)
        • Spring Cloud (7)
        • Security6 (5)
        • JPA (12)
        • 프로젝트 리팩토링 회고록 (4)
        • Logging (8)
        • Batch (2)
      • Redis (17)
        • Redis 개념 (8)
        • Redis 채팅 (5)
        • Redis 읽기쓰기 전략 (1)
      • AWS (11)
      • 리눅스 (29)
        • 리눅스 마스터 2급 (5)
        • 네트워크(기초) (7)
        • 리눅스의 이해 (6)
        • 리눅스의 설치 (2)
        • 리눅스 운영 및 관리 (6)
      • JAVA-기초 (16)
        • JAVA기본 (11)
        • Design Pattern (5)
      • JSP (27)
        • JSP 기본 개념 (10)
        • JSP (1)
      • SQL (1)
      • TIL (36)
      • 문제 풀이 (2)
        • Programmers (9)
        • 백준 문제풀이 (28)
      • JavaScript (10)
      • HTML (17)
      • Ngrinder (1)
        • Ngrinder 문서 정리 (1)
  • 블로그 메뉴

    • 링크

    • 공지사항

    • 인기 글

    • 태그

      자바 면접질문
      redis 채팅
      Spring
      백준
      springsecurity
      jsp request
      레디스
      jsp기초
      자바기초
      spring redis
      리눅스마스터2급
      스프링프레임워크
      자바 반복문
      JS
      Spring Data Redis
      자바스크립트
      리눅스마스터2급정리
      CSS
      JSP
      자바
      Til
      자바 알고리즘
      리눅스
      프로그래머스
      자바 면접
      JavaScript
      Springframework
      java
      HTML
      redis
    • 최근 댓글

    • 최근 글

    • hELLO· Designed By정상우.v4.10.3
    공부하고 기억하는 공간
    [BOJ 3085 - Java] 사탕게임 - 구현문제
    상단으로

    티스토리툴바