9월 4주차 문제 [ 1단계 ]

[Tokwasp]

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

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

---

📌 문제 목록 [ 1단계 ]

번호	문제	정답률	링크
1	[1차] 다트 게임	60%	🔗 바로가기
2	실패율	62%	🔗 바로가기

---

🗓️ 발표

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

---

🚨 벌금 규칙

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

---

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

[pia01190]

📌 다트게임

• String dartResult을 한 글자씩 쪼개서 처리

class Solution {
    public int solution(String dartResult) {
        int[] result = new int[3];
        int index = -1;
        int num = 0;
        
        for (int i = 0; i < dartResult.length(); i++) {
            char score = dartResult.charAt(i);
            
            if (score == 'S' || score == 'D' || score == 'T') {
                index = area(result, index, num, score);
            } else if (score == '*' || score == '#') {
                award(result, index, score);
            } else if (i > 0 && dartResult.charAt(i) == '0' && dartResult.charAt(i - 1) == '1') {
                num = 10;
            } else {
                num = Integer.parseInt(String.valueOf(score));
            }
        }
        
        int answer = 0;
        for (int i : result) {
            answer += i;
        }
        
        return answer;
    }
    
    private static int area(int[] result, int index, int num, char score) {
        if (score == 'S') {
            result[++index] = num;
        } else if (score == 'D') {
            num *= num;
            result[++index] = num;
        } else if (score == 'T') {
            num = num * num * num;
            result[++index] = num;
        }
        
        return index;
    }
    
    private static void award(int[] result, int index, char score) {
        if (score == '*') {
            result[index] *= 2;
                
            if (index > 0) {
                result[index - 1] *= 2;
            }
        } else if (score == '#') {
            result[index] *= -1;
        }
    }
}

📌 실패율

• 스테이지의 개수 : 500
• stages의 길이 : 200000
• => 완전 탐색

import java.util.*;

class Solution {
    public int[] solution(int N, int[] stages) {
        List<double[]> fail = new ArrayList<>();
        
        for (int i = 1; i <= N; i++) {
            int stageCount = 0;
            int failCount = 0;
            
            for (int j = 0; j < stages.length; j++) {
                if (stages[j] >= i) {
                    stageCount++;
                    
                    if (stages[j] == i) {
                        failCount++;
                    }
                }
            }
            
            double failRate = (failCount == 0) ? 0 : (double) failCount / stageCount;
            fail.add(new double[] {i, failRate});
        }
        
        fail.sort((a, b) -> {
            if (a[1] == b[1]) return Double.compare(a[0], b[0]);
            return Double.compare(b[1], a[1]);
        });
        
        int[] result = new int[N];
        for (int i = 0; i < fail.size(); i++) {
            result[i] = (int) fail.get(i)[0];
        }
        
        return result;
    }
}

[dbrkdgus00]

다트 게임

import java.util.*;

class Solution {
    public int solution(String dartResult) {

        // 3개의 점수를 저장할 리스트
        List<Integer> scoreList = new ArrayList<>();

        // 현재 위치를 나타내는 변수
        int index = 0;

        while (index < dartResult.length()) {
            int score = 0;

            // 점수 부분 처리 (10인지 1자리인지 구분해야 함)
            if (dartResult.charAt(index) == '1' && index + 1 < dartResult.length() && dartResult.charAt(index + 1) == '0') {
                // 숫자 '10'인 경우
                score = 10;
                index += 2; // 두 글자를 넘김
            } else {
                // 숫자 0~9인 경우
                score = dartResult.charAt(index) - '0'; // '3' → 3
                index++; // 한 글자 넘김
            }

            // 보너스 처리 (S, D, T)
            char bonus = dartResult.charAt(index);
            if (bonus == 'S') {
                score = (int)Math.pow(score, 1); // 그냥 그대로
            } else if (bonus == 'D') {
                score = (int)Math.pow(score, 2); // 제곱
            } else if (bonus == 'T') {
                score = (int)Math.pow(score, 3); // 세제곱
            }
            index++; // 보너스도 처리했으니까 다음 글자

            // 옵션 처리 (* 또는 #)
            if (index < dartResult.length()) {
                char option = dartResult.charAt(index);
                if (option == '*') {
                    // 현재 점수 두 배
                    score *= 2;

                    // 이전 점수도 두 배
                    if (!scoreList.isEmpty()) {
                        int lastIndex = scoreList.size() - 1;
                        scoreList.set(lastIndex, scoreList.get(lastIndex) * 2);
                    }

                    index++; // 옵션 처리 끝
                } else if (option == '#') {
                    // 현재 점수 마이너스 처리
                    score *= -1;
                    index++; // 옵션 처리 끝
                }
                // 옵션 없으면 그냥 넘어감
            }

            // 점수를 리스트에 저장
            scoreList.add(score);
        }

        // 모든 점수 더하기
        int total = 0;
        for (int s : scoreList) {
            total += s;
        }

        return total;
    }
}

