[Java] 코딩테스트 문제 리스트 (with 풀면서 배운점)

숫자문제 (소수, N진수 등)

소수 만들기

- 배운점:

소수인지 판별하는 방법: Math.sqrt(num) 과 num%i == 0 이용하여 알고리즘 짜기

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

프로그래머스

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        for(int i = 0; i < nums.length; i++){
            for(int j = i + 1; j < nums.length; j++){
                for(int k = j + 1; k < nums.length; k++){
                    int sum = nums[i] + nums[j] + nums[k];
                    boolean isPrime = true;

                    for(int l = 2; l <= Math.sqrt(sum); l++){
                        if(sum % l == 0){
                            isPrime = false;
                            break;
                        }
                    }

                    if(isPrime){
                        answer++;
                    }
                }
            }
        }
        return answer;
    }
}

 

이진변환 반복하기

배운점:

문자열 길이는 length(), 배열 길이는 length 중괄호 있고 없고 차이가 있음

toBinaryString(10진수)로 10진수 숫자를 binary로 변형가능함

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

프로그래머스

class Solution {
    public int[] solution(String s) {
        int count = 0;
        int count_zero = 0;
        String str = "";
        while (s.length() != 1){
            str = s.replace("0","");
            count_zero += s.length() - str.length();
            count++;
            s = String.valueOf(Integer.toBinaryString(str.length()));
        }

        int[] answer = {count ,count_zero};
        return answer;
    }
}

 

3진법 뒤집기

- 배운점:

String 문자열에서 index를 통해 문자를 가져오려면 String.charAt(index) 을 사용하면 됨

10진수를 N진수로 변환 String str = Integer.toString(10진수int형, N) N진수로 변환된 숫자를 문자열로 반환함

N진수를 10진수로 변환 int t = Integer.parse(N진수 숫자,N)

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

프로그래머스

class Solution {
    public int solution(int n) {
        String str = Integer.toString(n,3);
        String str_reverse = ""; 
        for(int i=str.length()-1; i>=0;i--){
            str_reverse += str.charAt(i);
        }
        n = Integer.parseInt(str_reverse,3);
        
        int answer = n;
        return answer;
    }
}

 

[1차]비밀지도

- 배운점: 비트 연산자 '|' or를 쓰면 쉽게 풀수있는 문제였다.

while문으로 공백을 정해진 length만큼 채울 수 있구나..

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

프로그래머스

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];

        for (int i = 0; i < n; i++) {
            answer[i] = Integer.toString(arr1[i] | arr2[i],2);
            answer[i] = answer[i].replace('0', ' ');
            answer[i] = answer[i].replace('1', '#');

            while (answer[i].length() < n) {
                answer[i] = ' ' + answer[i];
            }
        }
        return answer;
    }
}

---

문자열(HashMap, Stack, Queue) 문제

알파벳 찾기

- 배운점: 아래와 같이 (char)를 사용하면 문자와 숫자 연산(아스키코드)으로 Character형으로 입력할 수 있다.

for(int i =0;i<'z'-'a'+1;i++){
    hm.put((char)('a'+i),-1);
}

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

10809번: 알파벳 찾기

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        HashMap<Character,Integer> hm = new HashMap<>();
        for(int i =0;i<'z'-'a'+1;i++){
            hm.put((char)('a'+i),-1);
        }
        String words = br.readLine();

        for(int i=0;i<words.length();i++){
            char c = words.charAt(i);
            if(hm.get(c) == -1){
                hm.put(c,i);
            }
        }
        for(Character keys: hm.keySet()){
            bw.write(hm.get(keys) + " ");
        }
        bw.flush();
        bw.close();
    }
}

 

짝지어 제거하기

- 배운점: For문을 안돌리고 Stack을 사용해서 연속되는 문자를 처음부터 찾아낼수 있다.

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

프로그래머스

import java.util.*;
class Solution
{
    public int solution(String s)
    {
        int answer = 0;
        char[] arr = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for(int i=0; i<arr.length;i++){
            char c = arr[i];
            if(stack.isEmpty()){
                stack.push(c);
            }else{
                if(stack.peek() == c){
                    stack.pop();
                }else{
                    stack.push(c);
                }
            }
        }
        answer = stack.isEmpty()?1:0;
        return answer;
    }
}

 

