[코테 매일 풀기 10일차] 1118

1. 백준 9012 괄호

아이디어

• 입력받는문제: scan.next()로 String 한줄을 입력받고, 문자열 길이만큼 순회하면서 char ch = str.charAt(j)를 입력받는다.
• flage로 한번만 출력되게 한다.( ')'가 들어왔는데 비어있으면, no표시만 flag = false로 하고, 마지막 출력때 flag && stack.isEmpty()조건으로 "YES"를 출력하도록 한다.

package boj_silver.p9012_괄호;
import java.util.*;

public class Review1 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();


        for (int i = 0; i < T; i++) {
            Stack<Character> stack = new Stack<>();
            //Character ch = scan.next().charAt(0);

            //입력 처리
            String str = scan.next(); //문자열 전체를 받음
            boolean isValid = true;

            //문자 하나씩 순회하기 !!
            for (int j = 0; j<str.length(); j++){
                char ch = str.charAt(j);  //하나씩 입력받기
                if (ch =='('){
                    stack.push(ch);
                }else if(ch ==')'){
                    if(stack.isEmpty()){
//                        System.out.println("NO");
                        //no표시만
                        isValid = false;

//                        return; //main 종료 -> 전체 종료
                        break; //for문 탈출
                        //continue는 다음 반복으로 건너뛰기
                    }else{
                        stack.pop();
                    }
                }
            }

            //stack에 남아있다면
            if (isValid && stack.isEmpty()) {
                System.out.println("YES");
            } else {
                System.out.println("NO"); //또 출력되는 문제가 있네-> flag 사용
            }

        }//for
    }//main

}//class

2. 백준 21736 헌내기는 친구가 필요해

아이디어

• I를 만나는 좌표를 저장함 ! -> bfs를 I부터 시작함
• 범위 조건& 탐색 조건을 map[nx][ny] !='X'로 하고, 'P'라면 cnt++하는 방식으로 cnt를 셈.

package boj_silver.p21736_헌내기는친구가;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

//미로 탐색이다.
//nxm의 크기으 ㅣ캠퍼스가 있고,
// O : 빈공간 / X: 벽 / I: 도연이 / P: 사람
//범위 조건에 O, X를 쓰고, P를 만날때 ++ 해서 출력

//도연이가 만날수 있는 사람의 수를 출력 -> 아무도 못만난 경우 TT 출력
public class Main {
    static int n,m, cnt ;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static char[][] map;
    static boolean[][] visited;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new char[n][m];
        visited= new boolean[n][m];

        int sx =0, sy = 0;
        //map 입력 받기
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = line.charAt(j);

                //I를 만나면 bfs 시작
                if (map[i][j] == 'I'){
                    sx = i;
                    sy = j;
//                    bfs(i, j);//바로 시작하면 전부다 입력이 안됨,.
                }
            }
        }
        bfs(sx, sy);

        //System.out.println(Arrays.deepToString(map));
        if(cnt>=1){
            System.out.println(cnt);
        }else{
            System.out.println("TT");
        }
    }
    static void bfs(int x, int y){
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{x,y});
        visited[x][y] = true;
        while(!q.isEmpty()){
            int[] cur = q.poll();
            int cx = cur[0];
            int cy = cur[1];
            for (int i = 0; i<4; i++){
                int nx = cx+dx[i];
                int ny = cy+dy[i];

                if(nx>=0 && ny>=0 && nx<n && ny<m){//가장자리 범위
                    if(!visited[nx][ny] && map[nx][ny]!='X'){
                        visited[nx][ny] = true;
                        q.offer(new int[]{nx,ny});
                        if (map[nx][ny] == 'P'){
                            cnt++;
                        }
                    }
//                    if(!visited[nx][ny] && map[nx][ny] == 'P'){
//                        //P를 만났을때 처리 !!!! -> 큐에 추가해야함
//                        q.offer(new int[]{nx,ny});
//                        visited[nx][ny] = true;
//                        cnt++;
//                    }
//                    if(!visited[nx][ny] && map[nx][ny] == 'O'){
//                        q.offer(new int[]{nx,ny});
//                        visited[nx][ny] = true;
//
//                    }
                }
            }
        }

    }
}

3. 백준 7576 토마토

아이디어

