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

[Tokwasp]

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

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

---

📌 문제 목록 [ 2단계 ]

번호	문제	정답률	링크
1	혼자서 하는 틱택토	41%	🔗 바로가기
2	줄 서는 방법	64%	🔗 바로가기

---

🗓️ 발표

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

---

🚨 벌금 규칙

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

---

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

[sduddla]

1️⃣ 혼자서 하는 틱택토

시간 복잡도: O(1)

• n: 행의 개수 (3)
• m: 열의 개수 (3)
• O(n*m) = O(9) = O(1)

function solution(board) {
    // 게임판이 규칙을 지켜서 진행한 틱택토에서 나올 수 있는 상황인가
    // o와 x 동시에 승리 불가
    // o 승리 -> x 보다 1개 많아야함
    // x 승리 -> o와 개수가 같아야 함
  
    // o 개수
    let oCount = 0;
  
    // x 개수
    let xCount = 0;
  
    // 개수 카운트
    for(let row of board) {
        for(let item of row) {
            if(item === 'O') oCount++;
            if(item === 'X') xCount++;
        }
    }
  
    // o는 x보다 1개 많거나 같아야 한다 -> x가 크거나 2개 이상 차이 나면 잘못된 게임
    if(xCount > oCount || oCount - xCount > 1) return 0;
    
    const win = (ch) => {
        // 가로
        for(let i = 0; i < 3; i++) {
            if(board[i][0] === ch && board[i][1] === ch && board[i][2] === ch) return true;
        }
        
        // 세로
        for(let i = 0; i < 3; i++) {
            if(board[0][i] === ch && board[1][i] === ch && board[2][i] === ch) return true;
        }
        
        // 대각선
        if(board[0][0] === ch && board[1][1] === ch && board[2][2] === ch) return true;
        if(board[2][0] === ch && board[1][1] === ch && board[0][2] === ch) return true;
        
        return false;  
    }
    
    const oWin = win('O');
    const xWin = win('X');
    
    // o와 x가 동시에 이길 수 없음
    if(oWin && xWin) return 0;
    
    // o가 이긴 경우, x의 개수보다 1개 더 많아야 한다.
    if(oWin && oCount < xCount + 1) return 0;
        
    // x가 이긴 경우, o와 X의 개수가 같아야 한다.
    if(xWin && xCount !== oCount) return 0;
    
    return 1;
}

---

2️⃣ 줄 서는 방법

시간 복잡도: O(n^2)

• for 반복문이 n번 실행되므로 O(n)
• splice는 배열 내부 요소를 한 칸씩 이동시키므로 O(n)
• 전체적으로 O(n^2)이지만, n ≤ 20이므로 성능에는 문제 없음

function solution(n, k) {
    let result = []; // 결과 담을 배열
    let nums = []; // 숫자 담을 배열
    
    // 1~n 번호 추가
    for(let i = 1; i <= n; i++) {
        nums.push(i);
    }
    
    // 팩토리얼
    function factorial(num) {
        if(num === 0) return 1;
        return num * factorial(num - 1);
    }
    
    k = k - 1; // 인덱스 0부터
    
    for(let i = n; i >= 1; i--) {
        const f = factorial(i - 1); // 현재 숫자 기준 뒤에 올 경우의 수
        const index = Math.floor(k / f); // 현재 자리 숫자가 num 배열에서 몇 번째인 지 계산
        result.push(nums[index]); // 선택된 숫자 추가
        nums.splice(index, 1); // 선택한 숫자 제거
        k %= f; // k 업데이트
    }
    return result;
}

[dbrkdgus00]

줄 서는 방법

해결방법

• 1부터 n까지 숫자를 배열에 넣는다.
• 3중 for문을 써서 줄을 세우는 모든 경우를 하나씩 만든다.
• 그때마다 몇 번째 경우인지 숫자를 세면서 count++ 한다.
• count가 k와 같아지면 그 줄을 결과로 저장하고 끝낸다.

import java.util.*;

class Solution {
    public List<Integer> solution(int n, long k) {
        int[] nums = new int[n]; // 숫자들 저장할 배열

        // 1부터 n까지 숫자 넣기
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }

        // 몇 번째인지 세는 변수
        int count = 0;

