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

[Tokwasp]

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

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

---

📌 문제 목록 [ 1단계 ]

번호	문제	정답률	링크
1	문자열 나누기	60%	🔗 바로가기
2	키패드 누르기	53%	🔗 바로가기

---

🗓️ 발표

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

---

🚨 벌금 규칙

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

---

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

[Tokwasp]

✂️ [ 문자열 나누기 ]

🧩 문제 요약

• 첫 글자 X / X 아닌 문자 개수가 같으면 분해 반복
• 예외: 분해 안된 경우 ex) aab

---

⚙️ 문제 풀이

• 첫 글자 X : Stack 저장
• X 아닌 문자 개수 : count
• 스택의 크기와 count 가 같으면 분해
• 예외: Stack이 비어 있지 않은 경우 + 1
• 시간 복잡도: 1만 O(N)

class Solution {
    public int solution(String input) {
        Stack<Character> stack = new Stack<>();
        
        int total = 0;
        int count = 0;
        for(int index = 0; index < input.length(); index++){
            char ch = input.charAt(index);
            
            // 첫 문자인 경우
            if(stack.isEmpty()){
                stack.push(ch);
                continue;
            }
            
            // 첫 문자와 같은 문자 / 다른 문자인 경우
            if(stack.peek() == ch){
                stack.push(ch);
            } else {
                count++;
            }
            
            // X와 X아닌 글자들이 나온 횟수가 같은 경우
            if(stack.size() == count){
                stack.clear();
                total++;
                count = 0;
            }
        }
        
        // 분해 되지 않은 문자가 남은 경우
        if(!stack.isEmpty()){
            total++;    
        }
        return total;
    }
}

---

🔢 [ 키패드 누르기 ]

⚙️ 문제 풀이

• Hand Class 직접 구현 풀이

class Solution {
    public String solution(int[] numbers, String direction) {
        String[][] board = new String[][]{
            {"1","2","3"},
            {"4","5","6"},
            {"7","8","9"},
            {"*","0","#"}
        };
        
        Hand leftHand = new Hand(3, 0, "L");
        Hand rightHand = new Hand(3, 2, "R");
        
        StringBuilder sb = new StringBuilder();
        for(int index = 0; index < numbers.length; index++){
            int targetNumber = numbers[index];
            
            // 1,4,7
            if(leftHand.isMoveAble(targetNumber)){
                leftHand.move(board, targetNumber);
                sb.append(leftHand.type);
            } 
            
            // 3,6,9
            if(rightHand.isMoveAble(targetNumber)){
                rightHand.move(board, targetNumber);
                sb.append(rightHand.type);
            }
            
            // 둘중 하나 움직였다면
            if(leftHand.isMove || rightHand.isMove){
                leftHand.moveInit();
                rightHand.moveInit();
                continue; 
            }
               
            // 2,5,8,0
            int leftDist = leftHand.getDistanceFrom(board, targetNumber);
            int rightDist = rightHand.getDistanceFrom(board, targetNumber);
            
            // 왼손 길이가 더 멀다면
            if(leftDist > rightDist){
                rightHand.move(board, targetNumber);
            } 
            
            // 거리 같다면
            if(leftDist == rightDist){
                if(direction.equals("left")){
                    leftHand.move(board, targetNumber);
                }
                
                if(direction.equals("right")){
                    rightHand.move(board, targetNumber);
                }
            }
            
            // 오른손이 더 멀다면
            if(leftDist < rightDist){
                leftHand.move(board, targetNumber);
            }
            
            if(leftHand.isMove){
                sb.append(leftHand.type);
                leftHand.moveInit();
            }
            
            if(rightHand.isMove){
                sb.append(rightHand.type);
                rightHand.moveInit();
            }
        }
        return sb.toString();
    }
    
    static class Hand{
        private int row;
        private int col;
        private String type;
        private boolean isMove;
        
        public Hand(int row, int col, String type){
            this.row = row;
            this.col = col;
            this.type = type;
            this.isMove = false;
        }
        
        public boolean isMoveAble(int number){
            if(this.type.equals("L") && number % 3 == 1){
                return true;
            }
            
            if(this.type.equals("R") && number % 3 == 0){
                if(number == 0) return false;
                return true;
            }
            return false;
        }
        
        public void move(String[][] board, int number){
            for(int row = 0; row < board.length; row++){
                for(int col = 0; col < board[0].length; col++){
                    if(board[row][col].equals(String.valueOf(number))){
                        this.row = row;
                        this.col = col;
                    }
                }
            }
            this.isMove = true;
        }
        
        public int getDistanceFrom(String[][] board, int number){
            int targetRow = 0;
            int targetCol = 0;
            
            for(int row = 0; row < board.length; row++){
                for(int col = 0; col < board[0].length; col++){
                    if(board[row][col].equals(String.valueOf(number))){
                        targetRow = row;
                        targetCol = col;
                    }
                }
            }
            return Math.abs(this.row - targetRow) + Math.abs(this.col - targetCol);
        }
        
        public void moveInit(){
            this.isMove = false;
        }
    }
}

[sduddla]

1️⃣ 문자열 나누기

시간 복잡도: O(n)

