브루트포스의 4가지 방법 중 첫번째
1) 다 해보는 방법 (주로 반복문을 의미, for문 사용)
2) 순열 사용
3) ⭐재귀 호출 사용⭐ (순열,비트마스크를 몰라도 대신 사용할 수도 있다.)
4) 비트마스크 사용

📌문제 2309번_일곱 난쟁이

https://www.acmicpc.net/problem/2309
시간제한 2초

9명의 난쟁이 중 진짜 난쟁이 7명을 찾아야 한다.
난쟁이의 키의 합은 100

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

✍입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

📄출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

👀예제

예제 입력 1
20 7 23 19 10 15 25 8 13

예제 출력 1
7 8 10 13 19 20 23

❓문제풀이

방법의 개수

1. 9명 중에 7명 찾기
2. 9명 중에 2명 찾기👍
   -> 9C2
   난쟁이 수를 N이라고 했을 때 N(N-1)/2x1 = O(N²)

⏳ 일곱난쟁이를 구하는 시간복잡도

= 방법의 개수(9명 중에 2명 찾기) x 시도하는 복잡도(나머지 7명 난쟁이의 키의 합)

1. 나머지 난쟁이의 키의 합 : O(N)
   ⏳ O(N²) x O(N) = O(N³)

2. 나머지 난쟁이의 키의 합 : O(1)
   "난쟁이의 키는 변하지 않음"을 이용하여 구하기

   일곱난쟁이의 키 = 모든 키의 합 - 가짜 난쟁이 i와 j
   = sum - tall[i]- tall[j]
   = O(1)

   ⏳ O(N²) x O(1) = O(N²)
   

🌴 Code

System.exit(0);
main 메소드 종료 (main 내부 함수에서도 실제호출)

1. O(N³)

import java.util.*;
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = 9;
        int[] a = new int[n];
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        for (int i=0; i<n; i++) {
            for (int j=i+1; j<n; j++) {
                int sum = 0;
                for (int k=0; k<n; k++) {
                    if (i == k || j == k) continue;
                    sum += a[k];
                }
                if (sum == 100) {
                    for (int k=0; k<n; k++) {
                        if (i == k || j == k) continue;
                        System.out.println(a[k]);
                    }
                    System.exit(0);
                }
            }
        }
    }
}

2. O(N²)

import java.util.*;
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = 9;
        int[] a = new int[n];
        int sum = 0;
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
            sum += a[i];
        }
        Arrays.sort(a);
        for (int i=0; i<n; i++) {
            for (int j=i+1; j<n; j++) {
                if (sum - a[i] - a[j] == 100) {
                    for (int k=0; k<n; k++) { // 7명의 진짜 난쟁이 출력
                        if (i == k || j == k) continue; //가짜이면 넘어감
                        System.out.println(a[k]);
                    }
                    System.exit(0);  // main 메소드 종료 (main 내부 함수에서도 실제호출)
                }
            }
        }
    }
}

반복문이 3중으로 중첩되니 O(N^3)으로 생각할 수 있는데 변수 k를 사용하는 반복문이 모든 i, j 마다 호출되지 않고, 딱 1번만 호출되기 때문에 O(N²)

3. 내 코드

package brute_force.n2309_일곱난쟁이;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static int MAX = 9;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        int sum =0;

        for (int i=0;i<MAX;i++){
            list.add(sc.nextInt());
            sum += list.get(i);
        }

        hi:
        for (int i=0;i<MAX-1;i++){
            for (int j=i+1;j<MAX;j++){
                if(sum-100 == list.get(i)+list.get(j)){
                    list.remove(j);
                    list.remove(i);
                    break hi;
                }
            }
        }

        Collections.sort(list);
        for (int k : list) System.out.println(k);

    }
}

새로 알게된 exit 함수 사용해봤음. 좋으다.