실패율

해결 방법

• 각 스테이지에 도달한 사람 수 세기
  입력으로 주어진 stages 배열을 돌면서, 각 스테이지에 도달했지만 아직 통과 못한 사람 수를 count[] 배열에 저장한다.

• 실패율 계산
  1번 스테이지부터 N번 스테이지까지 반복하면서,
  해당 스테이지에 멈춘 사람 수 / 그 스테이지 이상 도달한 사람 수 = 실패율
  실패율을 계산한 후, [스테이지 번호, 실패율] 형태로 리스트에 저장한다.

• 정렬
  실패율을 기준으로 내림차순 정렬한다.
  실패율이 같다면 스테이지 번호가 낮은 것부터 정렬한다.

• 결과 반환
  정렬된 리스트에서 스테이지 번호만 뽑아 배열로 반환한다.

import java.util.*;

class Solution {
    public int[] solution(int N, int[] stages) {
        int[] count = new int[N + 2];  // 각 스테이지에 머무는 사람 수 (1 ~ N+1)
        
        // 각 스테이지에 머무는 사람 수 세기
        for (int stage : stages) {
            count[stage]++;
        }

        // 실패율 저장 리스트 (스테이지 번호, 실패율)
        List<double[]> failList = new ArrayList<>();
        int users = stages.length; // 처음에는 전체 유저 수

        for (int i = 1; i <= N; i++) {
            int failed = count[i];
            double failRate = 0;

            if (users > 0) {
                failRate = (double) failed / users;
            }

            failList.add(new double[] { i, failRate });
            users -= failed; // 다음 스테이지 도달 유저 감소
        }

        // 실패율 기준 정렬 (같으면 번호 오름차순)
        Collections.sort(failList, (a, b) -> {
            if (a[1] == b[1]) {
                return (int)(a[0] - b[0]); // 스테이지 번호 오름차순
            } else {
                return Double.compare(b[1], a[1]); // 실패율 내림차순
            }
        });

        // 정답 배열 만들기
        int[] answer = new int[N];
        for (int i = 0; i < N; i++) {
            answer[i] = (int) failList.get(i)[0];
        }

        return answer;
    }
}

[sduddla]

1️⃣ [1차] 다트 게임

function solution(dartResult) {
    // 점수: 0 ~ 10까지
    // S: 1제곱
    // D: 2제곱
    // T: 3제곱
    // *: 바로 전 점수와 현재 점수를 각각 2배
    // #: 현재 점수 음수로
    
    let dartResultArr = dartResult.split(''); // 배열로
    let scores = []; // 점수 저장
    let num = ''; // 10
    
    for(let i = 0; i < dartResultArr.length; i++) {
        let ch = dartResultArr[i];
        
        if(!isNaN(ch)) { // 숫자인 경우
            num += ch;
        }
        
        else if(ch === 'S' || ch === 'D' || ch === 'T') {
            let score = parseInt(num);
            num = '';
            
            // 보너스
            if(ch === 'S') score = Math.pow(score, 1);
            if(ch === 'D') score = Math.pow(score, 2);
            if(ch === 'T') score = Math.pow(score, 3);
            
            scores.push(score);
        }
        
        // 옵션
        else if (ch === '*' || ch === '#') {
            if(ch === '*') {
                scores[scores.length - 1] *= 2; // 현재 점수
                if(scores.length > 1) { // 최소 2개 이상 쌓였을 때
                    scores[scores.length - 2] *= 2; // 전 점수
                }
            } else if(ch === '#') { 
                scores[scores.length - 1] *= -1; // 현재 점수
            }
        }
    }
    
    return scores.reduce((a, b) => a + b);
}

---

2️⃣ 실패율

function solution(N, stages) {
  let stageCnt = Array(N + 2).fill(0); // 스테이지 별 도전자 수
  
  for(let count of stages) { // 각 스테이지에 멈춘 사람 수 카운트
    stageCnt[count]++;
  }
    
  let result = [];
  let players = stages.length; // 전체 플레이어 수
    
  // 실패율 계산
  for(let i = 1; i <= N; i++) {
    let failRate = 0;
        
    if(players > 0) {
      failRate = stageCnt[i] / players; // 해당 스테이지에 멈춘 사람  / 전체 플레이어 수
      players -= stageCnt[i]; // i번 스테이지에 멈춘 사람 제외            
    }
    
    result.push([i, failRate]);
  }
    
  result.sort((a, b) => {
    if(b[1] === a[1]) return a[0] - b[0]; // 실패율 같으면 스테이지 번호 오름차순
    return b[1] - a[1]; // 실패율 내림차순
  });
    
  // 스테이지 번호만 반환
  return result.map(item => item[0]); 
}

[Tokwasp]

🎯 [1차] 다트 게임

[ 구현 방법 ]

