문제https://www.acmicpc.net/problem/2636 풀이문제의 핵심은 가장자리, 치즈의 테두리 부분을 어떻게 캐치할 것이냐이다. 문제에서 잘 보면 이미 힌트를 줬는데, 가장 끝쪽의 4면은 치즈가 존재하지 않는다. 이 말은 즉슨, 치즈 테두리 (녹을 치즈) 를 모두 탐색할 수 있다는 말이다. 가로 막힌부분이 없으니 말이다. 그렇기 때문에 끝 라인 아무곳에서  bfs 를 수행해서, 치즈의 테두리를 탐색하면 된다. 마지막의 경우 녹일 치즈가 없을것이다. 이를 대비하여 단계마다 녹일 치즈의 개수를 저장한다. -- 나는 배열 하나를 더 활용하여 녹일 치즈를 체크하고, bfs 방문 여부 모두를 체크했다. 그리고 난 후 녹일 치즈를 0 으로 바꿔주는 작업을 수행했다. 코드import java.uti..

문제https://www.acmicpc.net/problem/12891 풀이단순한 문제이다. 앞에서부터 부분문자열 만큼 range 를 잡고 그 구성에 최소한의 알파벳 개수가 있는지 체크하면 된다. 이후로 한칸씩 이동시키면서 알파벳 개수를 체크하면 된다. 투 포인터? 라고 해야할까, 앞 뒤 인덱스 각각 하나씩을 기억하고 이동시키면서 알파벳 개수 체크만 잘하면 되는 문제이다. 코드import java.util.*;import java.io.*;public class Main { public void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

문제https://www.acmicpc.net/problem/12919  풀이이 문제는 S를 T로 만들려고 하지 말고 T를 S로 만든다는 목표로 하면 풀 수 있다. 그러니까 연산을 역으로 해서 S로 갈 수 있는지 확인하는 것이다. 이유는, S에서 T로 만들 경우에는 두 연산 모든 경우의 수를 구현해봐야한다.그러나 이미 만들어진 문자열은 연산을 제한할 수 있다. 연산1 : 문자열의 뒤에 A를 추가한다.연산2 : 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다. 위와 같이 있을 때문자열의 첫번째가 B 라면 연산2를 사용해서 만들었을 수 있다.문자열의 끝이 A 라면 연산1을 사용해서 만들었을 수 있다. 이렇게 조건을 준다면 경우의 수는 훨씬 줄어든다.예로, AAA 는 연산 1만 사용해서 만들 수 있다.BAB 는..

문제https://www.acmicpc.net/problem/2607  풀이총 3개의 경우로 나눠서 생각하면 편하다.  [들어오는 값이 기준값보다 짧은 경우]짧은 경우에는 문자를 새롭게 하나 더해주는 경우의 수 밖에 없기 때문에 길이 차이는 1만 나야한다.기준값이 ABC 일 때, AB 와 같이 새로 추가할 문자열 "C" 를 제외했을 때, 문자열의 구성이 모두 같아야 한다. [들어오는 값이 기준값보다 긴 경우]긴 경우에는 문자를 하나 저게하는 경우의 수 밖에 없기 때문에 길이 차이는 1만 나야한다.기준값이 ABC 일 때,  ABDC 와 같이 제거할 문자열 "D" 를 제외했을 때, 문자열의 구성이 모두 같아야 한다.[들어오는 값이 기준값과 길이가 같은 경우]완전 구성이 똑같은 경우한 알파벳만 다른 경우한 알..

문제https://www.acmicpc.net/problem/1922  풀이진짜 그냥 크루스칼 알고리즘만 구현하면 끝이다. 코드import java.util.*;import java.io.*;public class Main { public static int[] parent; public static int totalWeight = 0; public void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int m = Integer.parse..

문제https://www.acmicpc.net/problem/4889  풀이단순히 스택을 사용하여 풀 수 있는 문제이다. 유명한 괄호 문제랑 거의 똑같은 문제긴 하다. 여는 괄호가 나오면 무조건 스택에 넣어준다. 그리고 빈 경우에 닫는 괄호라면, 여는 괄호로 바꿔줘서 넣어준다.스택에 } 이런 값이 하나 있어봤자 이 값은 여는 괄호일때만 사용할 수 있다. 그렇기 때문에 바꿔준 상태로 넣어준다. 그 외에 비지 않았는데 닫는 괄호라면, 스택에는 무조건 여는 괄호가 있기 때문에 짝이 맞는다.그렇기 때문에 여는 괄호를 빼주면 된다. 이 과정을 다 수행후에도 스택에 값이 남아있다면 이는 모두 여는 괄호일것이다. 수는 무조건 짝수로, 짝이 맞을거니까 {{{{ 이런 경우나 {{ 이런 경우가 있을것이다.하나만 닫는 괄호..

