Today's Algorithm(2019-01-14)

programmers. 숫자 야구

코드스쿼트라는 교육기관에 들어오기 전에 레벨 테스트로 숫자 야구를 구현했었는데요. 그렇다보니 이 문제가 참 낮설지 않았습니다. 이 문제에서 제가 생각하는 포인트는 2가지 입니다.

• 비교대상 숫자를 선정하는 방법
• 비교대상 숫자와 비교하여 스트라이크, 볼 판별

 

우선 '비교대상 숫자를 선정하는 방법'은 3자리 수를 만들기 위해 for문 3번을 쓸 수도 있겠지만 저는 그렇게는 하기 싫더라구요. 그래서 111~999까지 돌리는 방법을 정했는데요. 그렇게 하다보면 의도하지 않은 수(중복된 수가 존재하는 수, 0이 포함되는 수)가 나오게 됩니다. 그 경우는 Set<Integer> 를 사용하여 0이 포함되지 않으면서도 중복된 수를 걸려낼 수 있었습니다.

그리고 비교를 하는 경우는 뭐 다를 방법이 있을까요? 10씩 나눠주면서 나머지를 비교하였고 만약 자릿수가 다를 때는 위에서 만든 Set<Integer> 를 이용하여 다른 자리에 존재하는지 유무를 조사하여 볼 판별을 할 수 있었습니다. 아! 그리고 플래그 처리를 통해서 불필요한 계산(스트라이크, 볼 판별이 틀린 경우가 나왔을 때)을 줄이고 정확한 답(모든 판별이 맞았는지)을 구했습니다.

class Solution {
    public int solution(int[][] baseball) {
        int answer = 0;
        for (int i = 111; i < 1000; i++) {
            Set<Integer> set = setInit(i);
            if(set.contains(0) || set.size() != 3) continue;

            boolean flag = true;
            for (int[] ints : baseball) {
                int target = ints[0];
                int num = i;
                int strike = 0;
                int ball = 0;

                while(num != 0) {
                    int temp = target % 10;
                    if(num % 10 == temp) strike++;
                    else if(set.contains(temp)) ball++;
                    num /= 10; target /= 10;
                }

                if(strike != ints[1] || ball != ints[2]) {
                    flag = false;
                    break;
                }
            }

            if(flag) answer++;
        }
        return answer;
    }

    private Set<Integer> setInit(int i) {
        Set<Integer> set = new HashSet<>();
        String[] numText = String.valueOf(i).split("");
        for (String s : numText) {
            set.add(Integer.valueOf(s));
        }
        return set;
    }
}

 

 

programmers. 섬 연결하기

처음에 방향을 잘못 잡는 바람에 조금 고생했던 문제입니다. 맨 처음에는 '가장 적은 비용 순으로 하나씩 더해가면서 모든 도시를 다 돌때 그때 반복문에서 나오도록' 생각했거든요. 그런데 이것의 문제점은 종료시점이 부정확하고 모든 도시를 다 도는 것과 연결하는 다리 사이와 정확한 관련성이 없다는 것에서 여러 논리적 허점이 들어났습니다.

 

그렇게 고민끝에 조금 복잡하지만 bfs를 이용하기로 생각했습니다. 아이디어는 간단합니다.

비용이 적은 순으로 해당 노드를 연결했을 때 섬의 개수가 줄어들면 포함시킨다!!

섬의 개수를 구하는 방법은 bfs를 돌리는데 방문 표시를 하면서 Queue위에 모든 경우를 체크할 수 있도록 n개수만큼 반복문 돌리면 됩니다. 그렇기 떄문에 예를들어 (1-2-3, 4-5, 6, 7) 이렇게 연결이 되어있다면 섬의 개수는 4개가 나오고 Queue안에서 1,2,3 돌려지고 4,5 그리고 6 따로 7 따로 이렇게 체크될 것입니다. 아마 bfs 문제를 좀 풀어보셨다면 이런 식으로 푼 문제를 만났을거라 생각합니다.

이렇게 하면 단점은 복잡도가 증가한다는 것입니다. 저도 코드를 짜다가 무한루프를 돌기도 하고 OutOfIndex 에러가 뜨기도 했었는데요. List의 remove() 안에 Integer타입을 지울 떄는 index 번호로만 지우고, Queue에 넣기전에 방문 표시를 해야하는데 이후에 하다보니 무한루프에 빠지는 실수를 하였기 때문입니다. 큐에 이미 들어온 이상 그 수가 포함된 것이기 때문에 미리 방문 표시해야 무한루프를 피할수 있습니다. 이제 그럼 코드를 보겠습니다.

class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        Queue<Cost> queue = initCost(costs);  // 오름차순 우선순위큐
        List<List<Integer>> list = new ArrayList<>(); 
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());  // NullPointException피하기 위해
        }
        int node = 0;
        int curIslandCount = n;  // 초기 섬의 개수 -> 6개

        while (node < n - 1) {  // 만약 도시가 5개면 3개까지 받아야 4개 노드를 구할 수 있음
            Cost cost = queue.poll();
            int temp = getIslandCount(curIslandCount, n, list, cost);  // 노드 연결 후 섬의 개수
            if(curIslandCount > temp) {  // 만약 섬의 개수가 줄어들었다면
                curIslandCount = temp;
                answer += cost.cost;
                node++;
            }
        }

        return answer;
    }

    private int getIslandCount(int curIslandCount, int n, List<List<Integer>> list, Cost cost) {
        int city1 = cost.city1;
        int city2 = cost.city2;

        list.get(city1).add(city2);  // 서로 연결 기록
        list.get(city2).add(city1);

        Queue<Integer> queue = new LinkedList<>();
        int thisIslandCount = 0;  // 노드 연결 후 섬 개수 기록할 변수
        boolean[] visit = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (visit[i] == false && list.get(i).size() == 0) {  // 비었거나 방문하지 않을때, 혼자 동떨어진 섬일 경우
                visit[i] = true;
                thisIslandCount++;
                continue;
            }
            if(visit[i]) continue;  // 방문했던 도시

            visit[i] = true; 
            queue.addAll(list.get(i));
            for (Integer integer : list.get(i)) {
                visit[integer] = true;  // 큐에 넣으면 무조건 방문표시
            }
            while (!queue.isEmpty()) {
                int city = queue.poll();
                for (Integer integer : list.get(city)) {  // 해당 도시와 연결된 다른 도시
                    if(!visit[integer]) {
                        visit[integer] = true;  // 큐에 넣으면 무조건 방문표시
                        queue.add(integer);
                    }
                }
            }
            thisIslandCount++;  // 이것도 꼭 섬 +1증가 해야함
        }

        if(curIslandCount == thisIslandCount) {  // 만약 섬의 개수가 줄어들지 않았다면 원복
            list.get(city1).remove(list.get(city1).indexOf(city2));
            list.get(city2).remove(list.get(city2).indexOf(city1));
        }
        return thisIslandCount;
    }

    private Queue<Cost> initCost(int[][] costs) {
        Queue<Cost> costList = new PriorityQueue<>();
        for (int[] cost : costs) {
            costList.add(new Cost(cost[0], cost[1], cost[2]));
        }
        return costList;
    }
}

class Cost implements Comparable<Cost> {
    int city1;
    int city2;
    int cost;

    public Cost(int city1, int city2, int cost) {
        this.city1 = city1;
        this.city2 = city2;
        this.cost = cost;
    }

    @Override
    public int compareTo(Cost o) {  // 비용 오름차순 순으로 정렬
        return this.cost - o.cost;
    }
}