soo 문제집 완전탐색 easy 문제 남은 10문제중 7문제를 풀었고, 그중 힌트를 참고한 문제 및 정리하기 위한 4개의 문제를 재풀이해서 학습 및 체득하려는 목적으로 작성했습니다.

문제번호	제목	난이도
3085번	사탕 게임	실버 2
16945번	매직 스퀘어로 변경하기	실버 2
5883번	아이폰 9S	실버 4
5671번	호텔 방 번호	실버 5

3085번 사탕게임

해결 코드:

import java.io.*;
import java.util.*;


public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        char[][] arr = new char[n][n];
        for (int i = 0; i < n; i++) {
            String input = br.readLine();
            for (int j = 0; j < n; j++) {
                arr[i][j] = input.charAt(j);
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n-1; j++) {
                char tmp = arr[i][j];
                arr[i][j] = arr[i][j+1];
                arr[i][j+1] = tmp;

                ans = findAns(n, arr, ans);

                tmp = arr[i][j];
                arr[i][j] = arr[i][j+1];
                arr[i][j+1] = tmp;
            }
        }


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n-1; j++) {
                char tmp = arr[j][i];
                arr[j][i] = arr[j+1][i];
                arr[j+1][i] = tmp;

                ans = findAns(n,arr,ans);

                tmp = arr[j][i];
                arr[j][i] = arr[j+1][i];
                arr[j+1][i] = tmp;

            }
        }

        bw.write(ans+"");

        br.close();
        bw.close();
    }

    private static int findAns(int n, char[][] arr, int ans) {
        for (int i = 0; i < n; i++) {
            int count = 1;
            for (int j = 0; j < n - 1; j++) {
                if(arr[i][j] == arr[i][j+1]){
                    count++;
                }else{
                    count = 1;
                }
                ans = Math.max(ans, count);
            }
        }

        for (int i = 0; i < n; i++) {
            int count = 1;
            for (int j = 0; j < n - 1; j++) {
                if(arr[j][i] == arr[j+1][i]){
                    count++;
                }else{
                    count = 1;
                }
                ans = Math.max(ans, count);
            }
        }
        return ans;
    }
}

고민과 해결의 시간:

1. 입력값의 크기가 매우 작아서 완전탐색으로 풀 수 있는 문제다.
2. 위치를 한번씩 바꾸고 모두 탐색해서 가장 큰 연속된 사탕의 색이 있는지 체크한다. 그중 가장 큰 값을 정답으로 설정한다
3. 이때 상하좌우 중 오른쪽과 아래쪽만 살펴보면 된다. 왼쪽과 위쪽은 중복이기 때문에, 두 방향만 살펴보면 해결된다
4. 주의할점은 원본 값에서 변경하고 나서 확인 후에 다시 원상태로 돌려놔야한다
5. 살펴볼때는 두가지 경우를 살펴본다. 가로 방향으로 모든 배열을 탐색하고 세로 방향으로 모든 방향을 탐색한다
6. 이때 일단 탐색하는 그 지점의 색은 무조건 골라지므로 count는 1로 초기화하고 만약 그 옆의 값과 같다면 count를 증가시킨다
7. 각 탐색마다 ans에 count와 비교해서 더 큰 값을 넣어준다
8. 5~7번 과정을 우측으로 살펴보는 경우와 아래쪽으로 바라보는 경우 모두 탐색한 뒤 ans를 리턴해준다
9. 이렇게 완성한 ans를 출력하면 정답이 된다.

문제 링크:

3085번 - 사탕게임

16945번 매직스퀘어로 변경하기

해결 코드:

import java.io.*;
import java.util.*;



public class Main {

    static int[][] arr = new int[3][3];
    static boolean[] visited = new boolean[10];
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < 3; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }


        backtracking(0,0);
        bw.write(min+"");

        br.close();
        bw.close();
    }

    private static void backtracking(int depth, int sum) {
        if(depth == 9 && checked()){
            min = Math.min(min, sum);
            return;
        }

        int y = depth / 3;
        int x = depth % 3;

        for (int i = 1; i <= 9; i++) {
            if(!visited[i]){
                visited[i] = true;
                int tmp = arr[y][x];
                arr[y][x] = i;
                backtracking(depth+1, sum + Math.abs(tmp - i));
                visited[i] = false;
                arr[y][x] = tmp;
            }
        }

    }

    private static boolean checked() {

        for (int i = 0; i < 3; i++) {
            int rowSum = 0;
            int colSum = 0;
            for (int j = 0; j < 3; j++) {
                rowSum += arr[i][j];
                colSum += arr[j][i];
            }
            if(rowSum != 15 || colSum != 15){
                return false;
            }
        }

        int cross1 = arr[0][0] + arr[1][1] + arr[2][2];
        int cross2 = arr[0][2] + arr[1][1] + arr[2][0];
        if(cross1 != 15 || cross2 != 15){
            return false;
        }

        return true;
    }
}

