[코딩테스트] [11068] 회문인 수 & [3085] 사탕게임

회문인 수

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

256 MB

4766

2414

2001

54.331%

문제

어떤 수를 왼쪽부터 읽어도, 오른쪽부터 읽어도 같을 때 이 수를 회문인 수라고 한다. 예를 들어, 747은 회문인 수이다. 255도 회문인 수인데, 16진수로 표현하면 FF이기 때문이다. 양의 정수를 입력받았을 때, 이 수가 어떤 B진법 (2 ≤ B ≤ 64)으로 표현하면 회문이 되는 경우가 있는지 알려주는 프로그램을 작성하시오. B진법이란, 한 자리에서 수를 표현할 때 쓸 수 있는 수의 가짓수가 B라는 뜻이다. 예를 들어, 십진법에서 B는 10이다.

입력

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 64 이상 1,000,000 이하인 하나의 정수로 주어진다.

출력

출력은 표준출력을 사용한다. 하나의 테스트 데이터에 대한 답을 하나의 줄에 출력한다. 각 테스트 데이터에 대해, 주어진 수가 어떤 B진법 (2 ≤ B ≤ 64)으로 표현하여 회문이 될 수 있다면 1을, 그렇지 않다면 0을 출력한다.

문제풀이

회문은 거꾸로 읽어도 바로 읽은 것과 같은 문장

을 의미한다.

1. 모든 진법에 대해 진법을 변환하자

digit배열을 만들때 정확한 자리값을 구하기 위해 나는 x의 복사본을 만들어 계산하여 배열의 길이를 구하였다.

이번에는 회문인지 판단하기 위해 생성한거라서 뒤집을 필요가 없다..!

    public  static int convertBase(int x, int B) {
        int len = 0, copyX = x;
        while (copyX >0 ) {
            copyX /= B;
            len++;
        }

        int[] digit = new int[len];
        len = 0;
        while (x > 0) {
            digit[len++] = x % B;
            x /= B;
        }
    }

2. 변환된 수가 회문이 될 수 있는지 판단한다 반을 나눠서 계산해보자.

회문이라면 true를 반환하고 아니라면 false를 반환한다.

비교는 반으로 나누어 처음과 끝부터 하나하나씩 비교하면 공통인지 아닌지 알 수 있다.

    public static boolean isPalindrome(int[] digit) {
        for(int i=0; i< digit.length/2; i++)
            if(digit[i]!=digit[digit.length - i - 1])
                return  false;
        return true;
    }

3. 입력을 테스트케이스만큼 받고 회문이라면 1을 아니라면 0을 출력하자

비교를 하여 true가 하나라도 있다면 끝나니 break를 걸어 반복문을 종료한다.

    public static  void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-->0) {
            int x = sc.nextInt();
            boolean ans = false;

            for (int i=2; i<=64; i++) {
                int[] baseDigit = convertBase(x, i);
                if (isPalindrome(baseDigit)) {
                    ans = true;
                    break;
                }
            }
            System.out.println(ans ?  "1" : "0");
        }
    }

시간복잡도

이 알고리즘의 시간복잡도는 O(64 * logb(x))이다.

 

[3085] 사탕게임

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

128 MB

52696

18645

12797

34.180%

문제

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

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

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

입력

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

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

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

출력

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

문제풀이

색이 다른 사탕이 인전합 두칸을 골라 사탕을 서로 교환할때 같은 색으로 이루어진 가장 긴 연속 부분 행/열의 최대값을 구하자.

1. 가능한 모든 쌍의 사탕을 서로 교환한다.

교환 가능한 사탕은 서로 인접해야 한다. 그리고 서로 색이 달라야 한다 두가지 조건을 if문을 작성해서 조건을 충족시키자!

4방향으로 인접한 행렬을 비교하면 중복문제가 발생한다. 아래 이미지를 보면 중복이 발생하는 것을 확인할 수 있다..!

그래서 증가하는 두방향만 확인을 한다면 중복을 해결할 수 있다.

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++) {
                if (j + 1 < N && map[i][j] != map[i][j + 1]) {
                    swapCandy(map, i, j, i, j + 1);
                    ans = Math.max(ans, Math.max(findMaxColumn(map), findMaxRow(map)));
                    swapCandy(map, i, j, i, j + 1);
                }
                if (i + 1 < N && map[i][j] != map[i + 1][j]) {
                    swapCandy(map, i, j, i + 1, j);
                    ans = Math.max(ans, Math.max(findMaxColumn(map), findMaxRow(map)));
                    swapCandy(map, i, j, i + 1, j);
                }
            }
        }
        System.out.println(ans);
    }

2. 교환한 상태에서 가장 긴 연속 부분 행/열을 찾는다.

교환한 상태에서 이차원 배열 map에 있는 색이 같은 모든 행과 모든 열의 길이 중 가장 큰 길이를 갖고 있는 것을 반환하는 findMaxRow함수와 findMaxColumn함수를 만들었다. 비교를 하였을때 기준으로 모든 행과 열을 계산하는 것이다.

(2-1) 이전값과 비교하여 연속성을 판단하는 방법

public static int findMaxRow(char[][] map) {
	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);
	}
	return maxRow;
	}
	
	public static int findMaxColumn(char[][] map) {
	int N = map.length;
	int maxColumn = 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(maxColumn, len);
				len = 1;
			}
		}
		maxColumn = Math.max(maxColumn, len);
	}
	return maxColumn;
	}
	
	

(2-2) 변수를 이용해 연속성을 판단하는 방법

 public static int findMaxRow(char[][] map) {
	 int N = map.length;
	 int maxRow = 0;
	 
	 for(int r=0; r<N; r++) {
		int len = 0;
		int currentColor = map[r][0];
		for(int c= 0; c<N; c++) {
			if (map[r][c] == currentColor) len++;
			else {
				currentColor = map[r][c];
				len = 1;
			}
			maxRow = Math.max(maxRow, len);
		}
	}
	return maxRow;
}	

 public static int findMaxColumn(char[][] map) {
	 int N = map.length;
	 int maxColumn = 0;
	 
	 for(int c=0; c<N; c++) {
		int len = 0;
		int currentColor = map[r][0];
		for(int r= 0; r<N; r++) {
			if (map[r][c] == currentColor) len++;
			else {
				currentColor = map[r][c];
				len = 1;
			}
			maxColumn = Math.max(maxColumn, len);
		}
	}
	return maxColumn;
}	

시간복잡도

이 알고리즘의 시간복잡도는 O(N^2 * (2N^2 + 2N^2)) = O(N^4)이다.