[백준] 2798번 : 블랙잭 - JAVA[자바] - 티스토리

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

2798번: 블랙잭

 * 입력 : N장의 카드가 주어짐 , 딜러가 M 이란 숫자가 주어짐

 * N장 중 3장 고를 수 있음. 3장의 합이 M을 넘으면 안됨. 

 

 * 시간복잡도 체크 

   3<= N <= 100  

  10<= M <= 300,000

 

 * 빅오 : 카드 100개 주어져서 배열에 담아도 배열의 크기가 100개 

   100 * 99 *98 대략 1000000번(백만번) 연산 < 1억을 넘지 않는다.  

 -> 제한시간 1초이기 때문에 브루트포스(완전탐색)해도 좋다. (1억 == 대략 1초 )

 

* 총 2가지의 풀이 방법으로 풀었다. 

1번째는,  시간생각안하고 반복문 다 돌려서 찾을 생각으로 풀었고, 

2번째는,  시간을 좀 더 고려했다.

깨닫고 바꾼 부분  

1. 중간중간에 if문을 넣어서 필요없는 연산을 피했다.

2. 삼항연산자를 -> if문으로 바꿨다. 

     바꾼 이유 : if문은 조건에 해당될 때만 연산을 하지만, 삼항연산자는 모든 경우를 연산한다. 

추가로, 코드에는 없지만 효율을 생각하여 바꾸어 주었다.

Scanner -> BufferedReader 

System.out.println -> BufferedWriter 

 

 

1 번째

package bruteforce;

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



public class BOJ_2798_clear {
	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		//첫 줄 입력 
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken()); 		 
		int[] arr = new int[n];
		
		//두번째 줄 입력 
		st = new StringTokenizer(bf.readLine());
		for(int i=0 ;i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		// M을 넘지 않는 && 가장 큰 숫자를 answer에 담아서 출력
		// 효율을 따지지 않고 무작정 다 돌릴 생각만 했던 1번째 풀이 
		int answer = solve1(n,m,arr);
		// 효율을 좀 더 생각한 2번째 풀이 
		// int answer = solve2(n,m,arr);
		
		

		
		bw.write(answer+"");
		bw.flush();
		bw.close();
		bf.close();
		
	}
	
	public static int solve1(int n,int m,int[] arr) {
		
		for(int i=0;i<n;i++) {
			for(int j=i+1;j<n;j++) {
				for(int k= j+1; k<n; k++) {
					int temp = arr[i]+arr[j]+arr[k];
					answer = temp <= m && answer < temp ? temp : answer;
			
				}
			}
		}
		return answer;
	}

}

2 번째

package bruteforce;

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



public class BOJ_2798_clear {
	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		//첫 줄 입력 
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken()); 		 
		int[] arr = new int[n];
		
		//두번째 줄 입력 
		st = new StringTokenizer(bf.readLine());
		for(int i=0 ;i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
        // M을 넘지 않는 && 가장 큰 숫자를 answer에 담아서 출력
		// 효율을 따지지 않고 무작정 다 돌릴 생각만 했던 1번째 풀이 
		//int answer = solve1(n,m,arr);
		// 효율을 좀 더 생각한 2번째 풀이 
		int answer = solve2(n,m,arr);
		
		

		
		bw.write(answer+"");
		bw.flush();
		bw.close();
		bf.close();
		
	}
	
	public static int solve2(int n,int m,int[] arr) {
			int answer=0;
			
			for(int i=0;i<n-2;i++) { 						//n-2 까지 
				if(arr[i]>m) continue;						//조건 추가  
				for(int j=i+1;j<n-1;j++) {					//n-1까지 
					if(arr[i]+arr[j]>m) continue;			//조건 추가
					for(int k= j+1; k<n; k++) {
						int temp = arr[i]+arr[j]+arr[k]; 	
						if(temp==m) return temp; 			//조건 추가
						if(temp<m && answer < temp)			//삼항연산자 -> 조건문 
							answer = temp;
						 
				
					}
				}
			}
			return answer;
		}

}

 

 

읽어주셔서 감사합니다.

지적이나, 조언 등 자유로운 코멘트 환영합니다~