2022-07-27 [8회차] 알고리즘 스터디

1. 카카오 프렌즈 컬러링북 - lv 2

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

프로그래머스

 

  MySol) 9.1ms

    - 전형적인 DFS알고리즘 문제이다.

<hide/>

import java.util.Arrays;

// 프로그래머스 컬러링북 - DFS

public class Test1 {

    static int[][] Direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static boolean[][] Visited;
    static int cnt = 0;

    public static int[] solution(int m, int n, int[][] picture) {

        int[] answer = new int[2];
        int numberOfArea = 0;       // 영역의 개수
        int maxSizeOfOneArea = 0;   // 가장 큰 영역의 칸 수
        Visited = new boolean[m][n];

        for(int i = 0; i < m; ++i){
            for(int j = 0;j < n; ++j){
                if(picture[i][j] != 0 && !Visited[i][j]){   // 새로운 영역이 나올 때만 DFS()메서드 적용
                    ++numberOfArea;         // 영역의 개수
                    DFS(i, j, picture);     // 같은 영역의 마지막까지 DFS 돌린다.
                }
                if(cnt > maxSizeOfOneArea){     // 더 큰 값이 나올 때마다 max에 저장한다.
                    maxSizeOfOneArea = cnt;
                }
                cnt = 0;    // DFS가 끝날 때마다 다음 영역의 칸 수를 셀 수 있도록 초기화한다.
            }
        }
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }

    public static void DFS(int _row, int _col, int[][] picture){
        Visited[_row][_col] = true;
        ++cnt;

        for(int i = 0; i < 4; ++i){
            int nextRow = _row + Direction[i][0];
            int nextCol = _col + Direction[i][1];

            if(nextRow < 0 || nextRow >= picture.length ||
               nextCol < 0 || nextCol >= picture[0].length){
                continue;
            }
            if(picture[_row][_col] == picture[nextRow][nextCol] &&
                            !Visited[nextRow][nextCol]){
                DFS(nextRow, nextCol, picture); // 다음 칸으로 넘어간다.
            }
        }
    }

    public static void main(String[] args){

        int[][] picture = {{1, 1, 1, 0}, {1, 2, 2, 0}, {1, 0, 0, 1}, {0, 0, 0, 1}, {0, 0, 0, 3}, {0, 0, 0, 3}};
        for(int a : solution(6, 4, picture)){   // 4 5
            System.out.print(a + " ");
        }
    }
}

 

  Sol) 재귀함수 - 9.32ms

    - 내가 구현한 DFS와 거의 같은데 Direction 행렬 쓰지 않는다는 점이랑 ArrayList<>에 영역의 크기를 저장하는 것만 다르다.

<hide/>

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    int span = 0;

    public int[] solution(int m, int n, int[][] picture) {

        int numberOfArea = 0;
        int maxSizeOfOneArea = 0;
        boolean[][] pathBool = new boolean[m][n];			// 방문 행렬
        ArrayList<Integer> answerList = new ArrayList<>();	// 각 영역의 개수
        int[] answer = new int[2];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j <n; j++) {
                if (picture[i][j] > 0) {
                    findPath(i, j, picture, pathBool);
                    if(span > 0){			// 각 영역의 크기마다 span에 저장
                        answerList.add(span);
                        span = 0;
                    }
                }
            }
        }
        numberOfArea = answerList.size();
        if(numberOfArea == 0){
            return new int[]{0, 0};
        }
        Collections.sort(answerList, Collections.reverseOrder());
        maxSizeOfOneArea = answerList.get(0);	// 가장 큰 영역의 값 
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }

    public void findPath(int m, int n, int[][] picture, boolean[][] pathBool) {
       
       if (pathBool[m][n] == true)
            return; 			
            
        long su = picture[m][n]; // 현재 배열 내 (m, n) 위치의 원솟값 
        int column = picture[0].length;
        int row = picture.length;
        pathBool[m][n] = true;	// 방문 처리
        span++;
        
        // m: 현재 행, n: 현재 열
        // 오른쪽 이동
        if ((n + 1 < column) && (pathBool[m][n + 1] == false && su == picture[m][n + 1])) {
            findPath(m, n + 1, picture, pathBool);
        }
        // 아래쪽 이동
        if ((m + 1 < row) && (pathBool[m + 1][n] == false && su == picture[m + 1][n])) {
            findPath(m + 1, n, picture, pathBool);
        }
        // 왼쪽 이동
        if ((n - 1 >= 0) && (pathBool[m][n - 1] == false && su == picture[m][n - 1])) {
            findPath(m, n - 1, picture, pathBool);
        }
        // 위쪽 이동
        if ((m - 1 >= 0) && (pathBool[m - 1][n] == false && su == picture[m - 1][n])) {
            findPath(m - 1, n, picture, pathBool);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int m = 4;
        int n = 4;
        int[][] picture = {
                {1,1,1,1},
                {1,4,1,1},
                {1,3,2,1},
                {1,1,1,1}};
        System.out.println(solution.solution(m, n, picture)[0] + ", " + solution.solution(m, n, picture)[1]);
    }
}

 

  Note) 유사한 문제 - 실버 1

