프로그래머스 프로세스, 퍼즐조각 채우기, 올바른 괄호

💿 프로그래머스 : 프로세스 

https://school.programmers.co.kr/learn/courses/30/lessons/42587

프로그래머스

💿 프로그래머스의 스택 / 큐 자료구조 문제에서 가져와서 풀어봤다.

💿 큐에 프로세스의 인덱스 + 우선순위를 저장해두고, 얘를 수행해도 되는지 탐색한 다음 수행가능하면 정답 배열에 해당 프로세스 우선순위를 저장한다.

💿 간단하게 구현해본 문제이다. 

💿 전체코드 

import java.util.*;
class Solution {
    public int solution(int[] priorities, int location) {
        Queue<Process> queue = new LinkedList<>();
        int[] order = new int[priorities.length];
        for (int i = 0; i < priorities.length; i++) {
            queue.add(new Process(i, priorities[i]));
        }
        
        int orderCount = 1;
        while (!queue.isEmpty()) {
            Process poll = queue.poll();
            if (isFirst(poll.order, queue)) {
                order[poll.index] = orderCount;
                orderCount++;
            } else {
                queue.add(poll);
            }
        } 
        
        return order[location];
    }
    
    public boolean isFirst(int order, Queue<Process> list) {
        Queue<Process> temp = new LinkedList<>(list);
        while (!temp.isEmpty()) {
            Process poll = temp.poll();
            if (poll.order > order) {
                return false;
            }
        }
        return true;
    }
    
    class Process {
        int index;
        int order;
        public Process(int index, int order) {
            this.index = index;
            this.order = order;
        }
    }
}

 

---

 

🧩 프로그래머스 : 퍼즐조각 채우기

https://school.programmers.co.kr/learn/courses/30/lessons/84021

프로그래머스

🧩 이런 유형의 문제를 처음 풀어봐서 너무 감이 안 왔던 문제 ... 이다. 

🧩 문제 구조는 이렇다

• 빈칸, 블록 위치를 저장한다.
  • findStart : 맨 왼쪽, 맨 위 칸을 기준점으로, 블록이나 빈칸을 찾는다.
  • BFS : 블록이나 빈칸이 나오면 해당 지점에서부터 BFS 수행, 연결된 빈칸 또는 블록들의 좌표를 저장한다.
  • setZero : 블록들 좌표 쭉 저장한다음, 비교를 위해 블록의 맨 왼쪽 위를 0,0 기준점으로 세팅
• 각 빈칸 당 알맞은 블록이 있는지 찾는다.
  • canInsert(blank, block) : blank에 block 끼울 수 있어?
    • isSame : 각 블록 / 빈칸 이루는 좌표들이 동일한지 확인
    • turnQuarter : rotate 시키면서 맞는지 안 맞는지 확인해볼 것
      • 오른쪽으로 90도씩 회전 -> (x , y)라면 (y , -x)로 좌표를 바꾸면 된다. 
      • 회전후에도 setZero로 블록 기준점 0,0으로 세팅

🧩 새로 정의한 클래스

• Pos
  • x, y좌표 저장
• Block
  • 해당 블록의 칸 수(6개를 넘지 않음)
  • 각 칸의 좌표들을 담는 Pos 배열

🧩 기타 실수한 부분

• 중간에 퍼즐을 채우면 삭제하기 위해 LinkedList를 사용한다. 
• 그런데 이때 remove하고 다시 반복문으로 들어가면 동시성 관련한 예외 터지므로 break로 블록 관련 반복문은 탈출해줘야 한다.

🧩 코드 

import java.util.*;
class Solution {
        int row;
        int col;
        public int solution(int[][] game_board, int[][] table) {
            int answer = 0;
            List<Block> blocks = new LinkedList<>();
            List<Block> blanks = new LinkedList<>();
            row = game_board.length;
            col = game_board[0].length;

            findStart(game_board, 0, blanks); // 빈칸찾기
            findStart(table, 1, blocks); // 블록찾기

            // 빈 칸 당 블록 넣을 수 있나 없나 완탐 수행
            for (Block blank : blanks) {
                for (Block block : blocks) {
                    if (canInsert(block, blank)) {
                        answer += block.count;
                        blocks.remove(block);
                        if (blocks.size() == 0) {
                            return answer;
                        }
                        break; // 필수
                    }
                }
            }

            return answer;
        }

