[CodeTree] 아름다운 수, 양수 직사각형의 최대 크기, 알파벳과 사칙연산

BackTracking: 아름다운 수

 

문제설명

n자리 아름다운 수가 몇 개 있는지 출력한다.

여기서 "아름다운 수"란 각 숫자마다 반복되는 숫자가 일치하는 것을 말한다.
만약 1이 나오면 1이 1번 반복되어야 하고, 3이 나오면 3이 3번 나와야 한다. 이것을 모두 만족 하는 것이 아름다운 수이다.

 

해결방법

1. n자리 숫자를 중복 순열로 만들어준다. (완전탐색을 하는 것)

2. 순열로 만든 숫자를 모두 검사해서 "아름다운 수" 인지 아닌지를 판별한다.

3. 만든 순열이 아름다운 수인지 만족하는 것만 개수를 세서 출력한다.

 

 

중복순열을 만든 것까지 코드를 짰는데 아름다운 수를 판별하는 방법이 좀 이해가 안갔다.

판별하는 방법은 시작점(시작하는 위치: i)부터 그 시작점이 가리키는 값(arr[i])까지 같은 숫자를 반복하면 되었다.

 

아래가 주요 로직이다. i는 시작하는 위치, arr[i]는 시작점, arr[j]는 반복되어서 같아야 하는 값을 의미한다.
여기서 i+=arr[i]을 해서 건너띄어주는 의미는 다음 아름다운 수를 찾아야 하기 때문이다.

for(int i=0; i<n; i+=arr[i]){
	for(int j=i; j<i+arr[i]; j++)
    	{
        	if(arr[i]!=arr[j]) return false;
        }
}

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static StringTokenizer tokens;
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static int n,res;
    static int arr[];
    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(input.readLine());
        arr = new int [n];

        permu(0);
        System.out.println(res);

    }

    static boolean check() {
        for(int i=0; i<n; i+=arr[i]) {

            if(i+arr[i]-1 >=n) { //범위를 벗어남
                return false;
            }
            for(int j=i; j<i+arr[i]; j++) {
                if(arr[i] != arr[j]) return false;
            }
        }
        return true;
    }
    static void permu(int cnt) {
        if(cnt == n) {
            System.out.println(Arrays.toString(arr));
            //아름다운 수인지 아닌지 확인
            if(check()) res++;
            return;
        }

        for(int i=1; i<=4; i++) {
            arr[cnt] = i;
            permu(cnt+1);
        }
    }
}

 

 

Simulation: 양수 직사각형

문제설명

n*m 크기의 이차원 영역의 각 위치에 정수 값이 하나씩 적혀있다.

이 영역 안에서 가능한 양수 직사각형 중 최대 크기를 구하려고 한다.

양수 직사각형은 직사각형 내에 있는 숫자들이 전부 양수인 직사각형을 의미한다. (0보다 커야한다!) 

이때, 최대 크기의 양수 직사각형을 찾아야 한다.

 

 

해결방법

방법은 역시 완전 탐색!

1. 직사각형의 크기를 구한다.

2. 그 크기 중에 모든 수가 양수이면 OK, 음수가 포함되어 있다면 저장하지 않는다.

 

나는 직사각형의 크기를 구하는 과정에서 1*1, 1*2 이거를 다 정해서 해야 하나.. 고민했는데
크기를 정할 때 직사각형은 왼쪽 위의 점, 오른 쪽 아래 점을 정해서 그 크기에 대해서 검사만 하면 되었다.

 

 

이런식으로 왼쪽 끝점을 정하면 오른쪽 끝점은 왼쪽 끝점보다는 크면서 범위에 벗어나지 않도록 반복문을 돌리면 된다.

        //왼쪽 끝점
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                //오른쪽 끝점
                for(int a=i; a<n; a++) {
                    for(int b=j; b<m; b++) {

 

그리고 , 아래처럼 왼쪽, 오른쪽 정한 점에 대해서 반복문을 돌리면서 양수만 있도록 범위를 정해주면 된다.

                        for(int r1=i; r1<=a; r1++) {
                            if(!flag) break;
                            for(int c1=j; c1<=b; c1++) {
                                if (map[r1][c1] <= 0)  {
                                    flag = false;
                                    break;
                                }
                            }
                        }

 

전체코드

package codeTree;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 양수직사각형의최대크기 {
    static StringTokenizer tokens;
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static int n,m;
    static int maxVal = Integer.MIN_VALUE;
    static int map[][];

    public static void main(String[] args) throws IOException {
        tokens = new StringTokenizer(input.readLine());
        n = Integer.parseInt(tokens.nextToken());
        m = Integer.parseInt(tokens.nextToken());
        map = new int [n][m];
        for(int i =0 ; i<n; i++) {
            tokens = new StringTokenizer(input.readLine());
            for(int j=0; j<m; j++) {
                map[i][j] = Integer.parseInt(tokens.nextToken());
            }
        }

        rectangle();
        System.out.println(maxVal);

    }
    static void rectangle() {
        //왼쪽 끝점
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                //오른쪽 끝점
                for(int a=i; a<n; a++) {
                    for(int b=j; b<m; b++) {

                        boolean flag = true;
                        for(int r1=i; r1<=a; r1++) {
                            if(!flag) break;
                            for(int c1=j; c1<=b; c1++) {
                                if (map[r1][c1] <= 0)  {
                                    flag = false;
                                    break;
                                }
                            }
                        }
                        int val=0;
                        if(flag) {
                            val= (a-i+1)*(b-j+1);
                        }
                        maxVal = Math.max(maxVal, val);
                    }
                }
            }
        }
    }

}

 

