hwooo

https://www.acmicpc.net/problem/22866 풀이각 건물에서 볼 수 있는 건물들의 번호가 아닌 갯수만 세면 된다는 게 핵심이었다.스택을 사용하여 현재 건물에서의 왼쪽, 오른쪽으로 보이는 건물의 개수를 각각 센다.스택은 top에 가장 낮은 높이의 건물이 들어가게 정렬되어 있다. 스택 최상단의 건물의 높이(top) 이 때 스택에 남아 있는 건물들은 모두 현재 pop된 건물에서 보이므로 pop된 건물에서 보이는 건물의 개수를 스택의 크기만큼 늘려준다. 또한 스택의 top 위치의 건물이 현재 pop된 건물과 가장 가까운 위치이므로 pop된 건물에 저장된 값(nearest)와 비교해 갱신한다. 이 때 각 작업의 마지막에 위치한 인덱스(0, N - 1)는 작업에 참여하지 않으므로 한 번 더 ..

https://www.acmicpc.net/problem/16234풀이bfs로 탐색하며 인구 수의 차이가 주어진 조건 내에 들어가는 나라들끼리 묶은 후, 인구 수를 재배치했다. 각 나라가 어떤 연합인지 저장하는 배열(union)과, 각 연합이 생겼을 때 나라 별 인구 수 (총 인구 수 / 연합 나라 수)를 저장할 맵(map) 하나를 만든다.bfs로 탐색하며 각 나라 별로 연합을 결정(groupNum)하여 배열(union)에 저장한 후, 연합의 총 인구 수(sum)와 나라 수(cnt)를 구했다.이를 토대로 연합 별 인구 수(sum / cnt)를 구한 후 맵(groupNum, sum/cnt) 에 저장하였고, 인구를 이동(movePeople)시켰다.이 때 인구 수가 변경되는 나라가 하나도 없다면(isMoved..

https://www.acmicpc.net/problem/13913 풀이0~100,000까지 갈 수 있는 배열을 선언, 해당 배열에 현재 위치에 도달하게 된 경로를 저장한다.수빈이의 위치(N)를 시작점으로 놓고 이동해가며 다음 위치를 확인한다. 이 때 이미 해당 위치에 도달한 기록이 있다면 제외한다. (중복 제거)현재 위치가 K에 도달한다면 탐색을 중단하고, K부터 N까지 역으로 탐색하며 경로를 출력한다.Java 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Arrays;import java.util.Que..

https://www.acmicpc.net/problem/1806풀이입력은 모두 자연수이므로 수를 더할 수록 값은 커지기만 한다.또한 연속된 수열의 합이므로 주어진 배열의 순서를 바꾸면 안 된다.투 포인터를 활용, end 인덱스를 늘려주며 부분합을 구하다가 합이 S가 넘으면 start 인덱스를 증가시키며 S가 넘는 부분합의 최소 길이를 찾는다.Java 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { private static int N, S; private static int[] nums; public static void main(Str..

https://www.acmicpc.net/problem/1946풀이두 개의 조건을 비교해야 하므로, 먼저 서류 심사 순으로 순위를 매긴다.이렇게 되면 서류 심사는 무조건 높은 사람부터 탐색할 수 있으므로, 면접 심사 순위만 비교하면 된다.현재 지원자의 면접 심사 순위를 저장해두고, 다음 면접자의 순위가 더 높은 경우만 합격시킨다.Java 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;public class Main { private static int[] num; private static..

https://www.acmicpc.net/problem/2638풀이bfs로 탐색하며 풀었다.이 때 치즈로부터 탐색하는 게 아닌, 공기를 탐색했다.현재 셀이 공기일 때 주위에 치즈가 있는지 확인, 있다면 공기와 맞닿은 횟수를 저장해둔다.탐색 중에 치즈를 녹인다면 다른 곳을 탐색할 때 영향을 미치므로 이를 저장해두었다가 마지막에 한 번에 바꿔줬다.이 때 플래그를 사용해 녹은 치즈가 없다면 현재까지 측정한 시간을 반환한다.Java 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;public class M..

https://www.acmicpc.net/problem/16940풀이문제의 이름처럼 BFS 탐색을 하며 확인했다.입력으로 주어진 BFS 방문 순서에 따라 우선순위를 부여해 BFS 시에 참고했다.우선순위 큐를 사용, 현재 단계에 탐색 가능한 모든 노드들을 저장하되 주어진 방문 순서대로 정렬했다. 방문 순서가 올바른지 판단하는 데에는 list를 사용했다.각 단계마다 list에 값을 넣어두고, 이 또한 주어진 순서에 따라 정렬했다.이 경우 입력받은 순서가 올바르다면 list에 있는 값과 입력받은 순서가 일치해야 한다.따라서 일치하지 않는 경우는 올바르지 않다고 판단했다. 입력 받은 순서를 저장해두고, 이 값으로 가지고 온다는 건 생각하지 못 했다...작은 디테일 하나를 생각하는 연습이 더 필요한 것 같다ㅠ..

https://www.acmicpc.net/problem/10942풀이M이 최대 1,000,000개 이므로 M이 들어올 때마다 팰린드롬인지 판단할 수는 없다. (시간제한 0.5초)따라서 모든 경우의 수에 대해 팰린드롬인지 저장한 후, 범위값이 들어오면 저장된 값을 불러와야 한다. 팰린드롬이란 중간을 기준으로 인덱스를 양 방향으로 이동했을 때 값이 같아야 한다.따라서 (1, 6)가 팰린드롬이라면 (2, 5), (3, 4) 또한 팰린드롬이어야 한다.이를 바탕으로 점화식을 세운다면 dp[s][e] = dp[s + 1][e - 1] && (nums[s] == nums[e]) 가 된다.이 때 s와 e의 차이가 2 미만일 경우는 dp 검증을 제외해줬다. dp[s][e]를 구할 때 dp[s + 1][e - 1]의 값..