올바른 괄호인지 검사하는 문제

- 배운점: String 으로 변환해서 비교하니까 시간초과뜸, Character 형으로 풀어서 해결

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

프로그래머스

import java.util.*;

class Solution {
    boolean solution(String s) {
        Stack<Character> stack = new Stack<>();

        if (s.charAt(0) == ')' || s.length() % 2 == 1) {
            return false;
        }

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                stack.pop();
            }
        }

        return stack.isEmpty();
    }
}

 

괄호 회전하기(맨 앞 괄호 맨뒤로 보내며 회전)

- 배운점:

문자열을 뒤로 보내는 작업을  Queue에 넣고 poll하고 add 하려고했지만, 이보다 substring으로 간단하게 해결가능함

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

프로그래머스

import java.util.*;
class Solution {
    public int solution(String s) {
        int answer = 0;
        
        for(int i=0; i< s.length();i++){
            //새로운 String을 만들어서 기존 s를 i만큼 자르고 뒤로 붙이는 작업
            String new_s = s.substring(i,s.length()) + s.substring(0,i);
            
            Stack<Character> stack = new Stack<>();
            for(int j=0; j<s.length();j++){
                //stack이 비어있을 때는 push
                if(stack.isEmpty()){
                    stack.push(new_s.charAt(j));
                }else{
                    //안 비어있을 때는 peek()와 들어갈 문자 비교
                    switch(new_s.charAt(j)){
                        case '}':
                            if(stack.peek() =='{'){
                                stack.pop();
                            }
                            break;
                        case ']': 
                            if(stack.peek() =='['){
                                stack.pop();
                            }
                            break;
                        case ')': 
                            if(stack.peek() == '('){
                                stack.pop();
                            }
                            break;
                        default: 
                            stack.push(new_s.charAt(j));
                            break;
                    }
                }
            }
            //stack이 모두 비워졌다면 카운팅
            if(stack.size() == 0){
                answer++;
            }
            
        }
        return answer;
    }
}

 

같은 숫자를 제거하는 문제

굳이 push한뒤에 pop 하기 싫어서 같으면 continue; 를 씀

stack.push() / hashMap.put() / queue.add() / srtingBuilder.append() 구분하고 외우자!

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

프로그래머스

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<arr.length;i++){
            if(!stack.isEmpty() && stack.peek() == arr[i]){
                continue;
            }else{
                stack.push(arr[i]);
            }
        }
        int[] answer = new int[stack.size()];
        int i=0;
        for(Integer item : stack){
            answer[i] = item;
            i++;
        }
        return answer;
    }
}

 

문자열 폭발(특정 문자열 지우기) Stack 문제

- 배운점:

스택을 이용하여 문자를 하나씩 push한다. 지울 문자 길이 만큼의 크기가 되었을 때부터 지울 문자와 Stack을 비교한다.

Java에는 Python처럼 index를 이용하여 문자열로 바로 뽑을 수 없기 때문에..

stack.get()과 for문을 이용하여 문자 하나 하나씩 비교해서 문자열이 같은지를 판별해야한다.

같다고 판별되었을 때는 pop()을 이용하여 지워준다.

 

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

