TIL 220518

백트래킹(backtracking)이란?: 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법

 

깊이 우선 탐색(DFS)이란? (37번, 소수 만들기) 

출처:https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog

 

학교 자료구조 시간에 DFS/BFS를 배웠음에도 불구하고 아래 코드를 이해하기 굉장히 어려웠다.. 알듯말듯 하면서 또 이해가 안가고. 콘솔에 어떻게 찍어야할지도 몰라서 일일이 손으로 다 해봤다.

    public int solution(int[] nums) {

        visit=new boolean[nums.length]; //입력 받은 배열들의 수만큼 길이의 boolean type 배열
        arr = new int[3];
        dfs(0,nums,0);

        return answer;
    }

    public void dfs(int depth, int[] nums, int start) {
        if (depth == 3) {
            for (int val : arr) {
                sum += val;
            }
            System.out.println(sum);
            if (isPrime(sum)) {
                answer++;
            }

            sum = 0;
            return;
        }
        for (int i = start; i < visit.length; i++) {
            if (!visit[i]) {
                visit[i] = true;
                arr[depth] = nums[i];
                dfs(depth + 1, nums, i); //arr요소에 nums[i]가 채워짐, 재귀
                visit[i] = false;
            }
        }
    }

    public boolean isPrime(int x) {
        if (x == 0 || x == 1) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(x); i++) {
            if (x % i == 0)
                return false;
        }
        return true;
    }

• boolean의 기본형은 false: nums.length만큼 생성된 boolean visit 배열의 안의 값은 초기에 모두 false

코드 이해하기

코드를 직접 이해하면서 depth와 start 변수를 이해했다. 설명하기도 정말 어렵다.

1. 3개의 수를 뽑는 경우이므로 ary[] = new int[3]을 정의해주고 dfs 함수를 이용해서 하나씩 넣어준다.

2. depth가 0일 경우 ary[0]에 값을, 2일 경우 ary[2]에 값을 넣어준다. 

3. depth가 3이 될 경우 ary에 값이 다 차므로 ary 요소를 모두 더해준 값을 sum에 담아 소수인지 아닌지 판별해주는 isPrime 함수에서 검사해주고 맞다면 answer++를 해준다. 그리고 sum값을 0으로 초기화

4. if(!visit) 값이 True라면 dfs를 반복할 필요 없다.. depth가 1인 수(ary의 두번째 값)의 반복문 안의 i가 2라면 그 다음수 depth 2(ary의 세번째 값)은 visit[i]부터 true false를 판별한다. 

 

dfs를 완전히 이해한 건 아닌 거 같지만 찍먹 정도는 해본 것 같다...

 

DecimalFormat

public void getPassenger(String destination, float placeDistance){
        if(this.status == false){
            System.out.println("탑승 불가");
            return;
        }else{
            this.status = false;
            DecimalFormat df = new DecimalFormat("#.##");
            System.out.println("택시 운행을 시작합니다. 목적지: " + destination + " 목적지까지 거리: " + df.format(placeDistance));
            this.placeDistance = (float) Math.floor(placeDistance*10)/10;

        }
    }

 

택시 모델을 만드는 과제였는데 float/double형에서 보여줄 소수점을 지정하는 함수였다.

 

 

Map.entry 인터페이스 (20번, 완주하지 못한 선수)

• Map 인터페이스의 내부 인터페이스
• Map에 저장되는 Key-Value 쌍을 저장하기 위해 내부적으로 Entry 인터페이스 정의

public String solution_2(String[] participant, String[] completion) {
        String answer = "";

        HashMap <String, Integer> map = new HashMap<>();
        for(String player : participant){
            map.put(player, map.getOrDefault(player, 0) + 1);
        }
        for(String player : completion){
            map.put(player, map.get(player) - 1);
        }

        Iterator<Map.Entry<String, Integer>> iter = map.entrySet().iterator();


        while(iter.hasNext()){
            Map.Entry<String, Integer> entry  = iter.next();
            if(entry.getValue() == 1){
                answer = entry.getKey();
                break;
            }
        }

        return answer;
    }

• map.getOrDefault(player, 0) + 1: map 안에 player에 해당하는 key의 value가 존재하면 값을 가져오고 그렇지 않다면 Default인 0을 넣어라.
• Iterator을 선언하여 컬렉션(Collection)객체에 보관하고 있는 자료들을 순차적으로 접근하면서 처리할 수 있도록 한다.
• for(String player : completion) map.put(player, map.get(player) - 1);: for-each 구문. completion 배열 String에 player(key)가 존재하면 value 값을 -1 해준다.
• while(iter.hasNext()): map.Entry에 다음 요소가 있을 때까지 반복한다.

참고: https://joy-baek.tistory.com/20

iterator & hasnext (), next() 메소드 - 미완성

참고2: https://coding-grandpa.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80-%EB%AA%BB%ED%95%9C-%EC%84%A0%EC%88%98-%ED%95%B4%EC%8B%9C-Lv-1

[프로그래머스] 완주하지 못한 선수 (해시 Lv. 1) - 자바 Java