고민과 해결의 시간:

1. 3X3으로 고정되어 있다. 완전 탐색을 활용할 수 있는 문제다.
2. 하지만 이 문제는 마치 백준의 백트래킹을 활용하는 스도쿠 문제와 같다.
3. 일단 매직스퀘어가 되기 위해서는 각 행,열,대각선을 더했을 때 15가 되어야한다
4. 따라서 각 값을 1~9까지 변경하면서 15가 되는 경우를 모두 찾아야 한다
5. 나올 수 있는 연쇄의 가지가 너무 많은 문제다. 따라서 백트래킹을 이용하였다
   백트래킹

• 함수식: backtracking(깊이, 변경된 값들의 합)
• base condition: depth == 9 && 매직스퀘어인지 체크해주는 로직
• 재귀식: backtracking(depth+1, sum + Math.abs(tmp - i))

6. 위와 같이 백트래킹을 설계하였다
7. 1~9까지 넣으면서 3 by 3 배열을 모두 탐색하는 반복문을 도는 식을 만들어주면된다
8. 이때 식을 간소화하기 위해 y는 depth / 3, x는 depth %3을 이용하였다.
9. 이렇게 하면 3 by 3의 각 y좌표와 x좌표를 depth를 이용해서 사용할 수 있다
10. 방문 배열도 이용해야한다. 1~9까지의 수를 이용하기 위해서이다
11. 백트래킹 후 base condition에서는 depth==9인 경우와 매직스퀘어 조건을 만족하는지를 체크해줘야한다
12. checked()함수에서는 각 행, 열, 대각선이 15가 아닌 경우 false를 리턴하고 모두 통과하는 경우 true를 리턴하도록 설계하였다.
13. 위 조건을 통과하면 min에 sum과 비교해서 더 작은 값을 넣어주고 min을 출력하면 정답이 된다.

문제 링크:

매직 스퀘어로 변경하기 - 16945번

5883번 아이폰9S

import java.io.*;
import java.util.*;



public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            set.add(arr[i]);
        }

        int ans = 1;
        for(Integer a : set){
            int now = arr[0];
            int count = 1;
            for (int i = 1; i < n; i++) {
                if(arr[i] == a){
                    continue;
                }

                if(arr[i] != now){
                    count = 1;
                }else{
                    count++;
                    ans = Math.max(ans, count);
                }
                now = arr[i];
            }
        }

        bw.write(ans+"");


        br.close();
        bw.close();
    }
}

고민과 해결의 시간:

1. 실제 배열은 그대로 나두고 숫자를 하나씩 빼보면서 탐색하는 문제이다
2. 이 문제를 해결하는데 사용한 방법은 Set 자료구조이다.
3. 각 값들을 중복없이 Set에 저장해서 그 값들을 하나씩 탐색한다
4. 이때 count를 1로 설정하고 맨 처음 값을 now로 설정한다
5. 이어서 1번째부터 n전까지 탐색을 하는데 만약 현재 arr[i]의 값이 a인 경우는 continue해서 넘겨준다
6. 만약 arr[i]가 now랑 같지 않으면 count를 1로 초기화하고 아니면 count++해준다
7. 이어서 ans에 count와 비교해서 더 큰 값을 넣어준다
8. 각 순회가 끝나기전에 now를 현재 arr[i]로 갱신해서 탐색을 계속한다
9. 완성한 ans를 출력하면 정답이 된다.

문제 링크:

5883번 - 아이폰9S

5671번 호텔 방 번호

import java.io.*;
import java.util.*;



public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String input = "";
        while((input = br.readLine()) != null){
            String[] tmp = input.split(" ");
            int n = Integer.parseInt(tmp[0]);
            int m = Integer.parseInt(tmp[1]);
            int count = 0;
            for (int i = n; i <= m; i++) {
                String s = String.valueOf(i);
                Set<Character> set = new HashSet<>();
                for (int j = 0; j < s.length(); j++) {
                    set.add(s.charAt(j));
                }
                if(set.size() == s.length()){
                    count++;
                }
            }
            bw.write(count + "\n");

        }


        br.close();
        bw.close();
    }
}

고민과 해결의 시간:

1. 입력부분은 생략하고, n부터 m까지 탐색할 때 각 숫자를 문자로 바꾼다
2. 그 문자의 길이만큼 탐색을 하는데, 이때 Set을 활용한다
3. 만약 Set의 크기와 문자열의 길이가 같다면 중복되는 숫자가 하나도 없다는 것을 의미한다
4. 이를 활용해서 각 문자열의 길이만큼 탐색한 뒤 만약 그 문자열의 길이와 Set의 크기가 같다면 count++를 해준다
5. 각 테스트케이스마다 완성된 count를 출력하면 정답이 된다

문제 링크:

5671번 - 호텔 방 번호