99클럽 코테 스터디 12일차 TIL

비기너

문제

10828번 스택

# 스택

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

풀이

대부분의 언어에서 스택이 구현되어 있으므로 구현된 스택을 사용하면 되는 문제이다.

코드

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());
		Stack<Integer> stk = new Stack<>();

		while (n-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String s = st.nextToken();
			if (s.equals("push"))
				stk.push(Integer.parseInt(st.nextToken()));
			else if (s.equals("pop")) {
				if (stk.isEmpty())
					bw.write("-1\n");
				else
					bw.write(stk.pop() + "\n");
			} else if (s.equals("size"))
				bw.write(stk.size() + "\n");
			else if (s.equals("empty")) {
				if (stk.isEmpty())
					bw.write("1\n");
				else
					bw.write("0\n");
			} else {
				if (stk.isEmpty())
					bw.write("-1\n");
				else
					bw.write(stk.peek() + "\n");
			}
		}

		bw.flush();
		bw.close();
	}
}

미들러

문제

7569번: 토마토

# bfs

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

풀이

3차원의 창고에서 익은 토마토에서 익지 않은 토마토로 익는 상태가 전파되는데 모든 토마토가 익는데 걸리는 최소 시간을 구하는 문제이다.

주로 2차원 맵에서 적용했던 bfs를 3차원으로 확장시켜 적용하면 되는 문제이다.

익은 토마토를 모두 큐에 넣고 bfs를 돌린다.

bfs가 완료된 후에도 안 익은 토마토가 있다면 토마토가 모두 익지 못하는 상황이기 때문에 -1을 출력한다.

다 익었다면 visited 배열에서 가장 큰 값 - 1을 출력하면 된다.

코드

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

class Node {
	int z, y, x;

	public Node(int z, int y, int x) {
		this.z = z;
		this.y = y;
		this.x = x;
	}
}

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());
		int h = Integer.parseInt(st.nextToken());
		int[] dz = { 1, -1, 0, 0, 0, 0 };
		int[] dy = { 0, 0, 1, -1, 0, 0 };
		int[] dx = { 0, 0, 0, 0, 1, -1 };
		int[][][] a = new int[h][n][m];
		int[][][] visited = new int[h][n][m];
		Queue<Node> q = new LinkedList<>();
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < n; j++) {
				st = new StringTokenizer(br.readLine());
				for (int k = 0; k < m; k++) {
					a[i][j][k] = Integer.parseInt(st.nextToken());
					if (a[i][j][k] == 1) {
						q.add(new Node(i, j, k));
						visited[i][j][k] = 1;
					}
				}
			}
		}

		while (!q.isEmpty()) {
			Node node = q.poll();
			for (int i = 0; i < 6; i++) {
				int nz = node.z + dz[i];
				int ny = node.y + dy[i];
				int nx = node.x + dx[i];
				if (nz < 0 || ny < 0 || nx < 0 || nz >= h || ny >= n || nx >= m)
					continue;
				if (visited[nz][ny][nx] >= 1 || a[nz][ny][nx] == -1)
					continue;
				q.add(new Node(nz, ny, nx));
				visited[nz][ny][nx] = visited[node.z][node.y][node.x] + 1;
			}
		}

		int ans = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < m; k++) {
					if (visited[i][j][k] == 0 && a[i][j][k] != -1) {
						bw.write("-1");
						bw.flush();
						bw.close();
						return;
					}
					ans = Math.max(ans, visited[i][j][k]);
				}
			}
		}

		bw.write((ans - 1) + "");
		bw.flush();
		bw.close();
	}
}

챌린저

문제

도넛과 막대 그래프

# 그래프

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

프로그래머스

풀이

그래프 구조가 주어졌을 때 시작 정점과 도넛, 막대, 8자 그래프의 수를 리턴하는 문제이다.

각 그래프의 특징을 살펴보면 시작 정점은 나가는 간선만 있고 들어오는 간선은 존재하지 않는다.

막대 그래프의 마지막 정점은 들어오는 간선만 있고 나가는 간선은 존재하지 않는다.

8자 그래프에 속한 일부 정점은 나가는 간선이 2개이다.

도넛 그래프의 정점은 모두 나가는 간선이 1개이다.

따라서 간선을 맵을 이용하여 나가는 간선과 들어오는 간선으로 저장하고 각 그래프의 특징에 따라 개수를 세주면 된다.

코드

import java.util.*;

class Solution {
    
    public int[] solution(int[][] edges) {
        int[] ans = new int[4];
        HashMap<Integer, Integer> in = new HashMap<>();
        HashMap<Integer, Integer> out = new HashMap<>();
        
        for (int[] i : edges) {
            if (out.containsKey(i[0])) 
                out.put(i[0], out.get(i[0]) + 1);
            else 
                out.put(i[0], 1);
            if (in.containsKey(i[1]))
                in.put(i[1], in.get(i[1]) + 1);
            else
                in.put(i[1], 1);
        }
        
        for (int i : out.keySet()) {
            if (out.get(i) >= 2) {
                if (!in.containsKey(i))
                    ans[0] = i;
                else
                    ans[3] += 1;
            }   
        }
        
        for (int i : in.keySet()) {
            if (!out.containsKey(i))
                ans[2] += 1;
        }
        
        ans[1] = out.get(ans[0]) - ans[2] - ans[3];
        return ans;
    }
}