출처 백준 단지번호 붙이기https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

  MySol) 224ms

<hide/>
// 단지번호 붙이기
import java.util.ArrayList;
import java.util.Scanner;
/*
입출력예시

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

3
7
8
9

 */

public class Practice1 {

    static int MAX_COUNT = 100;
    static int[][] AdjMat = new int[MAX_COUNT][MAX_COUNT];
    static int[][] Visited = new int[MAX_COUNT][MAX_COUNT];
    static int Width = 0;
    static int[][] DirMat = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int idx = 0;
    static ArrayList<Integer> result  = new ArrayList<>();
    static int cnt = 0; // 각 영역의 개수

    public static void DFS(int _currRow, int _currCol){

        Visited[_currRow][_currCol] = 1;
        ++cnt;

        for(int i = 0; i < 4; ++i){

            int nextRow = _currRow + DirMat[i][0];
            int nextCol = _currCol + DirMat[i][1];

            if( nextRow <= 0 || nextRow > Width ||
                nextCol <= 0 || nextCol > Width){
                continue;
            }
            
            if(AdjMat[nextRow][nextCol] == 1 && Visited[nextRow][nextCol] == 0){  // 같은 단지 내에서 DFS실행
                DFS(nextRow, nextCol);
            }
        }
    }

    public static void main(String[] args){

        Scanner scan = new Scanner(System.in);
        Width = scan.nextInt();

        for(int i = 1; i <= Width; ++i){
            String str = scan.next();
            for(int j = 1; j <= Width; ++j){
                AdjMat[i][j] = str.charAt(j - 1) - 48;
            }
        }
/*
  인접행렬 확인
        for(int i = 1; i <= Width; ++i){
            for(int j = 1; j <= Width; ++j){
                System.out.print(AdjMat[i][j] + " ");
            }
            System.out.println();
        }
 */
        for(int i = 1; i <= Width; ++i){
            for(int j = 1; j <= Width; ++j){
                if(AdjMat[i][j] == 1 && Visited[i][j] == 0){
                    DFS(i, j);
                    ++idx;
                }
                if(cnt > 0){        // 어떤 영역의 DFS을 다 돌고 나면 초기화해준다.
                    result.add(cnt);
                    cnt = 0;
                }
            }
        }
        System.out.println(idx);        // 단지의 개수
        result.sort((x, y) -> x - y);   // 오름차순
        for(int r: result){
            System.out.println(r);      //면적의 개수  정렬
        }
    }
}

    - 컬러링북은 영역의 개수, 가장 큰 영역의 크기를 반환하는데 백준(단지 번호 붙이기)문제는 영역 개수와 영역별로 크기를 모두 반환하도록 한다.

      -> DFS()를 실행한 다음의 if문에서 cntfmf result.add()한다.

   - 컬러링 북은 원소로  다양한 정숫값이 올 수 있는데 백준 문제는 0, 1로만 이루어진다는 점이 다르다.

   

 

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

 

<hide/>

