[Java]백준 2798번: 블랙잭

문제 url:
블랙잭

문제:

🤔 문제 알아보기

• 첫 줄에 n과 m을 입력받는데, n은 카드의 개수를 m은 카드 3장을 더했을 때 m에 근삿값을 찾기 위해 사용 되는 변수이다.
• 두 번째줄은 n개의 카드 개수만큼, 카드를 받는다.

대충 문제를 읽었을 때, 요구하는 바는 이와 같다.
그렇다면 m에 대한 근삿값을 구하기 위해서는 n개의 카드에서 3장을 더해 모두 비교하는 방법이 존재할 것인데, 이는 완전탐색(브루트포스 알고리즘)으로 풀어야 하는 문제이다.

이제 코드와 함께 더 자세히 알아보자

🐱‍👤 실제코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // n개의 데이터를 배열에 담기 위한 행위
        int[] arr = new int[n];
        int token = 0;
        StringTokenizer st_arr = new StringTokenizer(br.readLine());
        while(st_arr.hasMoreTokens()) {
            arr[token] = Integer.parseInt(st_arr.nextToken());
            token++;
        }

        int approximate = 0;
		// 어차피 3개를 뽑기 때문에 i는 뒤에 j, k를 제외한 n-2까지 반복
        for(int i = 0; i <n-2; i++) {
        	// j는 뒤에 k를 제외한 n-1까지 반복
            for(int j = i+1; j <n-1; j++) {
                for(int k = j+1; k < n; k++ ) {
                    int sum = arr[i] + arr[j] + arr[k];
                    if(sum <= m && approximate < sum) {
                        approximate = sum;
                    }
                }
            }
        }

        System.out.println(approximate);
    }
}

😢 코드 분석

먼저 문제 조건에 따라 n과 m을 입력받는다.
그런 다음 둘 째줄에 해당하는 값을 for문에서 사용하기 위해 배열에 담아 저장한다.

int[] arr = new int[n];
int token = 0;
StringTokenizer st_arr = new StringTokenizer(br.readLine());
while(st_arr.hasMoreTokens()) {
      arr[token] = Integer.parseInt(st_arr.nextToken());
      token++;
}

위 코드가 배열에 대한 코드인데, 하나씩 살펴보면
arr 변수는 n개(카드의 수)만큼 공간을 담을 배열을 생성

hasMoreTokens() 메서드는. StringTokenizer에서 반환할 토큰이 존재한다면, true를 반환하는 메서드로 while문에서 같이 사용할 수 있다.

그런 다음 token++를 하며 나머지 배열까지 넣을 수 있도록 한다.

int approximate = 0;
// 어차피 3개를 뽑기 때문에 i는 뒤에 j, k를 제외한 n-2까지 반복
for(int i = 0; i <n-2; i++) {
    // j는 뒤에 k를 제외한 n-1까지 반복
    for(int j = i+1; j <n-1; j++) {
        for(int k = j+1; k < n; k++ ) {
            int sum = arr[i] + arr[j] + arr[k];
            if(sum <= m && approximate < sum) {
                 approximate = sum;
            }
        }
    }
}

해당 알고리즘이 이번 문제를 푸는 로직으로,
approximate는 근삿값을 저장하기 위한 변수

3중 for문인 이유는 3개의 카드를 완전탐색 방식으로 구해야 하기 때문에 3중 for문을 사용한 것이다.

3중 for문이기 때문에 시간 복잡도는 O(n ^ 3)이다.
※여기서 시간 제한 1초를 주었는데, 이는 1억번 연산이 가능한 횟수로.
n의 값은 최대 100, 이를 세제곱해도 10000번이기 때문에 O(n^3)도 가능한 것이다.

틀렸으면 얘기해주시면 감사하겠습니다.

for문을 하나씩 들여다 보면, 해당 문제는 중복된 수를 허용하지 않는다.
즉, 첫번 째 테스트 케이스에서 5, 6, 7, 8, 9에서 3장을 뽑아 21을 만든다면, 7, 7, 7을 고르면 될 것이지만. 한장씩 뽑아야 하는 문제이므로 6, 7, 8을 이용해 21을 조합해야 하는 방식이다.

그래서 반복횟수를 보면 i는 n-2이전까지, j는 n-1이전까지 반복하는 것이다.

if(sum <= m && approximate < sum) {
    	approximate = sum;
}

먼저 sum <= m은 조건에서 3카드의 합은 m을 넘으면 안된다고 했기 때문에 작거나 같다로 표시한 것이며,
approximate(근삿값을 저장하는 변수)은 sum보다 작을 떄,
approximate변수를 가장 큰 값으로 초기화 시킬 수 있게 되는 것이다.

🤢 코드 리팩토링

역시.. 깔끔하게 짯다는 생각이 들지 않아 한번 고쳐봤다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // n개의 데이터를 배열에 담기 위한 행위
        int[] arr = new int[n];
        StringTokenizer st_arr = new StringTokenizer(br.readLine());
        for (int i =0; i < n; i++) {
            arr[i] = Integer.parseInt(st_arr.nextToken());
        }

        int approximate = 0;

        // 어차피 3개를 뽑기 때문에 i는 뒤에 j, k를 제외한 n-2까지 반복
        for(int i = 0; i <n-2; i++) {
            //만약 첫번째 카드가 m보다 크다면 조건에 해당하지 않으니 continue
            if(arr[i] >= m) {
                continue;
            }
            // j는 뒤에 k를 제외한 n-1까지 반복
            for(int j = i+1; j <n-1; j++) {
                //만약 첫 번쨰 카드와 두 번쨰 카드의 합이 m보다 크다면 조건에 해당하지 않으니 
                //continue
                if(arr[i] + arr[j] >= m) {
                    continue;
                }
                for(int k = j+1; k < n; k++ ) {
                    int sum = arr[i] + arr[j] + arr[k];

                    // 합이 m과 같다면 굳이 더 반복할 필요가 없기 때문에 for문을 멈춘다.
                    if(sum == m) {
                        approximate = sum;
                        System.out.println(approximate);
                        return;
                    }

                    if(sum <= m && approximate < sum) {
                        approximate = sum;
                    }
                }
            }
        }

        System.out.println(approximate);
    }
}

위에서도 말했지만, 해당 문제의 시간 복잡도는 O(N^3)을 가진다. 하지만 최악의 경우라고 해서, 무조건 N^3만큼 연산 횟수를 가질 필요는 없다.

그래서 조금이나마 for문을 덜 돌기 위해 위 코드에 if문을 추가한 모습을 볼 수 있다.

해당 if문을 얘기하자면,

• 첫번쨰 카드가 M보다 크거나 같으면, 나머지 2카드는 쓸모가 없어지기 때문에 조건에 맞지 않으니 하위 for문을 돌지 않도록 continue
• 첫번째 카드와 두 번쨰 카드의 합이 M보다 크거나 같으면, 나머지 카드는 쓸모 없어지니, 똑같이 하위 for문을 돌지 않도록 continue
• 마지막으로 만약 for문중, 3카드의 합이 m과 같으면 조건에 부합하기 때문에 이대로 출력한 후 return을 통해 명령어를 멈춘다.

해당 방법을 통해 조금이나마 반복을 줄일 수 있다. 하지만 이번 문제는, n값이 크지 않기 때문에 조건문을 다는 것이 시간이 더 걸릴 수 있다고 한다.

💜 참고자료

[백준] 2798번 : 블랙잭 - JAVA [자바] Stranger'sLAB