9935번: 문자열 폭발

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter (new OutputStreamWriter(System.out));
        String str = br.readLine();
        String cut = br.readLine();

        Stack<Character> stack = new Stack<>();
        int cnt =0;
        for(int i =0; i<str.length();i++){
            stack.push(str.charAt(i));
            if(stack.size() >= cut.length()){
                int count = 0;
                for(int j=0;j<cut.length();j++){
                    if(cut.charAt(j) == stack.get(stack.size() - cut.length() + j)){
                        count++;
                    }else{
                        break;
                    }
                    if(count == cut.length()){
                        for(int k=0;k<cut.length();k++){
                            stack.pop();
                        }
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(Character item : stack){
            sb.append(item);
        }
        bw.write(sb.toString() == ""? "FRULA":sb.toString());
        bw.flush();
        bw.close();
    }
}

 

숫자 문자열과 영단어

- 배운점: HashMap<key,value> 사용법 익힘

keySet() 으로 key 값을 foreach문으로 사용할 수 있음

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

프로그래머스

import java.util.*;
class Solution {
    public int solution(String s) {
        int answer = 0;
        StringBuilder sb = new StringBuilder();
        HashMap<String,String> hm = new HashMap<>();
        hm.put("zero","0");
        hm.put("one","1");
        hm.put("two","2");
        hm.put("three","3");
        hm.put("four","4");
        hm.put("five","5");
        hm.put("six","6");
        hm.put("seven","7");
        hm.put("eight","8");
        hm.put("nine","9");
        for(String key: hm.keySet()){
            s = s.replace(key,String.valueOf(hm.get(key)));
        }
        answer = Integer.parseInt(s);
        return answer;
    }
}

 

영어 끝말잇기

- 배운점:

Arrays.copyOfRange(카피할문자열,시작범위index,끝범위index에 1을 더한 값)

Arrays.asList(문자열).contains(확인할문자)

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

프로그래머스

import java.util.*;
class Solution {
    public int[] solution(int n, String[] words) {
        int[] answer = new int[2]; // 답변 변수를 먼저 선언

        for (int i = 1; i < words.length; i++) {
            String[]forward = Arrays.copyOfRange(words,0,i);
            if ((words[i-1].charAt(words[i-1].length() - 1) != words[i].charAt(0)) ||(Arrays.asList(forward).contains(words[i])))  {
                answer[0] = (i) % n+1;
                answer[1] = (i) / n+1;
                return answer;
            }
        }

        // 마지막 단어까지 모두 조건을 만족하는 경우
        answer[0] = 0;
        answer[1] = 0;

        return answer;
    }
}

 

두개 뽑아서 더하기

- 배운점:

List는 ArrayList<>();로 생성해줘야함

List.get(index번호)로 값을 가져올 수 있음

Integer에 int 들어감

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

프로그래머스

import java.util.*;
class Solution {
    public int[] solution(int[] numbers) {
        List<Integer> list1 = new ArrayList<>();
        for(int i=0; i<numbers.length;i++){
            for(int j=i+1;j<numbers.length;j++){
                int num = numbers[i] + numbers[j];
                if(!(list1.contains(num))){
                    list1.add(num);
                }
            }
        }
        int[] answer = new int[list1.size()];
        for(int i=0;i<list1.size();i++){
            answer[i] = list1.get(i);
        }
        Arrays.sort(answer);
        return answer;
    }
}

K번째 수

- 배운점:

int[] array = Arrays.copyOfRange(array,start_index,end_index+1) 이걸로 substring처럼 배열을 자를 수 있음

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

프로그래머스

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        for (int i = 0; i < answer.length; i++) {
            int[] arr = Arrays.copyOfRange(array, commands[i][0] - 1, commands[i][1]); // 인덱스 조정
            Arrays.sort(arr); // 잘라낸 배열 정렬
            answer[i] = arr[commands[i][2] - 1]; // 정렬된 배열에서 값 가져오기
        }
        return answer;
    }
}

---

그리디(Greedy Algorithm), (탐욕 알고리즘)

거스름돈 최소 동전 갯수 구하기

- 배운점:

그리디 알고리즘 핵심은

1. 계산에 필요한 값들을 Array에 넣는다.

2. Array 값을 원하는대로 정렬하여 넣는다.

3. 정렬되어있는 Array 값을 반복문 index를 이용하여 Greedy한 값부터 차례대로 계산한다.

4. for문 안에 if 문으로 조건을 걸어 결과값을 계산을 하면된다.

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

5585번: 거스름돈

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int price = 1000 - N;
        int[] coin = {500,100,50,10,5,1};
        int count =0;
        for(int i=0;i<coin.length;i++){
            count += price/coin[i];
            price = price%coin[i];
        }
        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
    }
}

 

문자열 내 마음대로 정렬하기

- 배운점:

Arrays.sort(arr,(o1,02)->{ return o1-o2});