• 익은 토마토(1)가 여러개 있을 수 있다 -> list로 좌표 입력 받고 , bfs에 한꺼번에 표시하기
• 벽: -1, 안익은 토마토: 0, 익은 토마토: 1 -> visited 배열 필요 없다.
• 출력은 만약 map에 0이 남아있으면, flag = flase, 아니면, max 변수에, 가장 큰 값을 넣는다.
  !flag이면 -1출력 / max -1 출력
• bfs) queue에 list에 있는 int[] 배열을 동시 추가한다.
  큐가 빌때까지 4방향 탐색을 한다. 범위: 안익은 토마토만 & 벽이 있으면 안됨. map[nx][ny] ==0 && map[nx][ny]!= -1

package boj_gold.p7576_토마토;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Review1 {
    static int n,m;
    static int[][] map;
//    static boolean [][] visited;
    static int[] dx ={-1,1,0,0};
    static int[] dy ={0,0,-1,1};
    static List<int[]> list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        map = new int[n][m];
//        visited = new boolean[n][m];

        //list에 1인 좌표를 큐에 넣기
        list = new ArrayList<>();

        //map 받기
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 1){
                    list.add(new int[]{i,j});
                }
            }
        }
        bfs(list);
//        System.out.println(Arrays.deepToString(map));
        int max= 0;
        boolean flag = true;

        //만약 0이 남아있으면 ?
        for (int i =0; i<n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    flag = false;
                }
                max = Math.max(map[i][j], max);
            }
        }
        if(!flag){
            System.out.println(-1);
        }else{
            System.out.println(max-1);
        }


    }
    static void bfs(List<int[]> list){
        Queue<int[]> q= new ArrayDeque<>();
        //동시 추가
        for (int[] pos: list){
            q.offer(pos);
        }

        while(!q.isEmpty()){
            int[] cur = q.poll();
            int cx = cur[0];
            int cy = cur[1];

            //4방향 탐색
            for(int i =0; i< 4; i++){
                int nx = cx+dx[i];
                int ny = cy+dy[i];
                if (nx >=0 && ny>=0 && nx<n && ny<m){ //범위 체크
                    //안익은 토마토만
                    if(map[nx][ny] ==0 && map[nx][ny]!= -1){
                        map[nx][ny] = map[cx][cy] + 1;
                        q.offer(new int[]{nx,ny});
                    }

                }
            }

        }
    }
}

4. 백준 1874 스택수열

아이디어

• Stack자료구조 쓰고, flag로 한꺼번에 출력 (StringBuilder)
• 입력받는 동시에 로직 작성 ! (target은 들어오는 숫자)
• cur = 1부터 시작해서, cur<=target까지 push(cur) cur++
• target이 stack.peek()과 같고, stack이 비지 않았다면, pop(); -> else flage = false break;

package boj_silver.p1847_스택수열;

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

//push 하는 순서는 반드시 오름차순 ->
public class Review1 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        StringBuilder sb = new StringBuilder();

        //배열 입력받기
//        int[] numbers = new int[n]; // -> 입력받는 동시에 비교하기
//        for (int i = 0; i<n; i++){
//            numbers[i] = scan.nextInt();
//        }

        Stack<Integer> stack = new Stack<>();
        int cur = 1;
        boolean possible = true;
        //while(cur<=target)

        for (int i = 0; i < n; i++) {
            int target= scan.nextInt();
            while(cur<=target){
                stack.push(cur);
                sb.append("+\n");
                cur++;
            }
            if(!stack.isEmpty() && target ==stack.peek()){
                stack.pop();
                sb.append("-\n");
            }else{
                possible = false;
                break; //for문 탈출
            }
        }
        if(possible){
            System.out.println(sb);
        }else{
            System.out.println("NO");
        }


    }
}

5. 백준 10773 제로

아이디어

• stack에 있는 것 다 더하기 로직 (while(!stack.isEmpty()){int num = stack.pop(); sum+= num; }

package boj_silver.p10773_제로;

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            int num = scan.nextInt();
            if(num !=0){
                stack.push(num);
            }else if(num ==0){
                stack.pop();
            }
        }
        //stack에 있는 것 다 더하기
        int sum = 0;
        while(!stack.isEmpty()){
            int num = stack.pop();
            sum += num;
        }

        System.out.println(sum);
    }
}