2022-08-28 [11회차] 알고리즘 스터디

1. 팔 - 실버1

08-28 일

출처 https://www.acmicpc.net/problem/1105

1105번: 팔

 

  MySol) ======= 미해결 코드 ========

<hide/>
import java.util.Scanner;
public class Test {

     static  int findEight(String s){
        int eightCnt = 0;
        for(char c : s.toCharArray()) {

            if (c == '8') {
                ++eightCnt;
            }
        }
        return  eightCnt;
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int L = scanner.nextInt();
        int R = scanner.nextInt();
        int minCnt = Integer.MAX_VALUE;

        String left = String.valueOf(L);
        String right = String.valueOf(R);
        
        if(left.length() != right.length()){
            System.out.println(0);
            return;
        }

        for(int i = L; i <= R; ++i){
            String s =  String.valueOf(i);
            int n = findEight(s);
            if(n < minCnt){
                minCnt = findEight(s);
            }
        }
        System.out.println(minCnt);
    }
}

    - 완전 탐색을 이용했더니 비효율적이라서 백준 통과하지 못했다.

    - if문 안에서 findEight(s) 와 minCnt를 비교하는 것보다 if문 앞에 int n =  findEight(s)을 선언한 다음 n과 minCnt를 비교하는 것이 더 좋다.

    - 그리고 minCnt의 초깃값은 MAX_INTEGER 값으로 줘야 디버그를 돌렸을 때 값이 변하는 것을 볼 수 있다.

 

 

   Sol) Gw

  스터디원 블로그  https://guiwoo.tistory.com/

class Test {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs= bf.readLine().split(" ");
        String Left = inputs[0];
        String Right = inputs[1];
        // Left<= Right;
        // 자리수가 달라 ? 그냥 뱉어
        if(Left.length() < Right.length()){
            System.out.println(0);
            return;
        }
        //두개가 같어 ? 그냥 뱉어
        if(Left.equals(Right)){
            int cnt = 0;
            for (int i = 0; i < Left.length(); i++) {
                if(Left.charAt(i) == '8') cnt++;
            }
            System.out.println(cnt);
            return;
        }
        //같은자릿수 에 Left right 앞자리부터 비교
        int idx = 0;
        int countEight = 0;
        while(idx < Left.length()){
            if(Left.charAt(idx) == Right.charAt(idx)){
                if (Left.charAt(idx) == '8') {
                    countEight++;
                }
                idx++;
            }else{
                break;
            }
        }
        System.out.println(countEight);
        return;
    }
}

    - 주어진 두 수의 자릿수가 다르면 두 수 사이에 어떤 10의 제곱수가 존재하므로 0을 반환한다.

      -> 10의 제곱수는 8이 하나도 없으니까 다음은 볼 필요도 없다.

    - 따라서 두 수의 자릿수가 같은 경우만 탐색한다.

 

 

  Sol) IA 

스터디원 블로그 -  https://velog.io/@kormeian       

<hide/>
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] s = br.readLine().split(" ");
    char[] l = s[0].toCharArray();
    char[] r = s[1].toCharArray();
    int cnt = 0;
    if (l.length == r.length) {
        for (int i = 0; i < l.length; i++) {
            if (l[i] == r[i]) {
                if (l[i] == '8') {
                    cnt ++;
                }
            }else break;
        }
    }
    System.out.println(cnt);
}

    - 초간단 코드..

    - 마찬가지로 두 개의 자릿수가 같은 경우에만 탐색한다.

    - L, R을 맨 앞에서 부터 같은 자릿수에 있는 숫자를 각각 비교하며 둘다 8이 있는 경우, 둘의 중간 값들도 그 자릿수는 8이 하나 들어가야하므로 플러스 해준다.

 

 

 

2. Number of Islands - medium (DFS, BFS )

08-29 월 

출처 https://leetcode.com/problems/number-of-islands/

Number of Islands - LeetCode

  MySol)

<hide/>
class Solution {

    static boolean[][] visited;
    static int rows;
    static int cols;
    static  int cnt = 0;
    static  int res = 0;
    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static int numIslands(char[][] grid) {
        cnt = 0;	// 이 부분을 꼭 넣어줘야한다.
        visited = new boolean[grid.length][grid[0].length];
        rows = grid.length;
        cols = grid[0].length;

        for(int i = 0;i < rows; ++i ){
            for(int j = 0; j < cols; ++j){

                if(grid[i][j] == '1' && !visited[i][j]){

                    System.out.println("DFS " + i + ", " + j);
                    DFS(i, j, grid);
                    cnt++;
                }
            // 재귀가 끝나고 다음 영역으로 순서로 넘어 갈 때
            }
        }
        return cnt;
    }