o1.compareTo(o2); 이것 도 리턴이 위에 sort()랑 같음

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

프로그래머스

 

import java.util.*;
class Solution {
    public String[] solution(String[] strings, int n) {
        String[] answer = new String[strings.length];
        Arrays.sort(strings,(o1,o2) -> {
            if(o1.charAt(n) == o2.charAt(n)){
                return o1.compareTo(o2);
            }
            return o1.charAt(n) - o2.charAt(n); 
        });
        
        return strings;
    }
}

 

회의실 배정

- 배운점:

Arrays.sort(array, (o1, o2) -> { return o1 - o2; }); 

• 양수 반환 (o1 - o2 > 0): 이 경우 o1이 o2보다 크다는 의미입니다. 따라서 o1이 o2보다 뒤에 위치하도록 정렬됩니다.
• 음수 반환 (o1 - o2 < 0): 이 경우 o1이 o2보다 작다는 의미입니다. 따라서 o1이 o2보다 앞에 위치하도록 정렬됩니다.
• 0 반환 (o1 - o2 == 0): 이 경우 두 객체의 값이 같다는 의미입니다. 순서에 변동이 없으며, 정렬에서는 그대로 유지됩니다.
• 즉,o1 -o2로 return 값을 줬을때 값이 양수면 바꾼다, 음수 혹은 0이면 순서를 안바꾼다. -> 내림차순이 됨
• 반대로 o2-o1 으로 return 했을때 양수면 o2가 더 크다는 소리고 양수면 o1이랑 o2랑 바꾸기 때문에 오름차순이된다.

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

1931번: 회의실 배정

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[][] numList = new int[N][2];

        for(int i=0;i<numList.length;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            numList[i][0] = Integer.parseInt(st.nextToken());
            numList[i][1] = Integer.parseInt(st.nextToken());
        }

        /*
        Arrays.sort(numList,new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2) {
                int comp = o1[1] -o2[1];
                if(comp == 0){
                    comp = o1[0] - o2[0];
                }
                return comp;
            }
        });
        아래 Arrays.sort()랑 같음*/
        
        Arrays.sort(numList,(o1,o2)->{
           if(o1[1] ==o2[1]){
               return o1[0] -o2[0];
           }
           return o1[1] - o2[1];
           //리턴 양수: o1이 앞으로감, 음수: o2가 앞으로감, 0: 변동 없음
        });

        int count = 1;
        int end = numList[0][1];
        for(int i=1;i< numList.length;i++){
            if(end <= numList[i][0]){
                end = numList[i][1];
                count++;
            }
        }

        bw.write(String.valueOf(count));
        bw.flush();
        bw.close();
    }
}

 

 

---

DFS, BFS 문제

DFS,BFS 단순 구현 문제(그래프)
- 배운점: Queue는 LinkedList<> 로 만든다.

큐에 요소 추가는 add, 요소 제거는 poll을 사용함

새로 구현된 메소드에 BufferedWriter나 Reader가 필요할때도 thorws IOException을 해줘야함

(입출력은 암기를 완료했다.)

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

1260번: DFS와 BFS