package brute_force.n2309_일곱난쟁이;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static int MAX = 9;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        int sum =0;

        for (int i=0;i<MAX;i++){
            list.add(sc.nextInt());
            sum += list.get(i);
        }

        for (int i=0;i<MAX-1;i++){
            for (int j=i+1;j<MAX;j++){
                if(sum-100 == list.get(i)+list.get(j)){
                    list.remove(j);
                    list.remove(i);
                    
                    Collections.sort(list);
        	    for (int k : list) System.out.println(k);

                    System.exit(0)
                }
            }
        }

       
    }
}

---

📌문제 3085번_사탕게임

https://www.acmicpc.net/problem/3085
시간 제한 1초

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

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

✍입력

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

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

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

📄출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

👀예제

예제 입력 1
5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

예제 출력 1
4

최대의 인접한 사탕 갯수는 4개로 아래의 2열에 C가 4개로 인접한걸 볼 수 있다.

YCPZY
YCZZP
CCPPP
YCYZC
CPPZZ

❓문제풀이

1. 인접한 두칸을 고르고
2. 사탕을 교환
3. 같은 색으로 이루어져 있는 가장 긴 연속 부분 행 또는 열을 고르기

이 방법을 하는게 몇 가지 있는지?

1. 인접한 두칸을 고른다는 건

한 칸을 고른 후 주변 네 칸 중에 하나를 고르는 것이다 : N²x4 = O(N²)
(실제로는 오른쪽과 아래 중에서 고르면 됨. 왼쪽 위에서부터 차례대로 진행되기 때문에)

2.교환하고 같은색으로 이루어져 있지 않으면 다시 되돌려 주어야함.

3. 같은 색으로 이루어져 있는 가장 긴 연속 부분을 고르기

3-1. 알 수 없으므로 MxN 전체 테이블 중에 어디가 가장 긴지 일일이 검사 해야 한다. : O(N²)
3-2. 3-1 방법에서 시간을 단축 할 수 있는데, 이는 연속된 부분이 있으면 그 행과 열만 검사 하는 것이다. : O(N)

💡 시간을 줄이는 방법은 중복된 연산을 여러번 하고 있는지 봐야한다.

⏳ 총 시간 복잡도

3-1이용. O(N²) x O(N²) = O(N⁴)
3-2이용. O(N²) x O(N) = O(N³)

N≤50, 50⁴ = 625만 < 1억 이므로 만족

🌴 Code

1,3,2,4 순으로 빠르다

1. 시간복잡도 O(N^4)

package brute_force.n3085_사탕게임;

import java.util.*;

//시간복잡도 O(N^4)
public class Main {

    //가장 긴 연속부분을 찾는 메소드 O(N^2)
    static int check(char[][] a) {
        int n = a.length;
        int ans = 1;

        for (int i=0; i<n; i++) {

            int cnt = 1; //인접한 사탕의 개수
            for (int j=1; j<n; j++) { //열
                if (a[i][j] == a[i][j-1]) { //i행에서 1열씩 증가하며 인접한 사탕 있는지 검사
                    cnt += 1;
                } else {
                    cnt = 1;
                }
                if (ans < cnt) ans = cnt; //최대의 인접함 찾기
            }

            cnt = 1;
            for (int j=1; j<n; j++) { //행
                if (a[j][i] == a[j-1][i]) { //i열에서 1행씩 증가하며 인접한 사탕 있는지 검사
                    cnt += 1;
                } else {
                    cnt = 1;
                }
                if (ans < cnt) ans = cnt;
            }

        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[][] a = new char[n][n];
        for (int i=0; i<n; i++) {
            a[i] = sc.next().toCharArray();
        }

        int ans = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) { //i행에서 1열씩 증가
                if (j+1 < n) { //오른쪽
                    char t = a[i][j]; a[i][j] = a[i][j+1]; a[i][j+1] = t; //교환
                    int temp = check(a); //가장 긴 사탕 찾기
                   if (ans < temp) {
                       ans = temp;
//                       for (char [] k: a){
//                           for (char l :k) System.out.print(l);
//                           System.out.println();
//                       }
//                       System.out.println(ans);
                   }
                    t = a[i][j]; a[i][j] = a[i][j+1]; a[i][j+1] = t; //모든 경우를 검사해야 하기 때문에 교환한것 다시 원래대로
                }
                if (i+1 < n) { //아래 
                    char t = a[i][j]; a[i][j] = a[i+1][j]; a[i+1][j] = t;
                    int temp = check(a);
                    if (ans < temp) {
                        ans = temp;
//                        for (char [] k: a){
//                            for (char l :k) System.out.print(l);
//                            System.out.println();
//                        }
//                       System.out.println(ans);
                    }
                    t = a[i][j]; a[i][j] = a[i+1][j]; a[i+1][j] = t;
                }
            }
        }
        