Simulation: 알파벳과 사칙연산

문제설명

a에서 f까지 알파벳과 +,-,* 기호만으로 문장이 주어진다.

이때 알파벳에 1~4 숫자를 넣어서 연산을 모두 한 후 최대값이 나와야 한다.

 

 

해결방법

1. 알파벳 배열을 만든다. a~f는 0~5에 매핑이 되는 수이다. 

2. 알파벳에 들어갈 수를 중복 순열로 고른다.

3. 중복 순열로 만든 수를 원래 연산에 넣어서 계산한다.

 

여기서 주의할 점은 a가 두번 나오면 같은 숫자가 나오는 것이다.. 나는 처음에 매핑을 하지 않고 각 다른 수로 취급을 하는데 같은 알파벳은 같은 숫자로 취급을 해야 한다! 

그래서 아래처럼 함수를 만들어서 a에 해당하는 index를 return 해주는 걸 만들었다.

    static int alpa(char c) {
        if(c == 'a') return 0;
        else if (c=='b') {
            return 1;
        } else if (c=='c') {
            return 2;
        } else if (c=='d') {
            return 3;
        } else if (c=='e') {
            return 4;
        } else {
            return 5;
        }
    }

 

근데 생각을 해보니 .. 배열에 넣어서 인덱스를 찾는 것보다 그냥

1. Map으로 저장해두면 더 편하다는 생각이 들기도 하고,

2. 아니면 ASCII 코드를 이용해서 인덱스에서 바로 찾으면 되는게 편하다는 생각이 들었다.

 

그래서 ASCll코드를 이용해서 최적화를 해주었다!

 

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static int[] res = new int[6];  // 각 알파벳에 할당할 값
    static int[] arr = {1, 2, 3, 4};  // 가능한 값 (1~4)
    static long maxVal = Long.MIN_VALUE;
    static char[] expression;  // 입력식을 저장할 char 배열
    static int n;  // 식에 포함된 알파벳 개수

    public static void main(String[] args) throws IOException {
        expression = input.readLine().toCharArray();  // 입력을 char 배열로 변환
        n = (expression.length + 1) / 2;  // 알파벳의 개수 계산 (연산자는 홀수 위치에 있음)

        // 순열 생성 및 최대값 계산
        permuteAndCalculate(0);
        System.out.println(maxVal);
    }

    // 순열을 사용하여 각 알파벳에 1~4 값을 할당하는 함수
    static void permuteAndCalculate(int cnt) {
        if (cnt == 6) {  // 6개의 알파벳에 모두 값을 할당한 경우
            long c = calc();  // 계산 후 최대값 갱신
            maxVal = Math.max(maxVal, c);
            return;
        }

        // 가능한 값(1~4) 중에서 선택하여 알파벳에 할당
        for (int i = 0; i < 4; i++) {
            res[cnt] = arr[i];  // 현재 알파벳에 값 할당
            permuteAndCalculate(cnt + 1);  // 다음 알파벳 처리
        }
    }

    // 현재 알파벳 값으로 식을 계산하는 함수
    static long calc() {
        int sum = res[expression[0] - 'a'];  // 첫 번째 알파벳 값으로 초기화
        for (int i = 1; i < expression.length; i += 2) {  // 연산자를 순차적으로 처리
            char operator = expression[i];  // 연산자
            int nextValue = res[expression[i + 1] - 'a'];  // 다음 알파벳 값

            // 연산자에 따른 계산
            if (operator == '-') {
                sum -= nextValue;
            } else if (operator == '+') {
                sum += nextValue;
            } else if (operator == '*') {
                sum *= nextValue;
            }
        }
        return sum;
    }
}