import java.io.*;
import java.util.*;
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N,M,V = 0;
    static boolean[][] graph;
    static boolean visited_BFS[];
    static boolean visited_DFS[];
    public static void DFS(int V) throws IOException{
        visited_DFS[V] = true;
        bw.write(String.valueOf(V) + " ");
        bw.flush();
        for (int i=1;i<N+1;i++){
            if(!visited_DFS[i] && graph[V][i]){
                DFS(i);
            }
        }
    }
    public static void BFS(int V) throws IOException{
        Queue<Integer> q = new LinkedList<>();
        visited_BFS[V] = true;
        q.add(V);
        while(!q.isEmpty()){
            V = q.poll();
            bw.write(String.valueOf(V) + " ");
            bw.flush();
            for(int i=1;i<N+1;i++){
                if(!visited_BFS[i]&&graph[V][i]){
                    q.add(i);
                    visited_BFS[i] = true;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        graph = new boolean[N+1][N+1];
        visited_DFS = new boolean[N+1];
        visited_BFS = new boolean[N+1];

        for (int i=0;i<M;i++){
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st2.nextToken());
            int b = Integer.parseInt(st2.nextToken());
            graph[a][b] = true;
            graph[b][a] = true;
        }
        DFS(V);
        bw.newLine();
        BFS(V);

    }
}

 

바이러스 문제

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

2606번: 바이러스

import java.io.*;
import java.util.*;
public class Main {
    static boolean[] visited;
    static boolean[][] graph;
    static int count = 0;
    static int N,M,V;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        V = 1;

        graph = new boolean[N+1][N+1];
        visited = new boolean[N+1];
        for(int i=0;i<M;i++){
            StringTokenizer str = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(str.nextToken());
            int b = Integer.parseInt(str.nextToken());
            graph[a][b] = true;
            graph[b][a] = true;
        }
        DFS(V);
        bw.write(String.valueOf(count-1));
        bw.flush();
    }
    public static void DFS(int V){
        visited[V] = true;
        count++;
        for(int i=1;i<=N;i++){
            if(graph[V][i] && !visited[i]){
                DFS(i);
            }
        }
    }
}

 

네트워크 (위 바이러스 문제랑 비슷함)

- 배운점:

for문 i랑 j 좀 실수하지말자..

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

프로그래머스

import java.util.*;
class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        int[] visited = new int[n];
        
        for(int i=0; i<n;i++){
            if(visited[i] ==0){
                answer++;
                Queue<Integer> q = new LinkedList<>();
                q.add(i);
                visited[i] = 1;
                while(!q.isEmpty()){
                    int v = q.poll();
                    for(int j=0; j<n;j++){
                        if(computers[v][j] ==1 && visited[j] ==0){
                            q.add(j);
                            visited[j] = 1;
                        }
                    }
                }
                
            }
        }
        
        return answer;
    }
}

 

게임 맵 최단거리 문제

- 배운점:

• 배열을 Queue에 넣을 때는 queue.add(new int[]{x,y}); 이렇게 넣어야함
• BFS로 visited에 지나온 거리값을 업데이트해서 도착점의 배열값을 리턴하면 그게 최단거리임

https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=java 

프로그래머스

import java.util.*;
class Solution {
    public int solution(int[][] maps){
        int[] dx = {0,0,1,-1};
        int[] dy = {1,-1,0,0};
        int[][] visited = new int[maps.length][maps[0].length];
        int x = 0;
        int y = 0;

        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});
        visited[x][y] = 1;

        while(!q.isEmpty()){
            int[] p = q.poll();
            x = p[0];
            y = p[1];
            for(int i=0;i<4;i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx >= 0 && nx < maps.length && ny >= 0 && ny < maps[0].length && (maps[nx][ny] == 1) && visited[nx][ny] == 0){
                    q.add(new int[]{nx,ny});
                    visited[nx][ny] = visited[x][y]+1;
                }
            }
        }

        int answer = visited[maps.length-1][maps[0].length-1];
        return (answer == 0) ? -1 : answer;
    }
}

 

미로 문제 (위 문제와 유사함)

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

2178번: 미로 탐색

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Integer N = Integer.parseInt(st.nextToken());
        Integer M = Integer.parseInt(st.nextToken());

        //BFS에 사용될 Queue<int[]>, 방문상태를 나타낼 visited[][]
        Queue<int[]> q = new LinkedList<>();
        int[][] visited = new int[N][M];

        //방향: {하,상,우,좌}
        int[] dx = new int[]{0,0,1,-1};
        int[] dy = new int[]{1,-1,0,0};

        //map에 1,0으로 이뤄진 지도 넣기 String으로 받은 문자열을 charAt()으로 Character형으로 바꿔준다.
        //charAt() 으로 map[i][j]을 받아오기 위함
        Character[][] map = new Character[N][M];
        for(int i=0;i<N;i++){
            String str = br.readLine();
            for(int j=0;j<M;j++){
                map[i][j] = str.charAt(j);
            }
        }

        //BFS 시작
        q.add(new int[]{0,0});
        visited[0][0] = 1;
        while(!q.isEmpty()){
            int[] c = q.poll();
            int x= c[0];
            int y = c[1];
            for(int i=0;i<4;i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx >=0 && nx <N && ny>=0 && ny <M){
                    if ((map[nx][ny] == '1') && (visited[nx][ny] == 0)) {
                        visited[nx][ny] = visited[x][y] + 1;
                        q.add(new int[]{nx,ny});
                    }
                }
            }
        }
        int result = visited[N-1][M-1];
        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
    }
}

 

