10월 1주차 문제 [ 2단계 ]

[Tokwasp]

📢 이번 주 알고리즘 스터디 문제

이번 주에는 총 4문제를 풉니다.
(정답률은 프로그래머스 기준)

---

📌 문제 목록 [ 1단계 ]

번호	문제	정답률	링크
1	양궁대회	38%	🔗 바로가기
2	타겟 넘버	64%	🔗 바로가기

---

🗓️ 발표

• 시간: 금요일 오전 10시
• 방식: 각자 풀이 공유 + 코드 리뷰

---

🚨 벌금 규칙

• 문제를 풀지 않은 경우 → 💸 1만 원

---

🔥 이번 주도 화이팅입니다!

[Tokwasp]

🎯 양궁 대회

public class ArcheryCompetition {
    private static int[] apeachInfo;
    private static int[] rionInfo;
    private static int[] result;

    private static int arrowCount;
    private static int maxDiff = 0;

    public int[] solution(int arrowCount, int[] apeachInfo) {
        this.apeachInfo = apeachInfo;
        this.arrowCount = arrowCount;

        result = new int[11];
        rionInfo = new int[11];

        dfs(0, 0);

        return maxDiff == 0 ? new int[]{-1} : result;
    }

    private static void dfs(int depth, int shootCount) {
        if (depth == 10) {
            rionInfo[10] += arrowCount - shootCount;

            int diff = getDiff();
            if (diff > 0) {
                if (diff > maxDiff || (diff == maxDiff && isBetter(rionInfo, result))) {
                    maxDiff = diff;
                    updateResult();
                }
            }

            rionInfo[10] = 0;
            return;
        }

        // 해당 점수를 포기
        dfs(depth + 1, shootCount);

        // 해당 점수를 획득
        int need = apeachInfo[depth] + 1;
        if (shootCount + need <= arrowCount) {
            rionInfo[depth] = need;
            dfs(depth + 1, shootCount + need);
            rionInfo[depth] = 0;
        }
    }

    private static int getDiff() {
        int rionScore = 0;
        int apeachScore = 0;

        for (int i = 0; i < 11; i++) {
            if (apeachInfo[i] == 0 && rionInfo[i] == 0) continue;

            if (rionInfo[i] > apeachInfo[i]) {
                rionScore += 10 - i;
            } else {
                apeachScore += 10 - i;
            }
        }

        return rionScore - apeachScore;
    }

    private static void updateResult() {
        for (int i = 0; i < 11; i++) {
            result[i] = rionInfo[i];
        }
    }

    private static boolean isBetter(int[] newInfo, int[] oldInfo) {
        for (int i = 10; i >= 0; i--) {
            if (newInfo[i] > oldInfo[i]) return true;
            else if (newInfo[i] < oldInfo[i]) return false;
        }
        return false;
    }
}

---

🎯 타겟 넘버

📖 문제 요약

• 각 숫자를 양수 혹은 음수로 선택하여 합계를 구한다.
• 최종 합계가 targetNumber가 되는 경우의 수
• 시간 복잡도: 숫자 부호 선택 (+), (-) * 20 ( 수의 개수 ) = 2의 20승 = 100만

public class TargetNumber {
    private static int[] numbers;
    private static int count;

    public int solution(int[] numbers, int target) {
        count = 0;
        this.numbers = numbers;
        dfs(0, numbers.length, 0, target);
        return count;
    }

    private static void dfs(int depth, int targetDepth, int total, int target) {
        if (depth == targetDepth) {
            if (total == target) count++;
            return;
        }

        dfs(depth + 1, targetDepth, total + numbers[depth], target);
        dfs(depth + 1, targetDepth, total - numbers[depth], target);
    }
}

---

📖 [ Stack 풀이 ]

🛠️ 풀이 과정 예시 [ 4, 1, 2, 1 ]

• 1번째: 4, Stack1: [-4, 4]
• 2번째: 1, 이전 결과 = Stack1: [-4, 4], 새로운 결과 = Stack2 [-5, -3, 3, 5]

lass Solution {
    public int solution(int[] numbers, int target) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        stack1.push(0);
        
        for(int i = 0; i < numbers.length; i++){
            int number = numbers[i];
            
            while(!stack1.isEmpty()){
                int stackNum = stack1.pop();
                stack2.push(stackNum + number);
                stack2.push(stackNum - number);
            }
            stack1 = stack2;
            stack2 = new Stack<>();
        }
    
        int count = 0;
        while(!stack1.isEmpty()){
            if(stack1.pop() == target) count++;
        }
        return count;
    }
}

[sduddla]

1️⃣ 양궁 대회

function solution(n, info) {
    // n 라이언이 가진 화살의 개수
    // info 어피치가 맞힌 과녁의 점수의 개수를 10점부터 0점까지 순서대로 담은 정수 배열
    // 각 구간 -> 라이언이 어피치보다 많이 쏘거나 안 쏘거나
    
    let maxDiff = 0;
    let ryan = Array(11).fill(0);
    let answer = [-1];
    
    function dfs(index, arrowLeft) {
        // 0~10점 다 탐색
        if(index === 11) {
            ryan[10] += arrowLeft; // 남은 화살 다 0점에 몰기
            
            // 현재 점수
            let ryanScore = 0;
            let apeachScore = 0;
            
            for(let i = 0; i < 11; i++) {
                // 둘 다 0점이면 점수 없음
                if(ryan[i] === 0 && info[i] === 0) continue;
                
                if(ryan[i] > info[i]) ryanScore += (10 - i);
                else apeachScore += (10 - i);
            }
            
            // 점수 차
            let diff = ryanScore - apeachScore;
            
            if(diff > 0) {
                if(diff > maxDiff) {
                    maxDiff = diff;
                    answer = [...ryan];
                } else if(diff === maxDiff) { // 점수 차 같으면 낮은 점수 더 많이 맞힌 경우 선택
                    for(let i = 10; i >= 0; i--) {
                        if(ryan[i] > answer[i]) {
                            answer = [...ryan];
                            break;
                        } else if(ryan[i] < answer[i]) {
                            break;
                        }
                    }
                }
            }
            
            ryan[10] -= arrowLeft; // 0점에 몰았던 화살 빼기
            return;
            
        }
        
        // 어피치 이기기 - 한 발 더 쏘기
        if(arrowLeft > info[index]) {
            ryan[index] = info[index] + 1;
            dfs(index + 1, arrowLeft - (info[index] + 1));
            ryan[index] = 0;
        }
        
        // 점수 포기
        dfs(index + 1, arrowLeft);
        
    }
    
    dfs(0, n);
    return maxDiff === 0 ? [-1] : answer;
}

---

2️⃣ 타겟 넘버

function solution(numbers, target) {
    
    let cnt = 0; // 타겟 넘버 만드는 방법의 수
    
    function dfs(index, sum) { // 인덱스, 현재까지 합
        if(index === numbers.length) {
            if(sum === target) {
                cnt++;
            }
            return;
        }
        dfs(index + 1, sum + numbers[index]);
        dfs(index + 1, sum - numbers[index]);
        
    }
    dfs(0, 0);
    
    return cnt;
}