        // 결과 저장할 리스트
        List<Integer> answer = new ArrayList<>();

        // 중첩 for문으로 순열 만듬
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j == i) continue;
                for (int k1 = 0; k1 < n; k1++) {
                    if (k1 == i || k1 == j) continue;

                    count++; // 하나 만들었으니까 +1

                    // count랑 원하는 k가 같으면 저장
                    if (count == k) {
                        answer.add(nums[i]);
                        answer.add(nums[j]);
                        answer.add(nums[k1]);
                        return answer;
                    }
                }
            }
        }

        return answer; // 혹시 못 찾으면 빈 리스트
    }
}

혼자서 하는 틱택토

class Solution {
    public int solution(String[] board) {
        int oCount = 0;
        int xCount = 0;

        // 1. O와 X 개수 세기
        for (int row = 0; row < 3; row++) {
            for (int col = 0; col < 3; col++) {
                char cell = board[row].charAt(col);

                if (cell == 'O') {
                    oCount++;
                } else if (cell == 'X') {
                    xCount++;
                }
            }
        }

        // 2. 턴 순서가 잘못되었는지 확인
        if (xCount > oCount) {
            return 0; // X가 먼저 둘 수는 없음
        }

        if (oCount - xCount > 1) {
            return 0; // O가 두 번 연속 둔 경우
        }

        // 3. 승리 여부 확인
        boolean oWin = checkWinner(board, 'O');
        boolean xWin = checkWinner(board, 'X');

        // 4. 말이 안 되는 상황 예외 처리

        if (oWin && xWin) {
            return 0; // 둘 다 이겼다는 건 잘못된 게임판
        }

        if (oWin && oCount != xCount + 1) {
            return 0; // O가 이기려면 O가 한 번 더 많아야 함
        }

        if (xWin && oCount != xCount) {
            return 0; // X가 이기려면 O와 X 개수가 같아야 함
        }

        // 5. 위 조건 다 통과했으면 정상적인 게임 상태
        return 1;
    }

    // 누가 이겼는지 확인하는 함수
    private boolean checkWinner(String[] board, char player) {

        // 가로 3줄 확인
        for (int row = 0; row < 3; row++) {
            if (board[row].charAt(0) == player &&
                board[row].charAt(1) == player &&
                board[row].charAt(2) == player) {
                return true;
            }
        }

        // 세로 3줄 확인
        for (int col = 0; col < 3; col++) {
            if (board[0].charAt(col) == player &&
                board[1].charAt(col) == player &&
                board[2].charAt(col) == player) {
                return true;
            }
        }

        // 대각선 (왼→오)
        if (board[0].charAt(0) == player &&
            board[1].charAt(1) == player &&
            board[2].charAt(2) == player) {
            return true;
        }

        // 대각선 (오→왼)
        if (board[0].charAt(2) == player &&
            board[1].charAt(1) == player &&
            board[2].charAt(0) == player) {
            return true;
        }

        // 이긴 경우가 없으면 false
        return false;
    }
}

[Tokwasp]

🎮 [ 혼자서 하는 틱택토 ]

💡 문제 풀이

• "O", "X" 를 9가지 경우의 수( 3 * 3 ) 완전 탐색 = 2의 9승 = 512
• 빈 틱택토 3 * 3 생성 후 탐색
• 문제에 주어진 틱택토와 같이 만들 수 있다면 성공 아닌 경우 실패

class Solution {
    private static char[][] map;
    private static char[][] originalMap;
    private static boolean isSameMap = false;
    
    public int solution(String[] board) {
        map = new char[board.length][board.length];
        originalMap = new char[board.length][board.length];
        
        // 입력 받기
        int shapeCount = 0;
        for(int i = 0; i < board.length; i++){
            String input = board[i];
            
            for(int j = 0; j < input.length(); j++){
                char shape = input.charAt(j);
                originalMap[i][j] = shape;
                
                if(shape != '.'){
                    shapeCount++;
                }
            }
        }
        
        // map 초기화
        for(int row = 0; row < map.length; row++){
            for(int col = 0; col < map[0].length; col++){
                map[row][col] = '.';
            } 
        }
        
        dfs(0, shapeCount);
        return isSameMap == true ? 1 : 0;
    }
    
