[백준] 2966번: 찍기(완전탐색, brute force)

https://www.acmicpc.net/problem/2966

2966번: 찍기

코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		/** 0 **/
		char[] A = {'A', 'B', 'C'};
		char[] B = {'B', 'A', 'B', 'C'};
		char[] G = {'C', 'C', 'A', 'A', 'B', 'B'};
		boolean flag = true;
		String[] name = {"Adrian", "Bruno", "Goran"};
		int[] rightCount = new int[3];
		String answer = scan.next();
		
		/** 1 **/
		for(int i=0; i<answer.length(); i++) {
			for(int j=0; j<A.length; j++) {
				if(i+j >= answer.length()) {
					flag = false;
					break;
				}
				
				if(answer.charAt(i+j) == A[j])
					rightCount[0] ++;
			}
			if(!flag)
				break;
			i += A.length-1;
		}
		
		/** 2 **/
		flag = true;
		for(int i=0; i<answer.length(); i++) {
			for(int j=0; j<B.length; j++) {
				if(i+j >= answer.length()) {
					flag = false;
					break;
				}
				
				if(answer.charAt(i+j) == B[j])
					rightCount[1] ++;
			}
			if(!flag)
				break;
			i += B.length-1;
		}
		
		/** 3 **/
		flag = true;
		for(int i=0; i<answer.length(); i++) {
			for(int j=0; j<G.length; j++) {
				if(i+j >= answer.length()) {
					flag = false;
					break;
				}
				
				if(answer.charAt(i+j) == G[j])
					rightCount[2] ++;
			}
			if(!flag)
				break;
			i += G.length-1;
		}
		
		/** 4 **/
		int max = 0;
		for(int i=0; i<rightCount.length; i++)
			if(rightCount[i] > max)
				max = rightCount[i];
		System.out.println(max);
		
		/** 5 **/
		for(int i=0; i<name.length; i++) {
			if(max == rightCount[i])
				System.out.println(name[i]);
		}
		
		scan.close();
	}

}

 

문제 이해

구현이 꽤 까다로웠다... 생각할 것이 좀 있기도해고, 복잡하게 풀어서 코드도 길어졌다.

문제를 보고 생각한 풀이는 , 

상근, 창영, 현진이가 각각 몇문제를 맞혔는지 전부 count를 하고,

가장 많이 맞힌 학생을 출력하는, 완전 탐색으로 풀려고 생각했다.

 

 

풀이

상근이는 A, B, C 순으로 찍고

창영이는 B, A, B, C 순으로 찍고

현진이는 C, C, A, A, B, B 순으로 찍는다.

따라서 위 세명이 찍는 방식을 배열로 저장한다.

 

/** 0 **/

char[] A, B, G

 - 각 학생이 찍는 규칙을 저장하고,

 

boolean flag

for문에서 범위가 벗어날경우 break를 걸어주기 위해 선언했다.

 - 예제 입력 1을 예로들면, 정답은 BAACC로 길이가 5지만, 현진이가 찍는 규칙의 길이는 6이다. 따라서 현진이가 찍는 배열의 길이가 정답의 길이보다 커질때, break로 탈출을 해줘야 한다.

 

String[] name

 - 마지막 출력에 사용할 세 학생의 이름을 저장한다.

 

int[] rightCount

 - 세 학생의 정답 수를 저장한다.

 

String answer

 - 정답을 입력받는다.

 

/** 1 **/

상근이가 찍은 문제의 정답을 구하는 for문이다.

i는 정답의 길이, j는 상근이가 찍은 문자의 길이다.

위 flag를 선언할때 말했던 것 처럼, 범위가 벗어날경우 탈출을 시킨다.

정답이 BAACC 일 때, 상근이는 A, B, C, A, B, C, ... 순으로 찍는다.

B A A

A B C

위 세개를 확인하고, 넘어가야하는 다음 정답은 상근이가 찍는 규칙의 길이만큼 뛰어넘어야 한다.