가장 먼 노드 수 구하기

- 배운점:

• 깊이를 구할 때는 int[] 을 생성하여 따로 저장해두자
• 깊이 입력은 현재노드에서 접근 가능한 노드를 탐색하는 for문 안의 if문에 위치해야하며, dept[i] = dept[V]+1 로 이전 노드까지의 깊이 + 1 을 해준다.
• 이때, if문에 dept[V] == 0 을 하는 이유는 이전 노드에서 접근한적이 있는 노드는 현재노드(V)가 접근하는 깊이보다 더 짧은 깊이 이기 때문에  깊이를 변경할 수 없게 해야한다 

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

프로그래머스

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;

        boolean[] visited = new boolean[n + 1];
        boolean[][] graph = new boolean[n + 1][n + 1];
        for (int i = 0; i < edge.length; i++) {
            int a = edge[i][0];
            int b = edge[i][1];
            graph[a][b] = true;
            graph[b][a] = true;
        }
        int[] dept = new int[n + 1];
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        while (!q.isEmpty()) {
            int V = q.poll();
            visited[V] = true;
            for (int i = 1; i <= n; i++) {
                if (!visited[i] && graph[V][i] && dept[i] == 0) { // dept[i]가 0일 때만 갱신
                    q.add(i);
                    dept[i] = dept[V] + 1;
                }
            }
        }
        int max = 0;
        for (int i = 1; i <= n; i++) {
            if (max < dept[i]) {
                max = dept[i];
            }
        }
        for (int i = 1; i <= n; i++) {
            if (max == dept[i]) {
                answer++;
            }
        }

        return answer;
    }
}

 

전쟁-전투 (BFS로 섹션 찾는 유형의 문제)

- 배운점: 

DFS, BFS 학습 이후 첫코딩에 정답을 맞췄다.

배열 가로 세로에 주의해야한다.가로 N 세로 M인 문제 (보통 가로M, 세로N이다.)

시작점과 시작점에 따른 탐색을 따로 해야하는 문제 였다.

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

1303번: 전쟁 - 전투

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        char[][] graph = new char[N][M];
        int[][] visited = new int[N][M];
        for(int i=0;i<N;i++){
            String str = br.readLine();
            for(int j=0;j<M;j++){
                graph[i][j] = str.charAt(j);
            }
        }

        int[] dx = new int[]{0,0,1,-1};
        int[] dy = new int[]{1,-1,0,0};
        int W = 0;
        int B = 0;


        for(int i=0; i<N;i++){
            for(int j=0; j<M;j++){
                Queue<int[]> q = new LinkedList<>();

                if(visited[i][j]==0){
                    q.add(new int[]{i,j});
                    visited[i][j] = 1;
                    int count = 1;
                    char c = graph[i][j];

                    while(!q.isEmpty()){
                        int[] current = q.poll();
                        int x = current[0];
                        int y = current[1];


                        for(int k=0;k < 4; k++){
                            int nx = x + dx[k];
                            int ny = y + dy[k];

                            if(nx >= 0 && ny >=0 && nx<N && ny<M){
                                if(graph[nx][ny] == c && visited[nx][ny] ==0){
                                    q.add(new int[]{nx,ny});
                                    visited[nx][ny] = 1;
                                    count++;
                                }
                            }
                        }
                    }
                    count =count * count;
                    if(c == 'W'){
                        W +=count;
                    }else{
                        B +=count;
                    }
                }
            }
        }
        bw.write(String.valueOf(W));
        bw.write(" ");
        bw.write(String.valueOf(B));
        bw.flush();
        bw.close();

    }
}

단지 번호 붙이기

- 배운점:

한번에 맞춘 문제2