        System.out.println("ans : "+ans);
    }
}

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

package brute_force.n3085_사탕게임;

import java.util.*;

//시간복잡도 O(N^3)
public class Main2 {

    //가장 긴 연속부분을 찾는 메소드 O(N)
    //연속된 부분이 나타난 행과 열만 검사
    static int check(char[][] a, int start_row, int end_row, int start_col, int end_col) {
        int n = a.length;
        int ans = 1;
        
        //가로줄 연속부분 
        for (int i=start_row; i<=end_row; i++) {
            int cnt = 1;
            for (int j=1; j<n; j++) {
                if (a[i][j] == a[i][j-1]) {
                    cnt += 1;
                } else {
                    cnt = 1;
                }
                if (ans < cnt) ans = cnt;
            }
        }
        //세로줄 연속부분 
        for (int i=start_col; i<=end_col; i++) {
            int cnt = 1;
            for (int j=1; j<n; j++) {
                if (a[j][i] == a[j-1][i]) {
                    cnt += 1;
                } else {
                    cnt = 1;
                }
                if (ans < cnt) ans = cnt;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[][] a = new char[n][n];
        for (int i=0; i<n; i++) {
            a[i] = sc.next().toCharArray();
        }
        int ans = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) { //i행을 기준으로 한열씩 이동해서 검사
                if (j+1 < n) {//오른쪽
                    char t = a[i][j]; a[i][j] = a[i][j+1]; a[i][j+1] = t; //교환
                    int temp = check(a, i, i, j, j+1);
                    if (ans < temp) ans = temp;
                    t = a[i][j]; a[i][j] = a[i][j+1]; a[i][j+1] = t;
                }
                if (i+1 < n) {//아래
                    char t = a[i][j]; a[i][j] = a[i+1][j]; a[i+1][j] = t;
                    int temp = check(a, i, i+1, j, j);
                    if (ans < temp) ans = temp;
                    t = a[i][j]; a[i][j] = a[i+1][j]; a[i+1][j] = t;
                }
            }
        }
        System.out.println(ans);
    }
}

3. 안보고 코드 짜보기 O(N^4)

package brute_force.n3085_사탕게임;

import java.util.Scanner;

