whiporithm

문제https://www.acmicpc.net/problem/2564 풀이기본적으로 bfs, 그래프 탐색으로 문제를 접근했다. 우선 점 하나를 배열의 한 칸이라고 생각해서 2차원 배열을 선언해주었다.해당 2차원 배열에는 좌표에 맞게 상점들을 위치 시킨다.상점들의 숫자 번호를 그대로 사용해서 배열에 넣어주면 된다.( 상점들의 위치는 항상 테두리에 위치하는데, 들어온 값에 따라 동서남북을 분기해주고,  그 시작점에서 거리만큼 떨어진곳에 위치시켜주면 된다.) 상점들은 최대 100번까지 있기때문에 상점이 위치한곳 빼고는 모두 101을 넣어, 상점이 위치하지 않다고 표기한다. 방문 배열 같은 경우에는, 겉 테두리만 모두 방문하지 않게 선언한다.2차원 배열이지만 실제적으로는 끝 라인들만 사용하기 때문이다. 최종적으..

문제https://www.acmicpc.net/problem/1068  풀이처음 생각한 기본 컨셉은 예시만 보고, 루트 노드에서 시작해서 식별된 "리프 노드" 들에서 지울노드에서 탐색 후 식별된 "리프 노드" 를 빼주는것이었다.  (지울노드도 포함) 하지만 이 방법으로 했을시,  1 - 2 - 3 과 같이 일직선 형태의 트리이고, (1이 root) 3를 지운다고 했을 때 루트노드에서 탐색시 리프노드는 1개이고,지울노드인 3에서도 탐색시 리프노드는 1개이다. 이 때 리프노드의 개수를 빼주면 최종적으로는 리프 노드 개수가 0개가 되는데 실상은 1 - 2 와 같이 형태가 되며, 2라는 리프노드가 하나 존재하게 된다. 이후 생각을 조금 거쳐서 실제 노드들을 삭제할까 하다가,그냥 플래그만 줘서 지우는 방식으로 분..

문제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...