function solution(s) {
    // x와 x가 아닌 다른 글자들이 나온 횟수 각각 세기
    // 처음으로 두 횟수가 같아지는 순간, 읽은 문자열 분리
    // 남은 문자열이 있다면, 이것도 분리
    
    let x = ''; // 첫 글자
    let xCount = 0; // x가 나온 횟수
    let otherCount = 0; // x가 아닌 다른 글자들이 나온 횟수
    let result = 0; // 분해한 문자열 개수
    
    // 첫 글자 정하기
    for(let i = 0; i < s.length; i++) {
        if(x === '') { // 첫 글자 안 정했다면
            x = s[i];
            xCount++;
        } else if(s[i] === x) { // x와 같다면
            xCount++;
        } else { // x와 다르다면
            otherCount++;
        }

        if(xCount === otherCount) { // 두 횟수가 같아질 경우
            result++;
            
            // 초기화
            x = '';
            xCount = 0;
            otherCount = 0;
        }
    }
    
    // 남은 문자열이 있다면 이것도 분리
    if(xCount !== 0 || otherCount !== 0) result++;
    
    return result;
}

---

2️⃣ 키패드 누르기

function solution(numbers, hand) {
    // 엄지손가락, 상하좌우 4가지 방향으로만 이동, 한 칸 거리 1
    // 1, 4, 7 - 왼손 엄지 손가락
    // 3, 6, 9 - 오른손 엄지손가락
    // 2, 5, 8, 0 - 더 가까운 엄지손가락 사용 / 거리 같으면 오른손잡이는 오른손 왼손잡이는 왼손
    // numbers 순서대로 누를 번호가 담긴 배열
    // hand 왼손잡이인지 오른손잡이인 지 나타내는 문자열
    
    let left = '*';
    let right = '#';
    let result = '';
    
    const position = {
        1: [0, 0],
        2: [0, 1],
        3: [0, 2],
        4: [1, 0],
        5: [1, 1],
        6: [1, 2],
        7: [2, 0],
        8: [2, 1],
        9: [2, 2],
        '*': [3, 0],
        0: [3, 1],
        '#': [3, 2],
    }
    
    for(let num of numbers) {
        if([1, 4, 7].includes(num)) { // 왼손
            result += 'L';
            left = num;
        } else if([3, 6, 9].includes(num)) { // 오른손
            result += 'R';
            right = num;
        } else {
            // 2, 5, 8, 0
            const [leftX, leftY] = position[left];
            const [rightX, rightY] = position[right];
            const [numX, numY] = position[num];
            
            const leftDistance = Math.abs(leftX - numX) + Math.abs(leftY - numY);
            const rightDistance = Math.abs(rightX - numX) + Math.abs(rightY - numY);
            
            if(leftDistance < rightDistance) {
                result += 'L';
                left = num;
            } else if(rightDistance < leftDistance) {
                result += 'R';
                right = num;
            } else {
                if(hand === 'left') { // 왼손잡이
                    result += 'L';
                    left = num;
                } else { // 오른손잡이
                    result += 'R';
                    right = num;
                }   
            }
        }
    }
    return result;
}

[dbrkdgus00]

문자열 나누기

해결방법

1. 첫 글자를 기준으로 같은 글자 개수(same)와 다른 글자 개수(diff)를 센다.
2. same == diff가 되는 순간, 문자열을 하나의 덩어리로 나눴다고 판단하고 분할 횟수(count)를 1 증가.
3. 이후 남은 문자열에서 다시 같은 방식으로 반복한다.
4. 문자열을 끝까지 순회하면, 총 몇 번 분할했는지를 return.

class Solution {
    public int solution(String s) {
        int count = 0; // 문자열 분해 횟수 저장
        int i = 0;     // 현재 위치
        
        while (i < s.length()) {
            char first = s.charAt(i);
            int same = 0; // 첫 글자와 같은 글자 수
            int diff = 0; // 다른 글자 수
            
            for (int j = i; j < s.length(); j++) {
                if (s.charAt(j) == first) same++;
                else diff++;
                
                if (same == diff) {
                    i = j + 1; // 다음 분해 시작 위치
                    break;
                }
                
                if (j == s.length() - 1) {
                    i = s.length();
                }
            }
            count++;
        }
        
        return count;
    }
}

키패드 누르기

import java.util.*;

class Solution {
    public String solution(int[] numbers, String hand) {
        // 키패드 각 숫자의 위치를 배열로 표현 (행, 열)
        int[][] keypad = {
            {3, 1}, // 0번 위치
            {0, 0}, {0, 1}, {0, 2},
            {1, 0}, {1, 1}, {1, 2},
            {2, 0}, {2, 1}, {2, 2}
        };

        // 시작 위치: 왼손은 * = (3,0), 오른손은 # = (3,2)
        int[] leftPos = {3, 0};
        int[] rightPos = {3, 2};

        StringBuilder result = new StringBuilder();

        for (int number : numbers) {
            int[] targetPos = keypad[number]; // 지금 누를 숫자의 위치

            // 왼쪽 열 숫자면 무조건 왼손
            if (number == 1 || number == 4 || number == 7) {
                result.append("L");
                leftPos = targetPos;

            // 오른쪽 열 숫자면 무조건 오른손
            } else if (number == 3 || number == 6 || number == 9) {
                result.append("R");
                rightPos = targetPos;

            // 가운데 열이면 거리 계산
            } else {
                int leftDist = Math.abs(leftPos[0] - targetPos[0]) + Math.abs(leftPos[1] - targetPos[1]);
                int rightDist = Math.abs(rightPos[0] - targetPos[0]) + Math.abs(rightPos[1] - targetPos[1]);

                // 왼손이 더 가까우면 왼손
                if (leftDist < rightDist) {
                    result.append("L");
                    leftPos = targetPos;

                // 오른손이 더 가까우면 오른손
                } else if (rightDist < leftDist) {
                    result.append("R");
                    rightPos = targetPos;

                // 거리가 같으면 손잡이 기준
                } else {
                    if (hand.equals("right")) {
                        result.append("R");
                        rightPos = targetPos;
                    } else {
                        result.append("L");
                        leftPos = targetPos;
                    }
                }
            }
        }

        return result.toString();
    }
}