문제https://www.acmicpc.net/problem/2841  풀이맵과 우선순위큐를 활용해서 풀었다. (근데 우선순위큐 말고 스택 쓰는게 2억배는 맞는 접근이다.) Map 의 Key 는 기타줄로 하고, Value 를 플랫을 넣고 관리하는 우선순위 큐로 만든다. 플랫 같은 경우에는 같은 줄일때, 더 높은 플랫이 나오면 손가락을 추가(?)만 해주면 된다. (우선순위 큐에 플랫을 추가해주면 된다.) 단 낮은 플랫일 경우에는 입력으로 들어온 플랫보다 큰 값이 같은 줄에 있으면 안된다.따라서 우선순위 큐의 가장 큰 값을 보고 비교해본다음, 우선순위 큐의 가장 큰 값이 입력값보다 같거나 작을 때 까지 값을 빼준다. 그 다음이 중요한데, 같은 값인 경우에는 손가락을 추가해줄 필요가 없다. 이미 플랫을 짚고 ..

문제https://www.acmicpc.net/problem/6198  풀이스택을 활용해야 하는 문제이다. N이 8만이므로, 완탐은 당연히 안된다. 앞에서부터 스택에 데이터를 넣는데, 이때 빌딩번호와 높이를 같이 넣는다.다음 빌딩이 스택의 가장 위의 빌딩보다 낮으면 그냥 넣어준다. 만약 다음 빌딩이 만약 더 크다면? 스택에서 빼서, 빌딩 번호의 차를 구하고 답에 더해주면 된다. 스택에서 빼는 과정을 자신보다 낮은 빌딩이 나올때까지 반복하면 된다. 그렇게 끝까지 반복적으로 수행한다음에, 스택에 남아있다면 남아있는 빌딩들은 오른쪽 끝까지 볼 수 있는 빌딩이므로 값을 계산해서 답에 추가해주면 된다. 코드import java.util.*;import java.io.*;/** * [문제] (https://www...

문제https://www.acmicpc.net/problem/2002  풀이추월의 요점을 잘 생각해봐야한다. 난 처음에 들어가는 순서보다 나오는 순서가 빠른 순으로만 생각했는데 바로 틀렸다. 요는, 내 뒤에 있던 차량이 내 앞으로 갔는가? 이다. 게시판에 반례가 a        db        ac        cd        b 가 있었다. (왼쪽 줄이 들어간 순서, 오른쪽 줄이 나온 순서) 나오는 순서대로 체킹하면 d 하나만 체크가 될 것이다. 그러나 내 뒤에 있던 차량이 내 앞으로 간 것을 체크하면 d 와 c 2개가 있다. 우선 차량이 들어온 순서대로 리스트로 데이터를 받는다. 나가는 순서는 해쉬맵을 이용해서 로 저장한다. 해쉬맵을 이용하지 않으면 리스트에서 내 뒤에 있는 차량이 내 앞에 있는..

문제https://www.acmicpc.net/problem/14719  풀이접근을 어떻게 하다가 좀 고민하다가, 나는 가장 긴 블록 기준으로 판별했다.  가장 긴 블록을 기준으로, 아래부터 좌우를 검사하면 빈 공간 찾아내기가 용이하다. 가장 높기 때문에 좌우로 빈 공간이 보이면 카운트하고, 그러다가 같은 행에 블록이 생기면 그 사이에 생긴 빈공간을 더해주면 된다. 빈공간이 계속 나왔지만 블록이 나오지 않았다면 옆면이 없는 것이므로 더하지 않으면 된다. 나는 입력을 받고, 2차원 배열로 형태를 잡았다. 그 다음 가장 큰 블록을 가지고 있는 x 좌표에서 가장 밑의 행부터 좌우로 검사하며 위쪽으로 올라갔다.  코드import java.util.*;import java.io.*;/** * [문제] (https..