잡다한 배똥월드

class Solution {
    public long solution(int w, int h) {
        long answer = (long) w * h;
        int temp = 0;
        
        for (int i = Math.min(w, h); i >= 1; i--) {
            if (w % i == 0 && h % i == 0) {
                temp = i;
                break;
            }
        }
        
        return answer - ((w / temp) + (h / temp) - 1) * temp;
    }
}

테스트 케이스의 위 도형을 보면 대각선이 꼭지점을 지나는 부분은

( 0 0 ), ( 2 3 ), ( 4 6 ), ( 6, 9 ), ( 8 12 ) 이다.

이걸 봤을 때 가로는 2씩, 세로는 3씩 커지는 것을 볼 수 있는데

각각 가로 세로 높이를 2와 3으로 나눠보면 4라는 숫자가 나오는 것을 알 수 있다.

가로와 세로가 8과 12라는 것을 봤을 때 최대공약수인 것을 알 수 있다.

그래서 최대 공약수를 구하고

최대 공약수를 이용해서 반복하는 칸에서 대각선이 지나가는 칸을 구해야하는데

위의 예제에서도 4칸인데, 다른 도형의 경우도 계산을 해보면 반복되는 가로 길이 + 반복되는 세로 길이 - 1이라는 공식이 나온다.

최종 공식은 전체 크기 - {(가로 / 최대공약수) + (세로 / 최대공약수) - 1 } * 최대공약수 이다.

참고 링크

class Solution {
    public int solution(int[] a, int[] b) {
        int answer = 0;
        
        for (int i = 0; i < a.length; i++) {
            answer += (a[i] * b[i]);    
        }
        
        return answer;
    }
}

정말 간단한 문제여서 설명 생략.

class Solution {
    public int solution(int[] absolutes, boolean[] signs) {
        int answer = 0;
        
        for (int i = 0; i < absolutes.length; i++) {
            if (signs[i]) {
                answer += absolutes[i];
            } else {
                answer -= absolutes[i];
            }
        }
        
        return answer;
    }
}

그냥 정말 말 그대로 for문으로 돌리는데 true면 더하고 false면 뺀다..

class Solution {
    public int solution(int[] numbers) {
        int answer = 0;
        int[] arr = new int[10];
        
        for (int i = 0; i < numbers.length; i++) {
            arr[numbers[i]]++;
        }
        
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 0) { answer += i; }
        }
        
        return answer;
    }
}

9까지 있는 배열을 만들기 위해서 배열 길이는 10으로 설정

numbers를 하나씩 돌리면서 해당 숫자의 배열 위치는 1씩 값을 늘려가고...

그리고 최종적으로 배열에서 0인 값의 위치는 answer에 더해서 리턴하는 것으로...

하지만 일하면서 했기 때문에 양심적으로 2시간 내라고 인정해주라.

import java.util.*;

class Solution {
    
    int answer = 0;
    int[] numArr;
    String[][] strArr;
    boolean[] check;
    
    public int solution(int n, String[] data) {
        String[] name = {"A", "C", "F", "J", "M", "N", "R", "T"};
        String nameStr = "ACFJMNRT";
        check = new boolean[8];
        strArr = new String[n][4];
        numArr = new int[n];
        
        for (int i = 0; i < data.length; i++) {
            String[] dataArr = data[i].split("");
            
            numArr[i] = Integer.parseInt(dataArr[4]);
            strArr[i] = Arrays.copyOf(dataArr, 4);        
        }
        
        func(strArr, name, new StringBuilder());
        
        return answer;
    }
    
    public void func(String[][] data, String[] name, StringBuilder sb) {
        if (sb.length() == 8) {
            answer++;
            return;
        }
        
        for (int i = 0; i < 8; i++) {
            if (check[i]) continue;
            
            StringBuilder temp = new StringBuilder(sb);
            temp.append(name[i]);
            
            boolean value = true;
            
            for (int j = 0; j < data.length; j++) {
                if (!data[j][0].equals(name[i]) && !data[j][2].equals(name[i])) continue;
                
                int a = temp.indexOf(data[j][0]);
                int b = temp.indexOf(data[j][2]);
                
                if (a == -1 || b == -1) continue;
                
                int num = Math.abs(a - b) - 1;
                
                if (data[j][3].equals("<")) {
                    if (num >= numArr[j]) {
                        value = false;
                        break;
                    }
                } else if (data[j][3].equals(">")) {
                    if (num <= numArr[j]) {
                        value = false;
                        break;
                    }
                } else {
                    if (num != numArr[j]) {
                        value = false;
                        break;
                    }
                }
            }
            
            if (value) {
                check[i] = true;
                func(data, name, temp);
                check[i] = false;
            }
        }
    }
}

한 글자씩 추가할 때 조건들을 비교하면서 조건에 적합하면 다음으로 넘어가고 아니면 그냥 끝내는 것으로 만들었는데,

이게 가능했던게, 일단 경우의 수가 8!에 조건이 최대 100개니까 엄청 큰 숫자가 아니기 때문에

