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

비기너

문제

같은 숫자는 싫어

# 스택

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

프로그래머스

풀이

배열에서 같은 숫자가 연속해서 나오는 부분은 숫자 하나만 남기고 제거한다.

스택을 이용해서 배열의 숫자를 담고 숫자를 담을 때 스택의 탑이 담을 숫자와 같은 수라면 담지 않고 제거한다.

스택에 담긴 수를 배열로 변환하여 반환한다.

코드

import java.util.*;

public class Solution {
    public int[] solution(int []a) {
        Stack<Integer> st = new Stack<>();
        for (int i : a) {
            if (!st.isEmpty() && st.peek() == i)
                continue;
            else 
                st.push(i);
        }
        
        int[] ans = new int[st.size()];
        for (int i = st.size() - 1; i >= 0;i--)
            ans[i] = st.pop();
        
        return ans;
    }
}

미들러

문제

13417번: 카드 문자열

# 덱

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

풀이

주어진 문자를 가져가 문자열을 만들 때 사전 순으로 가장 빠른 문자열을 구하는 문제이다.

첫 번째 문자를 기준으로 양 옆에 문자를 붙여 문자열을 만들기 때문에 덱을 사용하면 된다.

덱을 사용해서 덱의 front의 문자보다 가져온 문자가 크다면 덱의 back에 집어넣고 작거나 같다면 덱의 front에 집어 넣는다.

코드

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 t = Integer.parseInt(br.readLine());

		while (t-- > 0) {
			int n = Integer.parseInt(br.readLine());
			Deque<Character> dq = new LinkedList<>();
			StringTokenizer st = new StringTokenizer(br.readLine());
			dq.addFirst(st.nextToken().charAt(0));
			for (int i = 0; i < n - 1; i++) {
				char c = st.nextToken().charAt(0);
				if (c <= dq.peekFirst())
					dq.addFirst(c);
				else
					dq.addLast(c);
			}

			for (char c : dq)
				bw.write(c);
			bw.write("\n");
		}

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

챌린저

문제

2665번: 미로만들기

# 다익스트라 # bfs

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

풀이

검은방과 흰 방으로 이루어진 맵에서 시작점에서 끝점으로 이동하기 위해 바꾸어야 할 검은 방의 최소 수를 구하는 문제이다.

2차원 배열 d를 max  값으로 초기화한다.

d에는 해당 지점까지 도달하기 위해 바꿔야하는 검은 방의 최소 수가 저장된다.

bfs를 통해서 맵을 탐색하다가 해당 지점까지 도달하기 위해 바꾸어야할 검은 방의 수가 더 작은 경로가 있다면 해당 지점의 d값을 업데이트한다.

코드

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

class Node {
	int y, x;

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

public class Main {
	static int n;
	static char[][] a;
	static int[][] d;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };

	static void bfs() {
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(0, 0));
		d[0][0] = 0;

		while (!q.isEmpty()) {
			Node node = q.poll();
			for (int i = 0; i < 4; i++) {
				int ny = node.y + dy[i];
				int nx = node.x + dx[i];
				if (ny < 0 || nx < 0 || ny >= n || nx >= n)
					continue;
				if (d[ny][nx] > d[node.y][node.x]) {
					if (a[ny][nx] == '1')
						d[ny][nx] = d[node.y][node.x];
					else
						d[ny][nx] = d[node.y][node.x] + 1;
					q.add(new Node(ny, nx));
				}
			}
		}
	}

	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());
		a = new char[n][n];
		d = new int[n][n];
		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			Arrays.fill(d[i], 1000000000);
			for (int j = 0; j < n; j++)
				a[i][j] = s.charAt(j);
		}

		bfs();

		bw.write(d[n - 1][n - 1] + "");
		bw.flush();
		bw.close();
	}
}