class Solution {
    int[][] pic;
    Map<Integer,Integer> map = new HashMap<>();
    public int[] solution(int m, int n, int[][] picture) {
        pic = picture;
        int[] answer = new int[2];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(pic[i][j] != -1){
                    goThrough(i,j);
                }
            }
        }
        for (Map.Entry<Integer,Integer> k : map.entrySet()) {
            System.out.println(k.getKey() + " "+ k.getValue());
        }
        return answer;
    }
    public void goThrough(int row,int col){
        int[] dirs = {0,-1,0,1,0};
        int R = pic.length;
        int C = pic[0].length;
        int target = pic[row][col];

        Queue<int[]> q = new LinkedList<>();

        if(!map.containsKey(target)){
            map.put(target,0);
        }

        q.offer(new int[]{row,col});

        while(!q.isEmpty()){
            int[] cur = q.poll();
            System.out.println(Arrays.toString(cur)+" "+pic[cur[0]][cur[1]]);
            if(pic[cur[0]][cur[1]] != target) continue;
            pic[cur[0]][cur[1]] = -1;
            map.put(target,map.get(target)+1);
            for (int i = 1; i < dirs.length; i++) {
                int newR = row+dirs[i-1];
                int newC = col+dirs[i];
                if(newR<0 || newC<0 || newR >= R || newC >= C ||
                pic[newR][newC] != target)continue;
                q.offer(new int[]{newR,newC});
            }
        }

    }
}

 

 

 

2.   숫자 야구 - 완전 탐색

https://www.acmicpc.net/problem/2503

2503번: 숫자 야구

   Note) 입출력 예시

<hide/>
[입력]
4
123 1 1
356 1 0
327 2 0
489 0 1

[출력]
2

 

   Sol) 스터디원 - 88ms

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

<hide/>

class NaiveWay{
    List<Integer> possible = new ArrayList<>();
    List<StrikeAndBall> guess = new ArrayList<>();
    public void init() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        for (int i = 0; i < N; i++) {
            String[] input= bf.readLine().split(" ");
            int num = Integer.parseInt(input[0]);
            int strike = Integer.parseInt(input[1]);
            int ball = Integer.parseInt(input[2]);
            guess.add(new StrikeAndBall(strike,ball,num));
        }
    }
    public void main() throws IOException {
        init();
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= 9; j++) {
                if(i==j) continue;
                for (int k = 1; k <= 9; k++) {
                    if(j==k) continue;
                    if(i==k) continue;
                    int target = (i*100+j*10+k);//124
                    if(validate(target)){
                        possible.add(target);
                    }
                }
            }
        }
        System.out.println(possible.size());
    }
    public boolean validate(int target){ // 124
        for (StrikeAndBall cur : guess) { // 123 , 1s 1b
            if (!validCheck(target, cur))return false;
        }
        return true;
    }
    public boolean validCheck(int target,StrikeAndBall gus){
        int ball = 0;
        int strike = 0;
        String t = Integer.toString(target);
        String g = Integer.toString(gus.num);
        for (int i = 0; i < t.length(); i++) {
            for (int j = 0; j < g.length(); j++) {
                boolean b = t.charAt(i) == g.charAt(j);
                if(b && i == j){
                    strike++;
                    continue;
                }
                if(b){
                    ball++;
                }
            }
        }
        return ball == gus.ball && strike == gus.strike;
    }

    class StrikeAndBall{
        int strike;
        int ball;
        int num;
        public StrikeAndBall(int strike, int ball,int num) {
            this.strike = strike;
            this.ball = ball;
            this.num = num;
        }
    }
}

    - 서로 다른 숫자 세 자리라서 경우의수는 9 * 8 * 7=> 504

    - 123 ~ 987까지의 각 숫자에 대해 유효성 검사를 수행하도록 메서드를 작성한다.

    - 노드 StrikeAndBall 로 이뤄진 guess리스트에는 (숫자, 스트라이크 수, 볼 수)를 입력받는대로 add한다. 

    - guess의 원소들을 하나씩 유효성 검증을 해준다.

    - 최종적으로 검증을 마친 수들은 possibleList에 넣는다.

    - 1억 번이 1초라고 생각하면 504번 for문을 수행하는 것은 할만하기 때문에 완전 탐색을 이용할 수 있다.

 

  MySol) 240ms

<hide/>

import java.util.*;
class Node{
    int num;
    int strike;
    int ball;

    public Node(int num, int strike, int ball) {
        this.num = num;
        this.strike = strike;
        this.ball = ball;
    }
}
public class Test2 {
    
    static ArrayList<Integer> possible = new ArrayList<>();
    static  ArrayList<Node> guess = new ArrayList<>();

    public static boolean validate(int target){ 
        // 타겟 넘버와 노드의 정보가 일치하는지 확인
        // 각 노드에 대해 모두 검사한다.
        for(Node node : guess){
            if(!validCheck(target, node)){
                return false;
            }
        }
        return true;
    }