• 시간 복잡도: 제한 없음 (구현 문제)
• 입력 값을 통해 다트를 만들고 리스트에 넣는다.
• 다트 리스트를 순회하며 점수를 계산하고, 이전 다트와 옵션을 적용한다. ( 단. 첫 번째 다트는 이전 다트가 없으므로 0점 다트 기본 추가 )

public int solution(String dartResult) {
        List<Dart> darts = new ArrayList<>();
        int index = 0;

        while (index <= dartResult.length() - 1) {
            int score = 0;
            
            // 점수 입력
            if (dartResult.charAt(index + 1) == '0') {
                score = 10;
                index += 2;
            } else {
                score = dartResult.charAt(index) - '0';
                index += 1;
            }

            // 보너스
            char bonus = dartResult.charAt(index++);
            char option = '0';

            // 옵션이 있다면 추가
            if (index <= dartResult.length() - 1 &&
                    (dartResult.charAt(index) == '*' || dartResult.charAt(index) == '#')) {
                option = dartResult.charAt(index++);
            }
            darts.add(new Dart(score, bonus, option));
        }

        // 스택 방식으로 상단의 다트 계산
        Stack<Dart> stack = new Stack<>();
        
        // 기본 0점 다트 추가
        stack.push(new Dart(0, 'S', '0'));
        
        for (int i = 0; i < darts.size(); i++) {
            Dart dart = darts.get(i);
            dart.calculateScore();

            // 이전 다트와 옵션 적용
            Dart priorDart = stack.pop();
            dart.applyOption(priorDart);
            stack.push(priorDart);
            stack.push(dart);
        }

        int score = 0;
        while (!stack.isEmpty()) {
            score += stack.pop().score;
        }
        return score;
    }

    static class Dart {
        private int score;
        private char bonus;
        private char option;

        public Dart(int score, char bonus, char option) {
            this.score = score;
            this.bonus = bonus;
            this.option = option;
        }

        public int calculateScore() {
            if (bonus == 'S') {
                score = (int) Math.pow(score, 1);
            }

            if (bonus == 'D') {
                score = (int) Math.pow(score, 2);
            }

            if (bonus == 'T') {
                score = (int) Math.pow(score, 3);
            }
            return score;
        }

        public void applyOption(Dart priorDart) {
            if (option == '0') {
                return;
            }

            if (option == '*') {
                priorDart.score *= 2;
                score *= 2;
            }

            if (option == '#') {
                score *= -1;
            }
        }
    }

---

📉 [실패율]

[ 규칙 찾기 ]

• ex) [ 1, 2, 2, 2, 3, 3, 4, 6 ]
• 정렬 이유: 데이터가 난잡하여 정렬 해야 규칙을 더 쉽게 찾을 수 있음
• 2스테이지 도전자 수: 전체 인원수 8 - ( 2 스테이지 첫 시작 인덱스 1 ) = 7명
• 2스테이지 클리어 못한 사람 수: 숫자 2가 연속된 개수 = 3명

[ 정리 ]

• N스테이지 도전자 수 = 전체 인원수 - N 스테이지 시작 인덱스
• N스테이지 클리어X 사람 수 = N스테이지에 위치한 사람 수
• 시간 복잡도: 최대 도전자 수 = 20만

public int[] solution(int N, int[] stages) {
        Arrays.sort(stages);
        List<Result> failStages = new ArrayList<>();
        
        int index = 0;
        
        // 1 ~ N 스테이지 까지 반복
        for(int i = 1; i <= N; i++){
            int count = 0;
            int startIndex = index;
            
            // 현재 스테이지에 머문 사용자 수 찾기
            while(index <= stages.length - 1 && stages[index] == i){
                index++;
                count++;
            }
            
            // 전체 길이 - 시작 인덱스 = 도전자 수
            // ex) [1,1,2,2,3] 2스테이지 도전자수 5-2 = 3명
            int length = stages.length - startIndex;
            double failPercent = 0;
            
            // 예외 처리: ex) N = 2 [1,1] 2스테이지 도전자 수 0명 0나누기 방지
            if(length != 0){
                failPercent = count / (double) length;
            }
            failStages.add(new Result(i, failPercent));
        }
        
        // 실패율 내림차순, 스테이지 번호 오름차순 정렬
        failStages.sort(Comparator.naturalOrder());
        return failStages.stream().mapToInt(a -> a.stageNum).toArray();
    }
    
    private static class Result implements Comparable<Result>{
        private int stageNum;
        private double failPercent;
        
        public Result(int stageNum, double failPercent){
            this.stageNum = stageNum;
            this.failPercent = failPercent;
        }
        
        public int compareTo(Result another){
            double compare = this.failPercent - another.failPercent;
            if(compare < 0){
                return 1;
            } else if(compare == 0){
                return this.stageNum - another.stageNum;
            } else {
                return -1;
            }
        }
    }