    private static void dfs(int depth, int targetDepth){
        if(isSameMap == true){
            return;
        }
        
        if(depth == targetDepth || isWinner('O') || isWinner('X')){
            if(isSameMapCheck()){
                isSameMap = true;
            }
            return;
        }
        
        for(int row = 0; row < map.length; row++){
            for(int col = 0; col < map[0].length; col++){
                if(map[row][col] == '.'){
                    char shape = depth % 2 == 0 ? 'O' : 'X';
                    
                    map[row][col] = shape;
                    dfs(depth + 1, targetDepth);
                    map[row][col] = '.';
                }
            }
        }
    }
    
    private static boolean isSameMapCheck(){
        for(int row = 0; row < map.length; row++){
            for(int col = 0; col < map[0].length; col++){
                if(map[row][col] != originalMap[row][col]){
                    return false;
                }
            }
        }
        return true;
    }
    
    private static boolean isWinner(char shape){
        // 가로
        for(int row = 0; row < map.length; row++){
            if(map[row][0] == shape && map[row][1] == shape && map[row][2] == shape){
                return true;
            } 
        }
        
        // 세로
        for(int col = 0; col < map[0].length; col++){
            if(map[0][col] == shape && map[1][col] == shape && map[2][col] == shape){
                return true;
            } 
        }
        
        // 대각선
        if(map[0][0] == shape && map[1][1] == shape && map[2][2] == shape){
            return true;
        }
        if(map[0][2] == shape && map[1][1] == shape && map[2][0] == shape){
            return true;
        }
        
        return false;
    }
}

---

🧮 [ 줄 서는 방법 ]

💡 문제 풀이

• 최대 20! 이므로 완전 탐색 불가능
• 각 자리수 규칙성을 이용한 풀이

// n = 4
// 각 자리수는 뒷 자리수 경우의 수 이후에 변하게 된다. 맨 앞자리 예시를 보자.
// 1234에서 맨 앞자리 수는 1이다. 1이 2가 되려면 어떻게 해야 할까?
// 1234 -> 2134로 변할때 6가지 경우의 수 이후에 맨 앞자리가 1 -> 2로 변한다 뒤 자리수 경우의수는 3!이다.
// 3412는 몇번째 경우의 수 이후일까? 최소 3 * 3! = 18번째 이상임을 알 수 있다. 
// 1234를 0번째 기준으로 두기 때문에 k -= 1로 시작한다. 고로 3412는 22번째 수이다.
// 그렇다면 두번째 자리수 4는 어떻게 알 수 있을까?
// 남은 수는 앞자리를 결정 했으니 k = 22 - 18 = 4이다.
// 두번째 자리수는 4 / 2! = 2이다.
// 남은 수는 1 2 4 이다. 사용 하지 않은 수를 두번 지나치면 된다.
// 두번째 자리를 결정했으니 남은 수는 4 - 4 = 0이다.
// 세번째 자리는 0 / 1! = 0이다.
// 남은 수는 1 2 이다. 사용 하지 않은 수를 안지나치면 세번째 자리는 1이다.
// 네번째 자리는 자연스럽게 2가 된다 고로 답은 3412이다.

class Solution {
    public int[] solution(int maxNumber, long k) {
        int[] result = new int[maxNumber];
        
        // 숫자 사용 확인용
        boolean[] visited = new boolean[maxNumber + 1];
        k--;
        
        // 자리수 만큼 반복
        for(int seat = 0; seat < result.length; seat++){
            long divideNum = getFactorial(maxNumber - seat - 1);
            long remain = seat == result.length - 1 ? 0 : k / divideNum;
            k -= remain * divideNum;
            result[seat] = findNumber(visited, maxNumber, remain);
        }
        return result;
    }
    
    private long getFactorial(int num){
        long factorial = 1;
        while(num != 0){
            factorial *= num;
            num--;
        }
        return factorial;
    }
    
    private int findNumber(boolean[] visited, long maxNumber, long remain){
        long count = 0;
        
        for(int number = 1; number <= maxNumber; number++){
            if(!visited[number] && remain == count){
                visited[number] = true;
                return number;
            }
                
            if(!visited[number]){
                count++;
            }
        }
        return -1;
    }
}