문자열 문제입니다. 문자열과 폭발 문자열이 주어집니다. 문자열에 폭발 문자열과 같은 단어가 있다면 해당 문자를 지웁니다. 위의 방식을 반복하여 최종적으로 남는 문자열을 출력하는 문제입니다. 문자열의 모든 위치에서 폭발 문자열이 있는지 비교하게 된다면 O(N^2)의 시간이 걸리게 됩니다. 현재 인풋으로 받는 문자열의 최대 길이가 1,000,000 이므로 O(N^2)으로 풀게 된다면 시간초과가 발생하게 됩니다. 문자열을 차례대로 저장하고 마지막 글자가 폭발 문자열의 마지막 글자와 일치하다면 한 글자씩 비교하도록 하였습니다. 만약 모든 글자가 같다면 index를 폭발문자열 만큼 뒤로 이동해서 덮어씌우는 방식으로 문자를 입력해갔습니다. import java.io.BufferedReader; import java..
BFS 문제입니다. 로봇이 정해진 규칙대로 움직일 수 있을 때 도착지까지 최소 몇번의 명령이 필요한지 구해야합니다. 한번의 명령으로 아래의 규칙 중 하나를 수행 할 수 있습니다. 규칙 1. 보고 있는 방향으로 1칸, 2칸, 3칸 전진 2. 왼쪽 90도, 오른쪽 90도 회전 방문 배열을 만듭니다. => visit[y좌표][x좌표][방향] BFS 탐색으로 시작위치에서 규칙을 통해서 가능한 이동을 합니다. 1. 1칸 전진 2. 2칸 전진 3. 3칸 전진 4. 왼쪽 90도 회전 5. 오른쪽 90도 회전) 만약 이동을 했을 때 좌표 밖이거나 벽인 경우와 이미 방문한 경우에 대해서 처리해줍니다. 목적지에 최초로 도착했을 때 카운트값을 결과값으로 출력해주었습니다. import java.io.BufferedReader..
위상정렬 문제입니다. 작업들에는 선행순서가 있습니다. 선행순서를 실행하고 해당 작업을 실행하는 과정을 진행할 때 모든 작업이 완료되는 최소 시간을 구해야합니다. 선행순서가 없는 작업을 큐에 넣습니다. 큐에서 작업을 꺼내고 다음 위치를 탐색합니다. 다음 위치에 연결(선행이 필요한)된 작업이 있을 경우 넘어갑니다. 연결(선행이 필요한)된 작업이 없을 경우 해당 작업을 큐에 넣습니다. 위의 과정을 반복해서 모든 작업을 탐색하고 최소시간을 출력해주었습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.Outpu..
이분매칭 문제입니다. 열혈강호2와 유사한 문제입니다. https://j3sung.tistory.com/1019 [Java] 백준 11376번 열혈강호2 이분 매칭으로 문제를 해결하였습니다. N명의 직원이 있고 해야할 일이 M개가 있을 때 직원들이 할 수 있는 일들이 정해져있고 두개의 일만 할 수 있습니다. 이 때 일을 잘 분배해서 가장 많이 할 j3sung.tistory.com 상어가 속도, 사이즈, 지능이 주어질 때 다른 상어의 속도, 사이즈, 지능이 전부 같거나 작을 때 먹을 수 있습니다. 최대 2마리 까지 먹을 수 있으며 서로 먹고 먹힐 수는 없습니다. 이분매칭을 사용해서 상어들을 매칭해줍니다. 매칭 할 때 eat함수를 사용해서 해당 상어를 먹을 수 있는지 확인합니다. 먹을 수 있으면 해당 상어를 ..
이분 매칭으로 문제를 해결하였습니다. N명의 직원이 있고 해야할 일이 M개가 있을 때 직원들이 할 수 있는 일들이 정해져있고 하나의 일만 할 수 있습니다. 그리고 k만큼 직원들이 일을 추가적으로 할 수 있습니다. 이 때 일을 잘 분배해서 가장 많이 할 수 있는 일의 수를 찾는 문제입니다. A집단과 B집단을 매칭해야하는 경우이므로 이분매칭을 사용할 수 있습니다. 1. 매칭이 되어 있지 않으면 매칭 2. 매칭이 되어 있으면 매칭되어 있는 곳에서 다른 곳에 매칭이 되는지 확인 3. 불가능하면 다른 곳 매칭이 가능한지 확인 4. 모든 곳이 매칭 불가능하면 그 위치는 매칭이 안되는 곳으로 확인 각 사람에게 한개의 일을 부여하고 (각 사람을 대상으로 DFS 진행) k만큼 더 매칭이 가능한지 확인하고 가능한 경우 카..
이분 매칭으로 문제를 해결하였습니다. N명의 직원이 있고 해야할 일이 M개가 있을 때 직원들이 할 수 있는 일들이 정해져있고 K명은 2개의 일이 가능하고 나머지는 1개의 일만 할 수 있습니다. 이 때 일을 잘 분배해서 가장 많이 할 수 있는 일의 수를 찾는 문제입니다. A집단과 B집단을 매칭해야하는 경우이므로 이분매칭을 사용할 수 있습니다. 1. 매칭이 되어 있지 않으면 매칭 2. 매칭이 되어 있으면 매칭되어 있는 곳에서 다른 곳에 매칭이 되는지 확인 3. 불가능하면 다른 곳 매칭이 가능한지 확인 4. 모든 곳이 매칭 불가능하면 그 위치는 매칭이 안되는 곳으로 확인 각 사람에게 한개의 일을 부여하고 (각 사람을 대상으로 DFS 진행) 한번 더 일이 가능한지 확인합니다. (DFS 한번 더 진행) 가능한 경..
이분 매칭으로 문제를 해결하였습니다. N명의 직원이 있고 해야할 일이 M개가 있을 때 직원들이 할 수 있는 일들이 정해져있고 두개의 일만 할 수 있습니다. 이 때 일을 잘 분배해서 가장 많이 할 수 있는 일의 수를 찾는 문제입니다. A집단과 B집단을 매칭해야하는 경우이므로 이분매칭을 사용할 수 있습니다. 1. 매칭이 되어 있지 않으면 매칭 2. 매칭이 되어 있으면 매칭되어 있는 곳에서 다른 곳에 매칭이 되는지 확인 3. 불가능하면 다른 곳 매칭이 가능한지 확인 4. 모든 곳이 매칭 불가능하면 그 위치는 매칭이 안되는 곳으로 확인 각 사람당 DFS를 두번 돌리므로서 2개씩 일을 배치해 줄 수 있게 됩니다. import java.io.BufferedReader; import java.io.BufferedWr..
이분매칭 문제입니다. 각자가 일을 한개 씩 할 수 있을 때 최대한 많이 매칭시켜야 합니다. 이분 매칭 알고리즘을 사용해서 매칭을 시켜줍니다. 1. 매칭이 되어 있지 않으면 매칭 2. 매칭이 되어 있으면 매칭되어 있는 곳에서 다른 곳에 매칭이 되는지 확인 3. 불가능하면 다른 곳 매칭이 가능한지 확인 4. 모든 곳이 매칭 불가능하면 그 위치는 매칭이 안되는 곳으로 확인 위의 과정을 반복해서 모두 매칭을 하고 매칭된 수를 출력해줍니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWri..