[코딩 테스트] 백준 2503 (브루트포스 알고리즘)

브루트포스 알고리즘이란?

• 완전 탐색 또는 무차별 대입 알고리즘
• 쉽게 말해 모든 가능한 숫자들을 대입해 보는 방식
• 선형 구조 : 순차 탐색, 비선형 구조 : 백트래킹, DFS, BFS

문제 설명

풀기 전 생각

• 무작정 대입 알고리즘이니 세 자릿수 100부터 999까지 List에 넣기
• 100부터 999까지 반복을 돌면서 정답과 같은 위치면 strikeCnt++ 그렇지 않고 포함만 돼있으면 ballCnt++
• stikeCnt와 ballCnt가 힌트와 같지 않고 가능성 없는 수면 지우기

코드

import java.util.*;
import java.io.*;
public class Baek2503 {
    public static void main(String[] args) throws IOException {
        List<String> answerList = new ArrayList<String>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        for(int i = 100; i < 1000; i++){
            answerList.add(String.valueOf(i));
        }

        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String request = st.nextToken();
            int strike = Integer.parseInt(st.nextToken());
            int ball = Integer.parseInt(st.nextToken());
            for (int j = 100; j < 1000; j++) {
                String strj = String.valueOf(j);
                int strikeCnt = 0;
                int ballCnt = 0;
                if (request.charAt(0) == strj.charAt(0)) {
                    strikeCnt++;
                }else if (request.contains(String.valueOf(strj.charAt(0)))) {
                    ballCnt++;
                }
                if (request.charAt(1) == strj.charAt(1)) {
                    strikeCnt++;
                }else if (request.contains(String.valueOf(strj.charAt(1)))) {
                    ballCnt++;
                }if (request.charAt(2) == strj.charAt(2)) {
                    strikeCnt++;
                } else if (request.contains(String.valueOf(strj.charAt(2)))) {
                    ballCnt++;
                }
                if (strikeCnt != strike || ballCnt != ball) {
                    answerList.remove(strj);
                }
            }
        }
        System.out.println(answerList.size());
    }
}

오류 및 개선 

• 예제는 통과했지만 테스트케이스 실패
• 반례는 조건이 (서로 다른 세 자릿수) & (1~9까지의 숫자만) 된다는 조건을 놓침

최종 코드

import java.util.*;
import java.io.*;
public class Baek2503 {
    public static void main(String[] args) throws IOException {
        List<String> answerList = new ArrayList<String>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        for(int i = 100; i < 1000; i++){
            answerList.add(String.valueOf(i));
        }

        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String request = st.nextToken();
            int strike = Integer.parseInt(st.nextToken());
            int ball = Integer.parseInt(st.nextToken());
            for (int j = 100; j < 1000; j++) {
                String strj = String.valueOf(j);
                int strikeCnt = 0;
                int ballCnt = 0;
                if(strj.charAt(0)==strj.charAt(1)||strj.charAt(0)==strj.charAt(2)||strj.charAt(1)==strj.charAt(2)){
                    answerList.remove(strj);
                    continue;
                }if(strj.charAt(0)=='0'||strj.charAt(1)=='0'||strj.charAt(2)=='0'){
                    answerList.remove(strj);
                    continue;
                }
                if (request.charAt(0) == strj.charAt(0)) {
                    strikeCnt++;
                }else if (request.contains(String.valueOf(strj.charAt(0)))) {
                    ballCnt++;
                }
                if (request.charAt(1) == strj.charAt(1)) {
                    strikeCnt++;
                }else if (request.contains(String.valueOf(strj.charAt(1)))) {
                    ballCnt++;
                }if (request.charAt(2) == strj.charAt(2)) {
                    strikeCnt++;
                } else if (request.contains(String.valueOf(strj.charAt(2)))) {
                    ballCnt++;
                }
                if (strikeCnt != strike || ballCnt != ball) {
                    answerList.remove(strj);
                }
            }
        }
        System.out.println(answerList.size());
    }
}

시간이 많을 땐 함수로 분리!!