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

[Tokwasp]

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

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

---

📌 문제 목록 [ 1단계 ]

번호	문제	정답률	링크
1	크레인 인형뽑기 게임	54%	🔗 바로가기
2	숫자 짝꿍	62%	🔗 바로가기

---

🗓️ 발표

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

---

🚨 벌금 규칙

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

---

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

[sduddla]

1️⃣ 크레인 인형뽑기 게임

시간 복잡도: O(m*n)

• m = moves (최대 1000)
• n = board.length (최대 30)
• 최대 3만

function solution(board, moves) {
    // board에서 moves에 따라 인형 뽑음
    // 뽑은 인형 바구니에 넣기
    // 바구니에서 가장 위 인형과 같으면 둘다 pop
    
    let stack = []; // 바구니
    let cnt = 0; // 터트려서 사라진 인형 개수
    
    for(let move of moves) {
        for(let i = 0; i < board.length; i++) {
            const doll = board[i][move - 1];
            if(doll !== 0) {
                board[i][move - 1] = 0; // 인형 뽑았으니 0으로 처리
                if(stack[stack.length - 1] === doll) { // 바구니 맨 위 인형과 같다면 터트리기
                    stack.pop();
                    cnt += 2;
                } else {
                    stack.push(doll); // 바구니에 인형 추가
                }
                break;
            }
        }
    }
    return cnt;
}

---

2️⃣ 숫자 짝꿍

시간 복잡도: O(n+m)

• X 문자열 순회: O(n)
• Y 문자열 순회: O(m)
• 최대 600만

function solution(X, Y) {
    // 0~9 각 숫자 개수 저장할 배열
    const cntX = Array(10).fill(0);
    const cntY = Array(10).fill(0);
    
    // X 문자열에 등장하는 각 숫자 개수 카운트
    for(let nCnt of X) {
        cntX[nCnt]++;
    }
    
    // Y 문자열에 등장하는 각 숫자 개수 카운트
    for(let nCnt of Y) {
        cntY[nCnt]++;
    }
    
    let result = '';
    
    for(let i = 9; i >= 0; i--) {
        const common = Math.min(cntX[i], cntY[i]); // 최소 개수
        result += i.toString().repeat(common); // 해당 숫자 반복해서 추가
    }
    
    if(result === '') return '-1'; // 공통 숫자 없을 경우
    if(result[0] === '0') return '0'; // 0만 여러 개 있을 때 0 하나만 반환
    return result;
}

[Tokwasp]

🧸 크레인 인형뽑기 게임

🎯 문제 풀이

• 상단 인형 두개 확인 = Stack
• 시간 복잡도: 1000 ( move 크기 )

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        Stack<Integer> stack = new Stack<>();
        
        int count = 0;
        for(int i = 0; i < moves.length; i++){
            int col = moves[i] - 1;
            
            // 크레인 로직
            for(int row = 0; row < board.length; row++){
                int number = board[row][col];
                
                // 뽑을 인형이 있다면
                if(number != 0){
                    count += craneLogic(board, row, col, stack);
                    break;
                }
            }
        }
        return count;
    }
    
    private static int craneLogic(int[][] board, int row, int col, Stack<Integer> stack){
        stack.push(board[row][col]);
        board[row][col] = 0;
    
        int count = 0;
        
        // 상단 두개 같은지 확인
        if(stack.size() >= 2){
            int num1 = stack.pop();
            int num2 = stack.pop();
                        
            if(num1 != num2){
                stack.push(num2);
                stack.push(num1);
            } else {
                count += 2;
            }
        }
        return count;
    }
}

---

🔢 숫자 짝궁

🧩 문제 풀이

• 요약: X, Y 겹친 숫자 확인 후 가장 큰 수 만들기
• 겹친 숫자와 개수를 알기 위해 map<Integer,Integer> 사용
• 겹친 숫자를 List에 넣고 내림 차순 정렬
• 시간 복잡도: 300만 * log 300만

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        Map<Integer, Integer> xCountMap = new HashMap<>();
        
        // X 입력
        for(int i = 0; i < X.length(); i++){
            int num = X.charAt(i) - '0';
            xCountMap.put(num, xCountMap.getOrDefault(num, 0) + 1);    
        }
        
        List<Integer> resultNumbers = new ArrayList<>();
        
        // Y 입력
        for(int i = 0; i < Y.length(); i++){
            int num = Y.charAt(i) - '0';
            
            if(xCountMap.containsKey(num)){
                resultNumbers.add(num);
                
                int count = xCountMap.get(num) - 1;
                
                if(count == 0){
                    xCountMap.remove(num);
                } else {
                    xCountMap.put(num, count);
                }
            }
        }
        
        // 없으면
        if(resultNumbers.isEmpty()){
            return "-1";
        }
        
        // 내림차순 정렬
        resultNumbers.sort(Comparator.reverseOrder());
        
        // 제일 작은게 0이라면
        if(resultNumbers.get(0) == 0){
            return "0";
        }
        
        StringBuilder sb = new StringBuilder();
        for(int num: resultNumbers){
            sb.append(num);
        }
        
        return sb.toString();
    }
}