public class Prac1 {
    //연결된 사탕갯수 검사
    public static int max (char [][] arr){
        int cnt = 0;
        int ans = 1;
        for (int i =0;i<arr.length;i++){
            //가로 줄 검사
            cnt = 1; // ❗ 
            for (int j=1;j<arr.length;j++){
                if(arr[i][j-1] == arr[i][j]) cnt++;
                else cnt =1;

                if(ans<cnt) ans = cnt;
            }

            //세로 줄 검사
            cnt = 1; // ❗
            for (int j=1;j<arr.length;j++){
                if(arr[j-1][i]==arr[j][i]) cnt++;
                else cnt = 1;

                if(ans<cnt) ans = cnt;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char [][] candy = new char[n][n];

        for (int i =0; i<n; i++){
            candy[i] = sc.next().toCharArray(); //입력 받은 문자열을 char배열형태로 바꿈
        }

        int m = 1;
        for(int i=0;i<n;i++){

            for (int j=1;j<n;j++){
                //오른쪽에 있는 사탕이랑 교환
                char t = candy[i][j-1];
                candy[i][j-1] = candy[i][j];
                candy[i][j] = t;

                //가장 긴지 검사..
                if(m<max(candy)) {
                    m = max(candy);
//                       for (char [] k: candy){
//                           for (char l :k) System.out.print(l);
//                           System.out.println();
//                       }
//                       System.out.println("right : "+m);
                }

                t = candy[i][j-1];
                candy[i][j-1] = candy[i][j];
                candy[i][j] = t;

            }

            for (int j=1;j<n;j++){
                //아래에 있는 사탕이랑 교환
                char t = candy[j-1][i];
                candy[j-1][i] = candy[j][i];
                candy[j][i] = t;

                if(m<max(candy)) {
                    m = max(candy);
//                    for (char [] k: candy){
//                        for (char l :k) System.out.print(l);
//                        System.out.println();
//                    }
//                    System.out.println("down: "+m);
                }

                t = candy[j-1][i];
                candy[j-1][i] = candy[j][i];
                candy[j][i] = t;
            }
        }
        System.out.println(m);


    }
}

가장 긴 사탕을 찾는 max 메소드에서 가로줄 세로줄 마다 cnt 초기화를 해주어야하는데 안해줘서 다른곳에서 해맷음 ㅜ

4. 안보고 코드 짜보기 O(N^3)

2번코드의 "교환한 사탕의 행과 열만 비교함"을 이용했고
2번에서는 하나의 메소드를 이용했지만 여기서는 메소드를 두개로 만듦.

package brute_force.n3085_사탕게임;

import java.util.Scanner;

public class Prac2 {
    public static int max_2column(char[][] candy,int row,int column){
        int ans = 0;

            //가로줄 1개 검사
        int cnt = 1;
        for (int i=1;i<candy.length;i++) {
            if (candy[row][i - 1] == candy[row][i]) cnt++;
            else cnt = 1;
            if (ans < cnt) ans = cnt;
        }
            //세로줄 2개 검사
        cnt = 1;
        for (int i=1;i<candy.length;i++) {
            if (candy[i - 1][column - 1] == candy[i][column - 1]) cnt++;
            else cnt = 1;
            if (ans < cnt) ans = cnt;
        }
        cnt=1;
        for (int i=1;i<candy.length;i++){
            if(candy[i-1][column]==candy[i][column]) cnt++;
            else cnt = 1;
            if(ans < cnt) ans = cnt;
        }

        return ans;
    }

    public static int max_2row(char[][] candy,int row,int column){
        int ans = 0;
            //세로줄 1개 검사
        int cnt = 1;
        for (int i=1;i<candy.length;i++) {
            if (candy[i - 1][column] == candy[i][column]) cnt++;
            else cnt = 1;
            if (ans < cnt) ans = cnt;
        }
            //가로줄 2개 검사
        cnt = 1;
        for (int i=1;i<candy.length;i++) {
            if (candy[row - 1][i - 1] == candy[row - 1][i]) cnt++;
            else cnt = 1;
            if (ans < cnt) ans = cnt;
        }
        cnt=1;
        for (int i=1;i<candy.length;i++){
            if(candy[row][i-1]==candy[row][i]) cnt++;
            else cnt = 1;
            if(ans < cnt) ans = cnt;
        }
        return ans;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char [][] candy = new char[n][n];
        for (int i=0;i<n;i++){
            candy[i] =  sc.next().toCharArray();
        }

        int m = 1;
        for(int i=0;i<n;i++){
            for (int j=1;j<n;j++){ //오른쪽
                char t = candy[i][j-1];
                candy[i][j-1] = candy[i][j];
                candy[i][j] = t;
                int tmp = max_2column(candy,i,j);
                if(m<tmp) m = tmp;

                t = candy[i][j-1];
                candy[i][j-1] = candy[i][j];
                candy[i][j] = t;

            }
            for (int j=1;j<n;j++){ //아래
                char t = candy[j-1][i];
                candy[j-1][i] = candy[j][i];
                candy[j][i] = t;
                int tmp = max_2row(candy,j,i);
                if(m<tmp) m = tmp;

                t = candy[j-1][i];
                candy[j-1][i] = candy[j][i];
                candy[j][i] = t;
            }
        }

        System.out.println(m);

    }
}