위 문제(전쟁-전투)와 유형이 같다.

count된 값을 List에 하나씩 넣고 size()로 단지 갯수를 구하였다.

Collections.sort(list) 로 오름차순으로 정렬을 해준 뒤, 각 단지별 건물수를 뽑으면 끝

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

2667번: 단지번호붙이기

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        char[][] graph = new char[N][N];
        int[][] visited = new int[N][N];
        int[] dx = new int[]{0,0,1,-1};
        int[] dy = new int[]{1,-1,0,0};

        for(int i =0; i<N;i++){
            String str = br.readLine();
            for(int j =0; j<N;j++){
                graph[i][j] =  str.charAt(j);
            }
        }
        List<Integer> count_list = new ArrayList<>();
        
        for(int i=0; i<N;i++){
            for(int j=0;j<N;j++){
                if(visited[i][j] == 0 &&  graph[i][j] == '1'){
                    int count = 1;
                    Queue<int[]> q = new LinkedList<>();
                    q.add(new int[]{i,j});
                    visited[i][j] = 1;
                    while(!q.isEmpty()){
                        int[] c = q.poll();
                        int x = c[0];
                        int y = c[1];
                        for(int k=0;k<4;k++){
                            int nx = x + dx[k];
                            int ny = y + dy[k];
                            if(nx >= 0 && ny >=0 && nx <N && ny < N){
                                if(visited[nx][ny] == 0 && graph[nx][ny] =='1'){
                                    q.add(new int[]{nx,ny});
                                    visited[nx][ny] = 1;
                                    count++;
                                }
                            }
                        }
                    }
                    count_list.add(count);
                }
            }
        }
        Collections.sort(count_list);
        bw.write(String.valueOf(count_list.size()));
        bw.flush();
        bw.newLine();
        for(int i=0; i< count_list.size();i++){
            bw.write(String.valueOf(count_list.get(i)));
            bw.flush();
            bw.newLine();
        }
        bw.close();

    }
}

연산자 끼워넣기

- 배운점:

백트래킹, DFS(재귀함수) 를 이용 해서 풀 수 있는 문제

Math.max(기존값, 새로운값) Math.min(기존값, 새로운값) 사용법

백트래킹 더 공부 해야할듯

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

14888번: 연산자 끼워넣기

//덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수
import java.io.*;
import java.util.*;
public class Main {
    static int N;
    static int[] numList;
    static int[] op;
    static int maxNum =Integer.MIN_VALUE;
    static int minNum =Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        numList = new int[N];
        op = new int[4];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N;i++){
            numList[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<4;i++){
            op[i] = Integer.parseInt(st.nextToken());
        }

        dfs(numList[0],1);
        //현재 index에 해당하는 숫자와 그다음 index를 para로 넘겨줌
        //즉 처음 숫자인 numList[0]과 다음 index인 1을 넘김

        bw.write(String.valueOf(maxNum));
        bw.flush();
        bw.newLine();
        bw.write(String.valueOf(minNum));
        bw.flush();
        bw.close();
    }
    public static void dfs(int num,int index){
        if(index == numList.length){
            //index가 마지막까지 도달한 경우에만 max 값과 min 값을 기존의 재귀값과 비교함
            //기존의 max, min 값보다 작거나 크다면 유지, 아니면 업데이트
            maxNum = Math.max(maxNum,num);
            minNum = Math.min(minNum,num);
            return;
        }
        for(int i=0; i<4; i++){
            //연산자 4개 만큼 for문 돌림
            if(op[i]>0){
                op[i]--;
                //연산할 수 있는 갯수가 있다면 사용한 연산자--; 하고 case별로 연산된 현재숫자와 다음 index를 재귀함수로 넘김
                switch(i){
                    case 0: dfs(num + numList[index],index+1); break;
                    case 1: dfs(num - numList[index], index+1); break;
                    case 2: dfs(num * numList[index], index+1); break;
                    case 3: dfs(num / numList[index], index+1); break;
                }
                op[i]++;
                //백트레킹을 위해 위에서 op[i]--;를 다시 ++;로 돌려놓음
            }
        }
    }
}