---

배열 풀이

• 시간 복잡도: 300만

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        int[] x = new int[10];
        int[] y = new int[10];
        
        for(int i = 0; i < X.length(); i++){
            int num = X.charAt(i) - '0';
            x[num] += 1;
        }
        
        for(int i = 0; i < Y.length(); i++){
            int num = Y.charAt(i) - '0';
            y[num] += 1;
        }
        
        StringBuilder sb = new StringBuilder();
        boolean isFind = true;
        
        while(isFind){
            isFind = false;
            
            for(int num = 9; num >= 0; num--){
                if(x[num] >= 1 && y[num] >= 1){
                    sb.append(num);
                    x[num] -= 1;
                    y[num] -= 1;
                    
                    isFind = true;
                    break;
                }
            }
        }
        
        if(sb.length() == 0){
            return "-1";
        }
        
        if(sb.charAt(0) == '0'){
            return "0";
        }
        
        return sb.toString();
    }
}

[dbrkdgus00]

숫자 짝궁

해결방법

• X와 Y에서 각각 숫자(0~9)의 등장 횟수를 센다.
• 각 숫자(0~9)에 대해 두 수에서 공통으로 몇 번 등장하는지 확인한다.
• 공통으로 나온 숫자를 큰 숫자부터 문자열에 이어 붙인다.
• 예외 처리:
  아무 숫자도 없으면 "–1" 반환
  전부 0이면 "0" 반환

import java.util.*;

class Solution {
    public String solution(String X, String Y) {
        // 각 숫자(0~9)가 몇 번 나왔는지 저장할 배열 만들기
        int[] xCount = new int[10]; // X에서 각 숫자 개수
        int[] yCount = new int[10]; // Y에서 각 숫자 개수

        // X에서 숫자 세기
        for (char c : X.toCharArray()) {
            int num = c - '0';     // 문자 → 숫자로 바꾸기
            xCount[num]++;         // 해당 숫자 개수 +1
        }

        // Y에서 숫자 세기
        for (char c : Y.toCharArray()) {
            int num = c - '0';     // 문자 → 숫자
            yCount[num]++;         // 해당 숫자 개수 +1
        }

        // 결과를 저장할 문자열 (뒤에 붙여야 하니까 StringBuilder 사용)
        StringBuilder sb = new StringBuilder();

        // 숫자 9부터 0까지 돌면서 (큰 숫자가 앞으로 가야 제일 큼)
        for (int i = 9; i >= 0; i--) {
            int common = Math.min(xCount[i], yCount[i]); // 둘 다 있는 숫자 중 최소 개수

            // 그 숫자를 공통으로 몇 번 쓰는지
            for (int j = 0; j < common; j++) {
                sb.append(i); // i는 숫자(0~9)
            }
        }

        // 결과가 아무것도 없다면 (공통 숫자 없음)
        if (sb.length() == 0) {
            return "-1";
        }

        // 결과가 0000... 이런식이면 그냥 0으로 처리
        if (sb.charAt(0) == '0') {
            return "0";
        }

        // 최종 결과 리턴
        return sb.toString();
    }
}

크레딧 인형뽑기 게임

해결방법

• 크레인이 움직일 위치(moves)를 하나씩 읽음.
• 해당 위치의 인형을 위에서부터 찾음.
• 인형을 바구니에 넣음
• 같은 인형이 연속되면 터뜨리고 개수를 +2
• 모든 moves가 끝나면 터진 인형 총 개수를 반환

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {

        // 바구니를 만들어둠 (인형을 담는 통)
        Stack<Integer> basket = new Stack<>();

        // 터진 인형 개수를 저장할 변수
        int count = 0;

        // 크레인을 한 번씩 움직여보기
        for (int i = 0; i < moves.length; i++) {

            int move = moves[i] - 1; // 크레인은 1부터 시작하니까 -1 해줘야 함
            int picked = 0; // 이번에 뽑은 인형 (0이면 아직 못 뽑은 상태)

            // 인형 박스를 위에서부터 아래로 내려가며 살펴봄
            for (int j = 0; j < board.length; j++) {

                // 만약 여기에 인형이 있다면
                if (board[j][move] != 0) {

                    // 인형을 집음
                    picked = board[j][move];

                    // 인형을 집었으니까 빈칸으로 만들어줌
                    board[j][move] = 0;

                    // 그 다음에는 더 아래로 내려갈 필요 없으니까 멈춤
                    break;
                }
            }

            // 만약 이번 턴에 인형을 못 뽑았으면 (빈칸이었으면)
            if (picked == 0) {
                continue; // 그냥 다음으로 넘어감
            }

            // 바구니가 비어있지 않으면서, 맨 위 인형이랑 지금 인형이 같으면 터짐!
            if (!basket.isEmpty() && basket.peek() == picked) {
                basket.pop(); // 맨 위에 있는 인형 꺼내기
                count += 2;   // 같은 인형 2개 터짐
            } else {
                basket.push(picked); // 아니면 그냥 바구니에 넣기
            }
        }

        // 다 끝났으면 터진 인형 개수 반환
        return count;
    }
}