문제 https://www.acmicpc.net/problem/1863 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 풀이 스택 자료구조를 활용한 문제입니다. stack에는 순서대로 들어오는 각 층을 쌓습니다. 여기서 조건을 잘 정리해야합니다. 우선, 스택이 비어있거나 stack의 peek이 들어올 y좌표보다 작을 때는 push를 합니다. 만약 peek이 크다면, peek이 y좌표보다 작을때마다 pop을 수행하고 pop 개수는 건물의 개수가 됩니다. 그리..
백준
문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 우선 순위 큐를 이용해 문제를 해결했습니다. 단순히 반복문 두 개로도 해결할 수는 있지만, 시간 복잡도가 300,000*300,000으로 제한 범위를 훨씬 넘어가게 됩니다. 풀이 방법은 다음과 같습니다. 1. 우선 보석을 무게에 대해 오름차순으로 정렬합니다. 그리고 무게가 같다면 가격에 대해 내림차순 정렬합니다. 2. 가방은 ..
문제 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 풀이 최소 공통 조상을 찾는 문제입니다. 위 문제는 sparse table이나 세그먼트 트리를 사용하지 않고, dfs로도 구현이 가능합니다. 우선 입력 값을 Arraylist[] 배열에 넣어 트리 상의 연결된 두 정점을 표현합니다. 그리고 parents[] 배열과 depth[] 배열을 통해 각 정점의 부모와 깊이를 저장합니다. (findDepthAndParents 메서드) 그럼 pare..
문제 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 풀이 가장 가까운 공통 조상을 찾는 문제입니다. LCA의 풀이법인, 세그먼트 트리나, Sparse table을 사용하지 않고, parents, check 배열을 통해 해결했습니다. 우선 입력이 부모와 자식이 구분되기 때문에, 입력을 받으며 해당 정점의 부모를 parents 배열에 입력합니다. 그리고 공통 조상을 구할 노드 중 하나를 pare..
문제 https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 풀이 순열이 포함된 구현 문제입니다. 처음에는, 점수를 계산하는 과정을 큐로 구현을 했습니다. Base를 돌고 홈으로 오는 선수들을 큐 자료형을 표현했는데 시간 초과가 나서, 점수를 산정하는 과정을 boolean[] 배열을 통해 경우를 따져가는 식으로 변경했습니다. 그리고 순열 시에 1번 타자는 항상 4번 째에 위치하는 것을 고려해, 해당 depth일 때는 배정을 한 칸씩 뒤로 미루었습니다. 아래..
문제 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 슬라이딩 윈도우 문제입니다. N의 input size가 30,000이기 때문에 for 문을 2번 돌게 되면 시간 제한 1초를 넘기게 됩니다. 관건은 초밥의 개수가 아닌 종류를 세야하는 것인데, 이는 Map 자료형을 통해 해결했습니다. map에서 key를 초밥의 종류로, value를 종류 당 개수로 지정해주고, 종류 카운트는 map.size를 통해 ..