    static void DFS(int row, int col, char[][] grid){
        visited[row][col] = true;
        // System.out.println(row + ", " + col);

        for(int i = 0; i < 4; ++i){
            int nextRow = row + dir[i][0];
            int nextCol = col + dir[i][1];
            if(nextRow < 0 || rows <= nextRow ||
               nextCol < 0 || cols <= nextCol){
                continue;
            }
            if(visited[nextRow][nextCol] || grid[nextRow][nextCol] == '0' ){
                continue;
            }

            // 재귀 가능한 경우
            if(grid[nextRow][nextCol] == '1' && !visited[nextRow][nextCol]){
                DFS(nextRow, nextCol, grid);
            }
            
            // 재귀를 안 돌고 다음 위치로 이동할 때
        }
    }
    
     public static void main(String[] args) {
        char[][] grid = {
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}
        };
        System.out.println(numIslands(grid));   // 1

        grid = new char[][]{
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}
        };
        System.out.println(numIslands(grid));   // 3

        grid = new char[][]{{'1'}};
        System.out.println(numIslands(grid));   // 1
    }
}

    - static int를 이용했는데 위의 3가지 테스트 케이스를 돌리면 1, 4, 1이 나왔다.

       -> static을 이용하면 객체 생성없이 바로 사용 가능한데 1번 테스트에서의 결괏값인 1에 더해서 누적되기 때문에 정답 3이 아닌 4가 나온 것이다. 

      -> 따라서, 메서드 맨 위에 0으로 초기화 해주는 작업이 꼭 필요하다.

 

  Sol)  Gyu

<hide/>
static boolean[][] visited;
static int[] drow = {-1, 1, 0, 0};
static int[] dcol = {0, 0, -1, 1};
static int r, c;
public static int numIslands(char[][] grid) {
    int result = 0;
    r = grid.length;
    c = grid[0].length;
    visited = new boolean[r][c];

    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[i].length; j++) {
            if (!visited[i][j] && grid[i][j] == '1') {
                bfs(grid, i, j);
                result += 1;
            }
        }
    }
    return result;
}

public static void bfs(char[][] grid, int row, int col) {
    Deque<int[]> deque = new ArrayDeque<>();
    deque.offer(new int[]{row, col});
    visited[row][col] = true;
    while (!deque.isEmpty()) {
        int[] rc = deque.pollFirst();
        int nrow, ncol;
        for (int i = 0; i < drow.length; i++) {
            nrow = rc[0] + drow[i];
            ncol = rc[1] + dcol[i];
            if (nrow >= 0 && nrow < r && ncol >= 0 && ncol < c
                    && !visited[nrow][ncol] && grid[nrow][ncol] == '1') {
                deque.offer(new int[]{nrow, ncol});
                visited[nrow][ncol] = true;
            }
        }
    }
}

    - 최단거리 문제가 아니라서 당연히 DFS라고 생각했는데 이 문제는 BFS로도 구현이 가능하다는 걸 알았다.

    - 내가 푼것과 마찬가지로 if문 안에서 BFS가 끝날 때마다  result에 1을 더해주도록 한다.

    - Deque, while문 사용한 것 빼고는 내 코드와 거의 비슷하다.

 

 

 

3. 스택 수열 - 실버 2

  

08-30 화

출처 https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

  MySol) 2200ms  =(StringBuffer)=> 1030ms =(Scanner 대신 BufferedReader 이용)=> 380ms

<hide/>
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Test3 {

    public static void main(String[] args)  throws  Exception{
 //       Scanner scanner = new Scanner(System.in);/
//        ArrayList<Character> result = new ArrayList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Integer> stack = new Stack<>();
        StringBuffer sb = new StringBuffer();
        
//        int n = scanner.nextInt();
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
//            arr[i] = scanner.nextInt();     // 찾고 싶은 값
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        int idx = 0;
        for(int i = 1; i <= n; ++i){
            stack.push(i);
//            result.add('+');
            sb.append("+\n");   // 줄바꿈

            while(!stack.empty() && stack.peek() == arr[idx]){
                // 팝하고
                stack.pop();
//                result.add('-');
                sb.append("-\n");   // 줄바꿈
                ++idx;  // 다음 타겟을 찾기 위해
            }
//            System.out.println("idx " + idx  + " result " + result);
        }
        if(idx != n){
            System.out.println("NO");
            return;
        }
        System.out.println(sb);
    }
}

    - 줄바꿈을  포함해서 출력해야해서 그런지 Scanner를 이용하는 경우와 BufferedReader를 이용하는 경우의 속도 차이가 많이 난다.

    - 그리고 결괏값을 출력하기 위해 ArrayList 보다는 StringBuffer 또는 StringBuilder를 이용하는게 훨씬 효율적이다.

 

  sol) Gyu - 330ms

