Java/BOJ

문제https://www.acmicpc.net/problem/3020  풀이 누적합을 이용해 해결한 문제입니다. 입력값이 2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000 으로 주어지기 때문에, 이중 for문을 돌면 바로 시간 초과에 걸리게 됩니다. 문제 상황을 위처럼 그림으로 나타내볼 수 있었습니다. 각 높이별로 파괴해야하는 장애물의 개수을 표시한 것입니다. 저 개수를 어떻게 구해야할지 생각해보다가 우선 석순과 종유석 배열을 각각 나누어야겠다고 생각했습니다.    그래서 우선 입력을 석순과 종유석(bottom[], up[])배열에 나누어서 받았습니다.이 때, 주어지는 입력 값인 장애물의 크기는  bottom[], up[] 배열의 인덱스로 입력받아, 해당하는 인덱스 배열의 값을 +1 해줍니다...

문제https://www.acmicpc.net/problem/1063 풀이 구현 문제입니다.  입력값을 어떤 형식으로 받을 것인지, 그리고 구현을 위한 메서드를 어떻게 나누고 적용할 것인지가 중요한 포인트 같습니다.  처음 구현시에 입력값도 String으로 받고 메서드를 제대로 분리하지 못했더니 너무 코드가 난잡해져서, 다시 입력 자료구조와 메서드를 정의해 문제를 해결했습니다.  우선 입력 시 char[] 배열을 통해 체스의 행과 열을 각각의 인덱스에 저장을 해주었습니다.  메서드는 크게 두 가지인데, chess를 옮기는 것과 범위를 체크하는 것입니다. 이 메서드를 king과 stone을 옮길 때 모두 사용할 수 있게끔 유연하게 만들어주었습니다.  그리고 조건에 통과해야지만, 이동된 배열 값에 업데이트를..

문제https://www.acmicpc.net/problem/18223   풀이다익스트라를 활용한 문제입니다.   일반적인 다익스트라 문제와 다른 것은, 특정한 경로를 지나칠 때를 고려해야한다는 것입니다. 특정한 경로를 지나치게하기 위해서 어떤 특별한 장치를 해야하는 것은 아니고, 그 특정 지점에서 다익스트라 알고리즘을 통해 각각의 노드까지의 최단 거리를 구해주기만 하면 됩니다.  그리고 그렇게 구한 최단 거리 배열을 통해 정답을 구할 수 있습니다. 아래는 소스 코드입니다. 소스 코드import java.util.ArrayList;import java.util.Arrays;import java.util.PriorityQueue;import java.util.Scanner;public class B1822..

문제https://www.acmicpc.net/problem/15681     풀이 서브 트리에 속한 정점의 개수를 세는 문제입니다. dfs를 통해 그래프를 탐색하며, 서브 트리의 루트가 인덱스인 배열에 정점의 개수를 저장합니다.  처음에 문제를 풀이할 때, 루트가 아닌 제일 마지막 자식부터 dfs 탐색을 시작해보려고도 했지만, 그렇게 접근하면 마지막 자식도 체크해야하고, 방문 배열을 통해 접근을 막아주어야하고.. 여러모로 로직이 복잡해집니다.  그래서 루트부터 출발해 자식으로 뻗어가며 subtrees 배열에 정점의 개수를 저장합니다. 이때 부모 노드에 자식 노드가 가진 정점의 개수를 더해주면 됩니다. 주의할 것은, 부모에서 자식으로 내려갔는데 다시 부모 노드를 검사하지 않도록 하는 것입니다. 이것은 d..

문제https://www.acmicpc.net/problem/21610 풀이 전형적인 삼성 역량 테스트의 구현 문제입니다.  우선 문제를 통해 다음의 동작으로 메서드를 구분해볼 수 있습니다. 1. 구름 이동 (moveClouds)2. 비 내리기(rain)3. 물 복사(copyWater)4. 구름 만들기(makeClouds) 각 단계별 메서드를 따라 구현을 해주면 되는데, 이 문제에서 생각해 볼 것은 1번 열과 N번 열, 그리고 1번 행과 N번 행이 연결된 것을 구현하는 것입니다. 이것은 % 연산자를 통해 간단히 구현할 수 있습니다.  그리고 이 문제의 전반적인 부분에서 조심해야하는 것은, 구름을 이동하거나 물을 복사하는 동작에서, 수정된 데이터를 사용하는 것을 주의해야합니다. 그것을 방지하기 위해 Arr..

문제https://www.acmicpc.net/problem/1240   풀이 트리에서의 탐색 문제입니다. Dfs를 이용해서 문제를 해결했습니다.  우선 Arraylist[] 배열에 입력값을 입력받습니다. 이 때, 방향은 양방향 모두 갈 수 있으니 양뱡향으로 입력 받습니다.  그리고 dfs메서드를 통해 시작점부터 탐색을 시작합니다. 한 가지 주의해야할 것은, 거리의 합을 구하는 것에 있습니다. 만약 아래와 같은 입력 값이 주어질 때를 생각해보겠습니다. 4 11 2 12 3 12 4 11 4// 정답 2  이 반례 코드에서 2는 3, 4의 두 방향으로 뻗게 됩니다. 그래서 3으로 보낸 dfs에서 거리의 합에 거리를 더하고, 그것을 바로 4로 보내게 되면 중복해서 값이 들어가게 됩니다. 그래서 한 노드에서 ..