가능하겠다고 생각이 들어서 그냥 조건 전체를 돌리는 것으로 만들었음.

그리고 한 번 쓴 문자는 쓰지 않도록 boolean 배열로 체크했고,

조건에 맞는지 확인 하는 것은 어떻게 했냐면

for (int j = 0; j < data.length; j++) {
                if (!data[j][0].equals(name[i]) && !data[j][2].equals(name[i])) continue;
                
                int a = temp.indexOf(data[j][0]);
                int b = temp.indexOf(data[j][2]);
                
                if (a == -1 || b == -1) continue;
                
                int num = Math.abs(a - b) - 1;
                
                if (data[j][3].equals("<")) {
                    if (num >= numArr[j]) {
                        value = false;
                        break;
                    }
                } else if (data[j][3].equals(">")) {
                    if (num <= numArr[j]) {
                        value = false;
                        break;
                    }
                } else {
                    if (num != numArr[j]) {
                        value = false;
                        break;
                    }
                }
            }

만약에 추가할 문자가 조건식에 없다면 그냥 넘어가고

조건식에 있다면 일단 추가할 문자와 상대방 문자가 있을 것이다.

그것들의 위치를 구하는데 만약 둘 중 하나가 추가되지 않아서 indexOf에서 -1을 리턴한다면 그냥 넘어가고

그렇지 않으면 이제 각 위치와 조건식이 부합한지 확인하기 위해 if문을 돌린...

이런 식으로 작성을 했다.

import java.util.*;

class Solution {
    
    ArrayList<String> list;
    String[] word = new String[]{"A", "C", "F", "J", "M", "N", "R", "T"};
    boolean[] check = new boolean[8];
    String[][] con;
    int[] con_num;
    
    public int solution(int n, String[] data) {
        int answer = 0;
        
        Arrays.fill(check, true);
        
        list = new ArrayList<>();
        con = new String[data.length][3];
        con_num = new int[data.length];
        
        for (int i = 0; i < data.length; i++){
            String[] temp = data[i].split("");
            
            con[i][0] = temp[0];
            con[i][1] = temp[2];
            con[i][2] = temp[3];
            con_num[i] = Integer.parseInt(temp[4]);
        }
        
        funk(0, new String[8]);
                
        return list.size();
    }
    
    public void funk(int num, String[] data){
        if (num == 8){
            boolean value = true;
            
            String temp = String.join("", data);
            
            for (int i = 0; i < con.length; i++){
                int fir = temp.indexOf(con[i][0]);
                int sec = temp.indexOf(con[i][1]);
                
                int mid = Math.abs(sec - fir) - 1;
                
                if (con[i][2].equals("=")){
                    if (mid != con_num[i]){
                        value = false;
                        break;
                    }
                    continue;
                }
                
                if (con[i][2].equals(">")){
                    if (mid <= con_num[i]){
                        value = false;
                        break;
                    }
                    continue;
                }
                
                if (con[i][2].equals("<")){
                    if (mid >= con_num[i]){
                        value = false;
                        break;
                    }
                    continue;
                }
            } 
            
            if (value) list.add(temp);
            
            
            return;
        }
        
        for (int i = 0; i < word.length; i++){
            if (check[i] == false) continue;
            
            check[i] = false;
            
            data[num] = word[i];
            
            funk(num+1, data);
            
            check[i] = true;
        }
    }
}

class Solution {
    
    int numberOfArea, maxSizeOfOneArea;    
    boolean[][] check;
    
    public int[] solution(int m, int n, int[][] picture) {
        numberOfArea = 0;
        maxSizeOfOneArea = 0;
        
        check = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (picture[i][j] == 0 || check[i][j]) continue;
                
                int num = func(picture, i, j);
                
                numberOfArea++;
                maxSizeOfOneArea = Math.max(maxSizeOfOneArea, num);
            }
        }
        
        return new int[]{numberOfArea, maxSizeOfOneArea};
    }
    
    public int func(int[][] picture, int x, int y) {
        int[] xMove = {0, 0, 1, -1};
        int[] yMove = {1, -1, 0, 0};
        
        int result = 1;
        
        if (check[x][y]) return 0;
        
        check[x][y] = true;
        
        for (int i = 0; i < 4; i++) {
            if (x + xMove[i] < 0 || y + yMove[i] < 0) continue;
            if (x + xMove[i] >= picture.length  || y + yMove[i] >= picture[x].length) continue;
            if (picture[x][y] != picture[x+xMove[i]][y+yMove[i]]) continue;

            result += func(picture, x+xMove[i], y+yMove[i]);
        }
        
        return result;
    }
}

너비 우선 탐색 (BFS)

이중 for문으로 picture와 방문했는지 확인하기 위해서 만든 check를 순차적으로 확인하는데, 방문을 했는지 안했는지 체크하고 방문 안했으면 func함수를 돌린다.

func함수에서는 상하좌우 칸이 같은 숫자면 func함수에 넣어 또 함수를 돌리고.. 재귀함수같이..?