        public void findStart(int[][] map, int find, List<Block> list) {
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (map[i][j] == find) {
                        Block block = BFS(new Pos(i, j), map, find);
                        list.add(block);
                    }
                }
            }
        }

        public Block BFS(Pos start, int[][] map, int find) {
            int[] dirX = { -1, 1, 0, 0};
            int[] dirY = { 0, 0, -1, 1};
            Queue<Pos> queue = new LinkedList<>();
            queue.add(start);
            map[start.x][start.y] = -1;
            Block block = new Block();

            while (!queue.isEmpty()) {
                Pos poll = queue.poll();
                block.list[block.count++] = poll;

                for (int i = 0; i < 4; i++) {
                    int nextX = poll.x + dirX[i];
                    int nextY = poll.y + dirY[i];

                    if (!isValid(nextX, nextY)) {
                        continue;
                    }
                    if (map[nextX][nextY] != find) {
                        continue;
                    }

                    map[nextX][nextY] = -1;
                    queue.add(new Pos(nextX, nextY));
                }
            }


            return setZero(block);
        }


        public Block setZero(Block block) {
            int minX = Integer.MAX_VALUE;
            int minY = Integer.MAX_VALUE;
            for (int i = 0; i < block.count; i++) {
                if (block.list[i].x < minX) {
                    minX = block.list[i].x;
                    minY = block.list[i].y;
                }
                else if (minX == block.list[i].x) {
                    minY = Math.min(minY, block.list[i].y);
                }
            }

            for (int i = 0; i < block.count; i++) {
                block.list[i].x -= minX;
                block.list[i].y -= minY;
            }
            return block;
        }

        public boolean canInsert(Block block, Block blank) {
            if (block.count != blank.count) {
                return false;
            }

            for (int i = 0; i < 3; i++) {
                if (isSame(block, blank)) {
                    return true;
                }
                turnQuarter(block);
            }
            if (isSame(block, blank)) {
                return true;
            }
            return false;
        }

        public boolean isSame (Block block, Block block2) {
            int count = 0;
            for (int i = 0; i < block.count; i++) {
                Pos pos = block.list[i];
                for (int j = 0; j < block2.count; j++) {
                    if (pos.x == block2.list[j].x 
                        && pos.y == block2.list[j].y) {
                        count++;
                        break;
                    } 
                }
            }
            if (count == block.count) {
                return true;
            }
            return false;
        }
    
        public void turnQuarter(Block block) {
            // (x, y) -> (y, -x)
            for (int i = 0; i < block.count; i++) {
                int temp = -block.list[i].x;
                block.list[i].x = block.list[i].y;
                block.list[i].y = temp;
            }
            setZero(block);
        }

        public boolean isValid(int x, int y) {
            if (x < 0 || x >= row || y < 0 || y >= col) {
                return false;
            }
            return true;
        }

        class Block {
            int count; // 칸 수
            Pos[] list = new Pos[6];
        }
        class Pos {
            int x;
            int y;
            public Pos(int x, int y) {
                this.x = x;
                this.y = y;
            }
        }
    }

 

---

 

🔎 프로그래머스 : 올바른 괄호 

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

🔎 안 풀어본 문제들 풀다가, 생각나서 풀어본 간단한 문제

🔎 괄호 짝만 맞는지 확인하면 된다. 

🔎 닫는 괄호가 나왔을 때 스택이 비어있거나 스택 pop 했을 때 여는 괄호가 아니라면 바로 false 리턴하면 된다. 

🔎 마지막에 스택에 원소가 남아있는 경우도 짝이 안 맞는 경우이므로, 이 경우도 마지막으로 확인하면 된다.

🔎 전체 코드 

import java.util.*;
class Solution {
    boolean solution(String s) {
        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        
        for (char c : chars) {
            if (c == '(') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                if (stack.pop() != '(') {
                    return false;
                }
            }
        }
        
        if (!stack.isEmpty()) {
            return false;
        } else {
            return true;
        }
    }
}