개발로그

풀이 먼저, 벽이 3개인 경우를 찾아 선생님 위치에서 상하좌우를 확인하도록 생각했다. 1. 벽 설치 벽이 3개가 아닌 경우 벽을 설치하도록 dfs로 구현했다. 벽이 3개가 될 경우 그래프를 탐색하면서 선생님이 위치한 좌표를 찾아 체크한다. 선생님 수 만큼 체크가 되어야 한다. (모든 선생님이 학생을 못 봐야 함.) 여기서 선생님 한명만 안보여도 통과하게 로직을 짜서 문제가 되었다. public static void dfs(int cnt) { if (cnt == 3) { // 벽이 3개가 설치된 경우 int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (graph[i][j] == 'T') { // 선생님 위치에서 학생들..

풀이 바이러스는 1번부터 순차적으로 번져간다. 순서대로 꺼내서 번지는 것을 생각하면 큐를 사용하는 것이 좋았음. 바이러스 정보를 담은 객체 (좌표와 어떤 바이러스인지) 를 1번부터 순서대로 큐에 나열한다. 그리고 꺼낼 때마다 전염 시킨다. (전염할 수 있는 조건에 맞게) (중심에 있는 바이러스는 이미 주변으로 퍼졌기 때문에 더 퍼질 수 없으니 다시 넣을 필요 없다.) 종료 조건에서 시간에 따른 종료 조건에 맞게 종료한다. 시간은 1번부터 k번까지 다 전염시킨 후에 더해진다. 큐에서 꺼내올 값의 index가 다시 1이 된 경우 시간을 증가시킨다. (peek()으로 확인하는데 큐가 NULL이면 NPE 발생하므로 먼저 비어있는지 확인하고 함) import java.util.*; class Virus imple..

최장 증가 부분 수열 전체 수열에서 만들 수 있는 부분 수열 중에 오름차순을 유지하며, 그 길이가 최대 길이인 부분 수열을 말한다. (정렬된 수열의 부분 수열을 말하는 것이 아니라, 주어진 수열의 순서에서 몇 개 원소를 제거하여 오름차순을 만든 부분 수열, 그 중에 최대 길이) 최장 증가 부분 수열의 길이 구하기 최장 증가 부분 수열의 길이를 구할 때, DP(동적 프로그래밍)을 통해 구현할 수 있다. DP 테이블을 구성하고, DP 테이블에는 각 인덱스까지 최장 증가 부분 수열의 길이를 저장한다. 1. DP 테이블은 각각 1로 초기화 한다. 각각 길이 1의 부분수열로 생각했을 때, 해당 인덱스에서 최장 길이는 1이다. 2. 부분 수열의 범위를 1씩 증가시키면서 해당 인덱스에서 최장 길이를 업데이트한다. 부..

풀이 벽을 세운 개수가 3개가 될 때마다 임시 맵에 바이러스가 퍼진 결과, 그리고 안전한 공간을 계산하도록 한다. 안전한 공간의 수는 최대값으로 갱신한다. 바이러스가 퍼지는 공간은 DFS로 면적을 포함해가면 된다. public static void virus(int x, int y) { for (int i = 0; i 0,0 0,1 n,m -> 0,0 0,2 0,3 -> ... 이렇게 모든 경우를 확인할 수 있다. 그 때 벽의 개수가 3개일 때마다 바이러스의 퍼짐 정도와 안전한 공간을 계산하면 된다. public static void dfs(int cnt) { // 벽 3개 건설된 경우 i..

문제 어떤 나라에 1~N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이때 X도시에서 출발하여 도달할 수 있는 도시 중 최단거리가 정확히 K인 모든 도시의 번호를 출력하는 프로그램 작성하시오. X 도시에서 X 도시까지의 거리는 0으로 가정한다. 입력 조건 첫째 줄에 N, M, K, X가 주어진다. 둘째 줄부터 A도시에서 B도시로 이동하는 단방향 도로 정보가 주어진다. 출력 조건 최단거리 K로 도달 할 수 있는 모든 도시를 오름차순으로 출력. 하나도 없다면 -1 출력 풀이 먼저 도로에 대한 정보가 주어지는 것을 인접리스트 방식으로 그래프화 시킨다. 도시별 최단거리를 저장할 배열을 선언한다. 처음 시작 도시 X의 거리를 0으로 지정하고, 나머지는 -1로 초기화 한다. 자료구조 ..

조합을 이용한 문제 자바에서 조합을 해결하는 방식 잘 이해할 것. 계속 공부해야함. [Algorithm] JAVA에서 조합 (Combination) 참고 자료 [Java] 조합 Combination 조합 조합이란 n 개의 숫자 중에서 r 개의 수를 순서 없이 뽑는 경우를 말한다. (위키백과 - 수학에서 조합은 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 youngssse.tistory.com import java.util.*; class Combination { private int n; // 총 치킨 집 수 private int r; // 선택하는 치킨 집 수 private int[] now; // 현재 조합 (인덱스로 저장) private ArrayList result; // 최종 조합 pu..

1. 먼저 주어진 표를 행렬로 표현하기 편하도록 아래의 그림과 같이 생각한다. y = 0 이 바닥이 되고, x = 0이 왼쪽 끝이 된다. 2. 없는 것을 삭제하거나 설치된 곳에 설치하지 않는다고 하니 검증하는 단계가 없어도 된다. 삭제와 설치에 대해서 실행하고 가능한지 판단하고 안되면 복구한다. 3. 가능한지 점검할 때는 주어진 조건에 따라 조건을 맞춰 검증한다. public boolean possible(ArrayList answer) { for (int i = 0; i < answer.size(); i++) { int x = answer.get(i).get(0); int y = answer.get(i).get(1); int stuff = answer.get(i).get(2); if (stuff == ..

프로그래머스 문제 https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 풀이 import java.util.*; class Solution { public int solution(String s) { int answer = s.length(); // 단위가 1부터 s.length() 까지 for (int len = 1; len < s.length(); len++) { // 단위별 압축된 문자열 저장 Stri..

프로그래머스 문제 https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 풀이 1. 키를 자물쇠 범위 안에 맞추지 않아도 일부만 맞아서 채워져도 된다. 자물쇠의 범위를 늘린다. 상하좌우를 늘림. (자물쇠만큼 늘려줬다.) 2. 키를 돌려가면서 맞추고자 했다. (하나의 공간에서 4개 경우의 수) 키 돌리는 메서드 작성 turn90 3. 자물쇠 범위에 키를 더하고, 체크해서 안에 합이 1로만 이루어진 경우 통과 true class Solution { public stat..

문제 알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어진다. 이때 모든 알파벳을 오름차순으로 정렬해 이어서 출력한 뒤, 모든 숫자를 더한 값을 이어서 출력한다. 입력 조건 첫째 줄에 문자열 S가 주어진다. 출력 조건 첫째 줄에 요구하는 정답을 출력한다. 풀이 1. 문자열을 입력받는다. 2. 문자열에 문자 하나하나 씩 숫자인지 문자인지 판별한다. 숫자면 sum이라는 정수형에 합으로 저장하고, 문자는 List를 정의해 저장한다. 3. 문자가 담긴 리스트를 정렬한다. 4. 결과를 담을 result에 문자를 하나씩 더한다. 그리고 마지막에 sum을 문자열로 변환해 더한다. import java.util.*; class Main { public static void main(String[] args..