그렇게 해서 칸의 개수를 가져옴.

어차피 상하좌우 방문 안해도 자기 숫자 하나는 가져올 수 있도록 했고, 방문한 칸이면 0으로 리턴하게 만들어서 두 번 방문할 일은 없을 것이다.

예전엔 정말 어려워서 몇 시간동안 끙끙 잡고 있었는데 그래도 어떻게 푸는지 알고 있으니까 쉽게 접근할 수 있었음.

import java.util.*;

class Solution {
    public int[] solution(int m, int n, int[][] picture) {
        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;

        int[][] pic = new int[picture.length][picture[0].length];
        int[][] temp = new int[pic.length][pic[0].length];
        
        for(int i = 0; i < pic.length; i++){
            for (int j = 0; j < pic[0].length; j++){
                pic[i][j] = picture[i][j];
            }
        }
        
        for (int i = 0; i < pic.length; i++){
            for (int j = 0; j < pic[0].length; j++){
                int ans = funk(pic, temp, i, j);
                
                if (ans != 0){
                    numberOfArea++;
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, ans);
                }
            }
        }
        
        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
    
    public int funk(int[][] pic, int[][] temp, int i, int j){
        if (pic[i][j] == 0) return 0;
        
        if (temp[i][j]++ > 0) return 0;
        
        int ans = 1;
        
        if (i+1 != pic.length) {
            if (pic[i+1][j] == pic[i][j]){
                ans += funk(pic, temp, i+1, j);
            }
        }
        
        if (j+1 != pic[0].length){
            if (pic[i][j+1] == pic[i][j]){
                ans += funk(pic, temp, i, j+1);
            }
        }        
            
        if (i-1 >= 0){
            if (pic[i-1][j] == pic[i][j]){
                ans += funk(pic, temp, i-1, j);
            }
        }
        
        if (j-1 >= 0) {
            if (pic[i][j-1] == pic[i][j]){
                ans += funk(pic, temp, i, j-1);
            }
        }
        
        return ans;
    }
}

선언 방법 : 

Queue<자료형> 이름 = new LinkedList<>();

함수

- add(), offer() : 추가 함수

1. 이름.add( 내용 );
2. 이름.offer( 내용 );

- peek() : 제일 처음 추가된 값을 삭제하지 않고 조회만 하는 함수 (만약 조회할 값이 없다면 null을 리턴)

이름.peek();

- element() : 제일 처음 추가된 값을 삭제하지 않고 조회만 하는 함수 (만약 조회할 값이 없다면 예외 발생)

이름.element();

- poll() : 제일 처음 추가된 값을 꺼내면서(삭제하면서) 값을 리턴하는 함수 (만약 리턴값이 없다면 null을 리턴)

이름.poll();

- remove() : 제일 처음 추가된 값을 꺼내면서(삭제하면서) 값을 리턴하는 함수 (만약 리턴값이 없다면 예외 발생)

이름.remove();

- clear() : 큐를 전체 초기화 시키는 함수

이름.clear();

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        
        ArrayList<Queue<Integer>> map = new ArrayList<>();
        
        for (int i = 0; i < board.length; i++) {
            Queue<Integer> q = new LinkedList<>();
            
            for (int j = 0; j < board[i].length; j++) {
                if (board[j][i] == 0) continue;
                
                q.add(board[j][i]);                
            }
            
            map.add(q);
        }
        
        Stack<Integer> s = new Stack<>();
        
        for (int i = 0; i < moves.length; i++) {
            Queue<Integer> q = map.get(moves[i]-1);
            if (!q.isEmpty()) {
                int num = q.poll();
                int sNum = (!s.empty()) ? s.peek() : -1;
                
                if (sNum != -1 && num == sNum) {
                    s.pop();
                    answer += 2;
                } else {
                    s.push(num);
                }
            }
        }
        
        return answer;
    }
}

board에 들어 있는 블록을 세로 한 줄씩 정리할건데, 위에서부터 정의되어 있어서 제일 먼저 들어간 것을 꺼내는 Queue를 이용하여 정리했음.

정리한 Queue들은 ArrayList로 묶어서 map을 만들었고, moves 배열에서 하나씩 꺼내오면서 제일 마지막에 넣는 것을 꺼내는 스택으로 블록을 하나씩 넣는데, 만약 제일 위에 있는 것이 넣을 것과 같으면 스택 맨 마지막에 넣은 값을 없애고 answer에 +2를 하는 것으로 코드를 짰다.

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        
        Stack stack = new Stack();
        
        int answer = 0;
        
        for (int i = 0; i < moves.length; i++){
            int num = moves[i] - 1;
            for (int j = 0; j < board.length; j++){
                if (board[j][num] != 0){
                    if (stack.size() != 0 && (int)stack.peek() == board[j][num]){
                        stack.pop();
                        answer += 2;
                    } else {
                        stack.push(board[j][num]);
                    }
                    
                    board[j][num] = 0;
                    break;
                    
                }
            }
        }
        
        return answer;
    }
}