B A A 다음 확인해야할 부분은 C C <- 이부분이다.

따라서 i의 값을 A.length - 1 만큼 더해주는데, -1을 하는 이유는 for문에 ++을 해주기 때문이다.

 

B A A C C

A B C

다음으로는

B A A C C

        A B C ... 

위와같이 확인해야 한다.

 

따라서 A배열의 인덱스는 j로 동일하지만,

문자열 answer의 인덱스는 위에 처럼 이동하므로 i값만큼 더해줘야 한다.

if(answer.charAt(i+j) == A[j])
    rightCount[0] ++;

 

/** 2 **/ , /** 3 **/

위 2번, 3번은 /**1 **/과 동일하게 각각 창영, 현진이의 정답을 카운트 해주는 for문이다ㅣ.

 

 

/** 4 **/

세 학생중 정답을 가장 많이 맞춘(잘찍은) 학생을 찾고, max에 저장한다.

 

 

/** 5 **/

각 학생별 맞은 정답을 저장한 rightCount 배열의 요소값이 max와 동일할 때, 

동일한 i값을 인덱스로 갖는 name 배열을 출력한다.

 

 

다른 풀이

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = Integer.parseInt(sc.nextLine());
		String answer = sc.nextLine();
		int[] score = new int[3];
		int[] pattern = { 66, 65, 66, 67 };
		for (int i = 0; i < n; i++) {
			if (answer.charAt(i) == i % 3 + 65) {
				score[0]++;
			}
			if (answer.charAt(i) == pattern[i % 4]) {
				score[1]++;
			}
			if (answer.charAt(i) == (i + 4) % 6 / 2 + 65) {
				score[2]++;
			}
		}
		
		int max = 0;
		for (int i = 0; i < 3; i++) {
			if (score[i] > max) {
				max = score[i];
			}
		}
		
		System.out.println(max);
		if (score[0] == max) {
			System.out.println("Adrian");
		}
		if (score[1] == max) {
			System.out.println("Bruno");
		}
		if (score[2] == max) {
			System.out.println("Goran");
		}
		
		sc.close();
	}
}

pattern 배열의 66, 65, 66, 67 값은 각각 아스키코드값으로 B, A, B, C 값이다.

위에 각 학생별 score 배열을 저장하는 논리가 너무너무 깔끔하다 ... !!

 

 

 

import java.util.*;

class Main {
	public static void main(String[] Q) {
		Scanner k = new Scanner(System.in);
		int s = Integer.parseInt(k.nextLine());
		String rslt = k.nextLine().substring(0, s);
		String a = "ABC";
		String b = "BABC";
		String g = "CCAABB";
		int best[] = new int[3];
		for (int i = 0; i < rslt.length(); i++) {
			if (rslt.charAt(i) == a.charAt(i % 3))best[0]++;
			if (rslt.charAt(i) == b.charAt(i % 4))best[1]++;
			if (rslt.charAt(i) == g.charAt(i % 6))best[2]++;
		}
		int Ma=best[0];
		int index=0;
		for(int i=0;i<best.length;i++) {
			if(best[i]>=Ma)
			{
				Ma=best[i];
				index=i;
			}
		}
		System.out.println(Ma);
		if(best[0]==Ma)System.out.println("Adrian");
		if(best[1]==Ma)System.out.println("Bruno");
		if(best[2]==Ma)System.out.println("Goran");

	}
}

각 학생의 정답을 저장할 때, 3, 4, 6 으로 나눈 인덱스와 동일한지를 판단해서 저장..... 왕

if문을 한줄로 서술하긴 했지만 역시 깔끔한 코드 ...

 

 

 

마지막 출력은 다 동일하지만, 각 학생이 찍는 길이는 3, 4, 6 이므로

이 값을 잘 이용하면 훨씬 쉽고 간결하게 풀 수 있었다 .!!