6-6화이탱

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net DFS를 사용하여 해결할 수 있었다. 1->3->1 , 5->5 와 같이 2번째 값과 1번째 값이 이어지는 것들을 찾으면 된다. 1. 배열에 2번째 줄 입력 값을 넣는다. 2. 이어지는 것들을 넣을 arryList, 방문 확인할 배열을 선언한다. 3. 첫번째부터 포문을 돌려서 방문을 표시하고, 해당 인덱스(첫번째 줄 값)을 2번째 줄 값으로 갖고 있는 애들을 확인한다. import j..

https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 최단 시간을 구하는 문제로 최단 거리를 구하는 bfs를 이용하여 문제를 풀었다. 큐에 지훈이 정보, 불의 정보를 넣었다. Node 객체를 생성하여 좌표와 카운트, 지훈인지 불인지 구분하는 name을 필드로 가지게 했다. 1. 불 이동 -> 지훈 이동 2. 방문했던 위치인지 확인 3. 동서남북으로 포문 돌려서 벽과 불이 아닐 경우에는 세가지의 작업을 한다. 1)해당 좌표의 값을 바꾸..

https://www.acmicpc.net/problem/2179 2179번: 비슷한 단어 첫째 줄에 S를, 둘째 줄에 T를 출력한다. 단, 이 두 단어는 서로 달라야 한다. 즉, 가장 비슷한 두 단어를 구할 때 같은 단어는 제외하는 것이다. www.acmicpc.net ArrayList에 넣어서 비교하면 되는 문제였다. 포문에서 char배열로 변환한 후 비교했었는데 이러면 메모리 초과가 발생되었다 .. charAt으로 해당 인덱스로 잘라서 비교함으로써 해결~~~ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; public class Ma..

https://www.acmicpc.net/problem/1522 1522번: 문자열 교환 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 www.acmicpc.net a의 갯수를 세어서 그 갯수만큼의 범위를 돌면서 b의 최솟값을 찾으면 된다! aaaabbbbba 인 경우에는, a가 5개 이므로 시작 지점을 0~9(문자열 길이 10) 범위는 5 1) aaaab -> 1개 2) aaabb -> 2개 3) aabbb -> 3개 4) abbbb -> 4개 5) bbbbb -> 5개 6) bbbba -> 4개 7) bbbaa -> 3개 8) bbaaa -> 2개 9) ba..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net DFS를 사용해서 맨 첫 여행지부터 시작해서 방문가능한 곳들에 대한 확인을 한다! 여행계획대로 포문을 돌려서 방문 가능한지 본다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokeni..

https://www.acmicpc.net/problem/24337 24337번: 가희와 탑 일직선으로 다양한 높이의 건물들이 N개 존재합니다. 가희는 건물들의 왼쪽에, 단비는 건물들의 오른쪽에 있습니다. 일직선 상에 가희와 단비, 건물들은 아래와 같은 순서로 배치되어 있습니다. www.acmicpc.net 구현 문제로, 풀이법을 생각해내기 꽤 어려운 문제였다... 1. 건물의 최고 높이는 a와 b중 큰 값이다. 2. 디큐를 생성하여 a-1만큼의 오름 차순 + 최고 높이 건물 + b-1만큼의 내림차순으로 먼저 add 한다! 3. 다 add 한 후에 디큐 사이즈가 n보다 크다면, 건물 정보가 나올 수 없는 것이기에 -1을 출력한다!! 4. 여기까지 진행하면 아래와 같은 경우가 발생된다. 입력 9 1 5 -..

https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 구현문제로, 해결법을 생각해내기가 조금 어려웠다.. ArrayList iint배열을 만들어서 넣는 방식으로도 도전해봤는데 시간초과가 발생하였다.. 결국 int배열로, 입력 받을때마다 빈자리는 양보하면서 자리 배치를 하였다. 왼쪽에 2명 있다는 입력을 받으면, -> 1번째 자리가 비어있다면 한명에게 자리 양보하니까 왼쪽 (현재 왼쪽 인원수 2) -1 2번째 자리도 비어있다면 또 양보하니까 (..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 최소시간으로 bfs를 사용하여 문제를 풀었다. 1. 좌표와 시간을 가진 객체 생성 2. 큐 생성하여 시작 좌표 add 3. 0~100000 범위에서 +1, -1, *2한 좌표를 가진 객체를 큐에 add 4. k에 도달하였을때, 시간을 확인하여 최솟값 여부 확인 ! import java.io.BufferedReader; import java.io.IOExceptio..

https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 알파벳별로 개수를 저장한 다음, k개 미만인 경우에는 확인하지 않도록 한다! 그리고 k가 1일 경우의 예외처리를 해줘야 한다는 점을 주의!! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; p..

https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 1. 지름길 객체를 만들고 1) 시작 위치 오름차순 2) 끝나는 위치 오름차순 3) 거리 오름차순 으로 정렬할 수 있도록 한다. 2.ArrayList에 객체를 넣고 정렬 시킨다. 3. int배열 dp를 만들고 열의 값으로 초기화한다. 4. 지름길 갯수 만큼 포문을 돌려서 dp[시작위치]+거리를 더한 값이 기존의 dp[끝위치]보다 작을 경우, 전체 고속도로의 거리까지 포문을 돌려서 dp값..