    public static boolean validCheck(int target,Node node){	
    // target과 node.num이 유효한지 확인

        int ball = 0;
        int strike = 0;

        String t = Integer.toString(target);
        String n = Integer.toString(node.num);

        for(int i = 0; i < t.length(); ++i){
            for(int j = 0;j < n.length(); ++j){
                if(t.charAt(i) == n.charAt(j) && i == j){    // 같은 자리에 같은 숫자가 있으면?
                    ++strike;
                    continue;
                }
                if(t.charAt(i) == n.charAt(j)){  // 자리가 다른 같은 글자가 있다면?
                    ++ball;
                }
            }
        }
        return  (strike == node.strike) && (ball == node.ball);
    }
    
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        for(int i = 0; i < n; ++i) {
            int num = scan.nextInt();
            int strike = scan.nextInt();
            int ball = scan.nextInt();
            guess.add(new Node(num, strike, ball));
        }
        
        for(int i = 1; i <= 9; ++i){	// 모든 세 자리 수를 넣어서 확인
            for(int j = 1; j<= 9; ++j){
                if(i == j){
                    continue;
                }
                for(int k = 1;k <= 9; ++k){
                    if(k == i || k == j){
                        continue;
                    }
                    int target = 100 * i + 10 * j + k;
                    if(validate(target)){
                        possible.add(target);
                    }
                }
            }
        }
        System.out.println(possible.size());
    }
}

    - 스터디원 코드 참고하여 작성했다. 스캐너를 쓰니까 시간이 조금 차이가 난다.

    - 처음에는 set에 가능한 후보들을 하나씩 추가해서 유효성 검증하는 방법을 생각했다.

    - 그래서 하나씩 넣어주는 방법을 고민하다가 풀이 시간이 금방 끝나 버렸다. 

    - 문제 가져온 분의 설명을 들으니 확실히 완전 탐색이 효과적이라는 것을 느꼈다.

    - target 넘버를 하나 정하고 각 노드에 대한 유효성 검증을 해서 통과할 경우 possible 리스트에 넣어줬다.

    - validate(int target) 메서드는 모든 노드와 target를 비교하면서 유효한 지 validCheck로 확인한다.

 

 

 

 

---

8/ 1 일요일

불참해서 내가 푼 게 없다.. 다시 꼭 풀어보자..!

 

 

3. 재귀함수가 뭔가요?

 

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

17478번: 재귀함수가 뭔가요?

 

  Sol) 문제 가져온 스터디원 블로그 - https://github.com/Gyubin0302

<hide/>

package backjoon17478;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

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

        N = Integer.parseInt(br.readLine());
        sb = new StringBuilder();
        sb.append("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n");
        sb.append("\"재귀함수가 뭔가요?\"\n");
        sb.append("\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n");
        sb.append("마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n");
        sb.append("그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n");

        recur(1);
        sb.append("라고 답변하였지.\n");
        System.out.println(sb.toString());
    }

    public static void recur(int n) {
        String s = str(n);
        sb.append(s);
        sb.append("\"재귀함수가 뭔가요?\"\n");
        
        if (n == N) {
            sb.append(s);
            sb.append("\"재귀함수는 자기 자신을 호출하는 함수라네\"\n");
            sb.append(s);
            sb.append("라고 답변하였지.\n");
            return;
        }
        
        sb.append(s);
        sb.append("\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n");
        sb.append(s);
        sb.append("마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n");
        sb.append(s);
        sb.append("그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n");
        recur(n + 1);
        sb.append(s);
        sb.append("라고 답변하였지.\n");
    }

    public static String str(int n) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            stringBuilder.append("____");
        }

        return stringBuilder.toString();
    }
}

 

 

  

4. Longest Substring Without Repeating Characters

출처 https://leetcode.com/problems/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters - LeetCode

 

  Sol) 문제 가져온 스터디원 블로그 - https://velog.io/@kormeian

<hide/>

import java.util.*;
class Solution {
    public static int lengthOfLongestSubstring(String s) {
        int i = 0;
        int j = 0;
        int maxLength = 0;
        HashSet<String> set = new HashSet<String>();

        while (i < s.length()) {
            boolean isValid = set.contains(String.valueOf(s.charAt(i)));
            if(!isValid){
                set.add(String.valueOf(s.charAt(i)));
                i++;
                maxLength = Math.max(maxLength,set.size());
            }else{
                set.remove(String.valueOf(s.charAt(j++)));
            }
        }
        return maxLength;
    }
    public static void main(String[] args)  {
        System.out.println(lengthOfLongestSubstring("pwwkew"));
    }
}