[코드트리/INTERMEDIATE LOW] 행복한 수열의 개수 (JAVA)

📖 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

💡  풀이 방식

• 완전탐색

. 시간 복잡도 : O(N^2)

 

1. 행복한 행을 구한다.

- 각 행을 돌면서 각 칸의 값이 이전 칸의 값과 같은지 비교한다.

  - 만약 같다면, 연속되는 갯수를 1 증가한다. 만약 연속되는 갯수가 M개 이상이 된다면, 반복문을 탈출한다.

  - 만약 다르다면, 연속되는 갯수는 1로 변경하고, 이전 칸 beforeVal의 값을 현재 칸의 값으로 갱신한다.

for(int i = 0 ; i < N ; i++) {
    int tmp = 1;    // 연속한 수 갯수
    int beforeVal = map[i][0];    // 이전 값

    for(int j = 1 ; j < N ; j++) {
        if(map[i][j] == beforeVal) {
            tmp++;
        }
        else {
            beforeVal = map[i][j];
            tmp = 1;
        }

        // 연속한 수 갯수가 M개 이상이라면, 정답 +1하고 탈출
        if(tmp >= M) {
            cnt++;
            break;
        }
    }
}

 

 

2. 행복한 열을 구한다.

- 행과 열 위치만 바뀌고, 나머지는 행복한 행 구하는 방식과 같다.

for(int i = 0 ; i < N ; i++) {
    int tmp = 1;    // 연속한 수 갯수
    int beforeVal = map[0][i];    // 이전 값

    for(int j = 1 ; j < N ; j++) {
        if(map[j][i] == beforeVal) {
            tmp++;
        }
        else {
            beforeVal = map[j][i];
            tmp = 1;
        }

        // 연속한 수 갯수가 M개 이상이라면, 정답 +1하고 탈출
        if(tmp >= M) {
            cnt++;
            break;
        }
    }
}

 

 

 

💥 유의사항

2번째 for문 안에서 연속되는 수의 갯수가 M개 이상이 되었을 때 바로 반복문을 탈출하게 해야 한다.

안 그러고 끝까지 for문을 돌리는 경우, 여태까지 연속된 수가 M개였다가 그 다음에 다른 수가 나오는 경우, 행복한 수열이 아닌 걸로 판단할 수 있기 때문이다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[][] map;
 
    static int cnt = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        if(N == 1 && M == 1) {
            System.out.println(2);
            return;
        }
 
        map = new int[N][N];
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        // 행복한 행 구하기
        for(int i = 0 ; i < N ; i++) {
            int tmp = 1;    // 연속한 수 갯수
            int beforeVal = map[i][0];    // 이전 값
 
            for(int j = 1 ; j < N ; j++) {
                if(map[i][j] == beforeVal) {
                    tmp++;
                }
                else {
                    beforeVal = map[i][j];
                    tmp = 1;
                }
 
                // 연속한 수 갯수가 M개 이상이라면, 정답 +1하고 탈출
                if(tmp >= M) {
                    cnt++;
                    break;
                }
            }
        }
 
 
        // 행복한 열 구하기
        for(int i = 0 ; i < N ; i++) {
            int tmp = 1;    // 연속한 수 갯수
            int beforeVal = map[0][i];    // 이전 값
 
            for(int j = 1 ; j < N ; j++) {
                if(map[j][i] == beforeVal) {
                    tmp++;
                }
                else {
                    beforeVal = map[j][i];
                    tmp = 1;
                }
 
                // 연속한 수 갯수가 M개 이상이라면, 정답 +1하고 탈출
                if(tmp >= M) {
                    cnt++;
                    break;
                }
            }
        }
 
        System.out.println(cnt);
    }
}

 

 

 

➕ 다른 풀이 방식

- 108ms, 9MB

import java.util.*;
import java.io.*;
 
public class Main {
    static int[][] arr;
    static int n, m;
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        arr = new int[n][n];
        for(int i = 0; i < n ; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        int answer = 0;
 
        for(int i = 0; i < n; i++){
            if(goRight(i)){
                answer++;
            }
 
            if(goDown(i)){
                answer++;
            }
        }
 
        System.out.println(answer);
 
    }
 
    // 행복한 열 찾는 함수
    public static boolean goRight(int r){
        int cnt = 0;
        int target = arr[r][0];
 
        for(int i = 0; i < n; i++){
            if(target == arr[r][i]){
                cnt++;
            }else{
                target = arr[r][i];
                cnt = 1;
            }
 
            if(cnt >= m){
                return true;
            }
        }
 
        return false;
    }
 
    // 행복한 행 찾는 함수
    public static boolean goDown(int r){
        int cnt = 0;
        int target = arr[0][r];
 
        for(int i = 0; i < n; i++){
            if(target == arr[i][r]){
                cnt++;
            }else{
                target = arr[i][r];
                cnt = 1;
            }
 
            if(cnt >= m){
                return true;
            }
        }
 
        return false;
    }
}

 

 

---

💦 어려웠던 점

- 연속한 수 갯수가 M개 이상일 때 정답 갯수에 +1하는 코드의 위치를 제대로 두지 않아 정답이 나오지 않았었다.ㅠ

- 17-19번째 줄에 N과 M이 1일 때를 따로 처리하는 코드를 작성했는데 이 부분은 담에 작성하지 않고 하도록 해야겠당

 

1회독	2회독	3회독	4회독	5회독
V