<hide/>
mport java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        Deque<Integer> deque = new ArrayDeque<>();
        StringBuffer sb = new StringBuffer();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        int idx = 0;
        for (int i = 1; i <= n; i++) {
            deque.offer(i);
            sb.append("+\n");
            while (!deque.isEmpty() && deque.peekLast() == arr[idx]) {
                sb.append("-\n");
                deque.pollLast();
                idx += 1;
            }
        }

        if (!deque.isEmpty()) {
            System.out.println("NO");
        } else {
            System.out.println(sb);
        }

    }
}

    - StringBuffer을 써서 그런지 시간이 훨씬 짧고 효율적이다.

    - Stack이 아닌 Deque를 이용했다는 부분 말고는 나와 로직이 거의 비슷하다.

 

 sol)  Ia

 스터디원 블로그 - https://velog.io/@kormeian

<hide/>
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] numArr = new int[n];
    StringBuilder sb = new StringBuilder();
    int crtIndex = 0;
    int crtNum = 1;

    for (int i = 0; i < n; i++) {
        numArr[i] = sc.nextInt();
    }
    ArrayDeque<Integer> stack = new ArrayDeque<Integer>();
    stack.push(crtNum++);
    sb.append("+\n");
    while (!stack.isEmpty()) {
        if (crtIndex > n) {
            System.out.println("No");
        }
        if (numArr[crtIndex] == stack.peek()) {
            crtIndex++;
            stack.pop();
            sb.append("-\n");
        } else {
            stack.push(crtNum++);
            sb.append("+\n");
        }
    }
    System.out.println(sb.toString());
}

 

 

 

4. 두 Queue의 합 같게 하기

 

08-31 수

 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

 

  MySol) 53점 - 시간 초과 해결하기

<hide/>
import java.util.*;
public class Test4 {
    public static int solution(int[] queue1, int[] queue2) {
        int answer = 0;

        long sum1 = Arrays.stream(queue1).sum();
        long sum2 = Arrays.stream(queue2).sum();

        // 더했는데 홀수인 경우
        if(sum1 % 2 == 0 && sum2 % 2 == 1 ||
           sum1 % 2 == 1 && sum2 % 2 == 0){//   더했는데 홀수면 리턴
            return -1;
        }

        long sum = sum1 + (sum2 - sum1) / 2;

        if(sum1 == sum2){
            return 0;
        }

        Queue<Integer> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();

        for(int n : queue1) q1.add(n);
        for(int n : queue2) q2.add(n);

        while(!q1.isEmpty() && !q2.isEmpty() ){

            long sumA = 0;
            for(int x : q1)  sumA += x;     // 첫번째 큐의 합 구하기

            if(sumA == sum){
                return  answer;
            }

            if(sumA > sum){
                // q1의 합이 > sum 인 경우, q1에서 뽑는다.
                int n = q1.poll();
                q2.add(n);
                ++answer;

                long tmp = 0;
                for(int x : q1){
                    tmp += x;
                }

                if(tmp == sum){
                    System.out.println("q1 " + q1);
                    System.out.println("q2 " + q2);
                    return  answer;
                }
                continue;
            }

            // queue2의 합이 더 큰 경우에는?
            int n = q2.poll();
            q1.add(n);
            ++answer;

            long tmp = 0;
            for(int x : q1){
                tmp += x;
            }
            if(tmp == sum){
                System.out.println("q1 " + q1);
                System.out.println("q2 " + q2);
                return  answer;
            }
        }

        System.out.println("q1 " + q1);
        System.out.println("q2 " + q2);
        return -1;
    }

    public static void main(String[] args) {

        int[] queue1 = {3, 2, 7, 2};
        int[] queue2 = {4, 6, 5, 1};
        System.out.println(solution(queue1, queue2));

        queue1 = new int[]{1, 2, 1, 2};
        queue2 = new int[]{1, 10, 1, 2};
        System.out.println(solution(queue1, queue2));

        // 어떻게 예외처리하지??????
        queue1 = new int[]{1, 1};
        queue2 = new int[]{1, 5};
        System.out.println(solution(queue1, queue2));   // - 1
    }
}