문제

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

풀이

class Solution {

    int cnt = 0;

    public int solution(int[] numbers, int target) {
        dfs(0, numbers, 0, target);
        return cnt;
    }

    public void dfs(int index, int[] numbers, int temp, int target) {
        if (index == numbers.length) {
            if (temp == target) cnt++;
            return;
        }
        dfs(index+1, numbers, temp+numbers[index], target);
        dfs(index+1, numbers, temp-numbers[index], target);
    }
}

풀이 과정

• 깊이 우선 탐색을 사용하였다.
• index를 하나씩 전진시켜나가면서 빼거나 더해 가며 다시 재귀적으로 dfs 함수를 호출한다.
• 만약 모든 배열을 다 돌았다면 return하되 임시 변수 temp가 target과 같다면 cnt를 증가시켜준다.

문제

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다. computer[i][i]는 항상 1입니다.

풀이

class Solution {

    public int solution(int n, int[][] computers) {
        int num = 0;
        boolean[] connected = new boolean[n];
        for (int i=0; i<n; i++) {
            if (connected[i]) continue;
            // System.out.println(i);
            num++;
            connected[i] = true;
            search(i, connected, computers);
        }
        return num;
    }

    public void search(int thiscom, boolean[] connected, int[][] computers) {
        for ( int i=0; i<computers.length; i++) {
            if (connected[i] || computers[thiscom][i] == 0) continue;
            connected[i] = true;
            search(i, connected, computers);
        }
        return;
    }
}

풀이 과정

• 0번 컴퓨터에서부터 시작하여 연결되어 있다면 표시하고, 연결된 컴퓨터에 연결된 컴퓨터를 재귀적으로 확인하였다.
• 재귀를 모두 돌았는데도 표시되지 않은 컴퓨터가 있다면 다른 네트워크가 있다는 뜻이므로 num++ 하고 재귀를 반복한다.

문제

Leo는 카펫을 사러 갔다가 중앙에는 빨간색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 빨간색 격자의 수 red가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 빨간색 격자의 수 red는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

풀이

import java.util.ArrayList;

class Solution {
    public int[] solution(int brown, int red) {
        int[] ret = new int[2];

        int sum = (brown + 4) / 2;
        // System.out.printf("sum: %d\n", sum);
        int row = -1, col = -1;
        ArrayList<Integer> candidates = new ArrayList<>();

        for ( int i=3 ; i<=sum/2 ; i++ ) {
            candidates.add(i);
        }

        for ( int candi : candidates ) {
            // System.out.printf("%d, %d\n", candi, sum-candi);
            if ( (candi-2) * (sum-candi-2) == red ) {
                row = sum - candi;
                col = candi;
                break;
            }
        }

        ret[0] = row;
        ret[1] = col;

        return ret;
    }
}

풀이 과정

• red와 brown 중 범위가 더 적은 brown을 기준으로 완전탐색을 진행하기로 했다.
• (brown+4)/2 는 row와 col를 더한 값이 된다.
• 1과 2는 가로, 세로의 값이 될 수 없으므로 (red가 최소 1) 3부터 시작하여 후보군을 만든다.
• 후보군을 대상으로 완전 탐색을 진행한다.

다른 사람의 풀이를 보고 느낀 점 & 아쉬웠던 점

1. 수학식으로 푸셨던 분이 계셨는데, 분명히 좋은 풀이라고 생각하지만 시험장에서 단기간에 생각해내기엔 어렵다고 느껴졌다.
2. 나와 비슷한 풀이방식이지만 모두 후보군에 저장하지 않고 하나의 for문에서 후보 뽑기와 정답인지 확인을 동시에 진행하신 분이 계셨다. 좋은 방법이라고 생각한다. 메모리와 시간효율 두 가지 면 모두에서 좋은 것 같다.

어제 저녁 현대ngv의 코딩테스트를 보았다. 자세한 건 되도록이면 쓰지 않으려고 한다. 난이도 자체는 어렵지 않았는데, 허비한 시간이 좀 아쉽다. 특히 처음에 문제를 잘 이해하지 못해서 2~30분 정도를 날렸는데, 그 시간이 있었다면 문제를 모두 풀 수 있지 않았을까 싶다.

한편으로는 디버깅을 할 때, 어떤 입력을 넣으면 디버깅 시간을 단축할 수 있을지에 대해 다시 생각해보게 되었다. 최대한 끝점의 입력과, 예외적인 입력 역시 넣어볼 것. 여러 가지 경우의 수를 최대한 생각해서 넣어볼 것.

아쉬운 점도 있지만, 나름 최선을 다해 풀었다고 생각한다.

오늘 한 것

• 프로그래머스에서 코딩 테스트 연습문제 자바로 다시 풀기