자료 구조37 [백준] 2517: 달리기 - JAVA https://www.acmicpc.net/problem/2517 풀이N명의 선수의 실력을 입력받는다. 입력을 받는 순서대로 해당 위치에 있다고 할 때, 실력이 자기보다 안좋은 선수가 앞에 있으면 역전할 수 있다. 예를들어 실력이 2, 8, 10으로 주어졌다면 8실력을 가진 선수는 앞에 자기보다 낮은 실력의 선수 1명이 있으므로 이 선수가 할 수 있는 최선의 등수는 1등이다. 10인 선수는 앞에 2명을 앞지를 수 있으므로 최선의 등수는 1등이 된다. 세그먼트 트리를 이용하여 실력을 tree의 인덱스로 하여 1늘린다. 1부터 자신의 인덱스까지 구간합을 구하면 자신과 자신보다 실력이 낮은 선수들의 합이 된다. 구간합과 입력받은 순서를 이용하여 최선의 등수를 계산할 수 있다. 각 선수의 실력은 모두 다르므로 .. 2024. 5. 18. [자료구조] 스택 & 큐 스택Stack 클래스에서 구현된 메서드는 다음과 같다. - `E push(E item)`: 스택의 맨 위에 요소를 추가한다. - `E pop()`: 스택의 맨 위 요소를 제거하고 제거된 요소를 반환한다. - `E peek()`: 스택의 맨 위 요소를 제거하지 않고 반환한다. - `boolean empty()`: 현재 스택에 요소가 존재하지 않을 경우 `true`, 그 외의 경우 `false`를 반환한다. - `int search(Object o)`: 스택의 상단부터 탐색하여 지정된 객체가 있는 요소의 위치를 반환한다. 없을 경우 `-1`을 반환한다. 스택은 먼저 들어온 데이터가 마지막에 나가는 구조이다. 페이지 뒤로가기, 실행 취소, 수식 괄호검사 등에서 응용된다. Stack 클래스는 .. 2024. 5. 18. [백준] 16120: PPAP - JAVA https://www.acmicpc.net/problem/16120 풀이문자열을 앞에서부터 보면서 'PPAP'가 되면 'P'로 바꿔준다. 최종적으로 'P'가 되면 성공. P가 들어오면 cnt를 1 늘려준다. A가 들어올 때 cnt가 2보다 작다면 PPAP를 만들수 없으므로 실패. cnt가 2이상이고, 다음 글자가 P라면 PPAP를 만들 수 있으므로, cnt를 1 줄여준다(P가 2개 빠지고 새로운 P가 들어오기 때문). 메모리: 20080KB시간: 260ms언어: Java 11import java.io.*;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new .. 2024. 5. 18. [백준] 19598: 최소 회의실 개수 - JAVA https://www.acmicpc.net/problem/19598 풀이회의의 시작, 종료 시간이 주어지고 최의실을 배정해야 한다. 회의실의 개수를 최소로 해야한다. 시작시간 순으로 정렬을해서 차례대로 회의실에 집어넣었다. 우선순위큐에 종료시간을 넣고, 우선순위큐의 peek이 새로 들어갈 회의의 시작시간보다 작다면 그 방을 사용할 수 있다. 메모리: 48764KB시간: 668ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputS.. 2024. 5. 17. [백준] 13335: 트럭 - JAVA https://www.acmicpc.net/problem/13335 풀이n개의 트럭이 길지 w의 다리를 건너는데 1을 가는데 1의 시간이 소요되고 다리가 견딜 수 있는 무게는 L이다. 다리 위에 L넘게 올라갈 수없다. 먼저 간 트럭이 다리를 벗어날 때까지 기다려야한다. 큐에 다리위에 있는 트럭들을 저장하고 sum에 트럭의 무게를 더해줬다. 큐에 넣을 때 다리를 벗어나는 시간까지 같이 넣어주었다. 시간을 늘리면서 큐의 맨 앞에 있는 트럭이 다리를 벗어날 시간이라면 큐에서 삭제, sum에서 무게를 빼주었다. `sum + 다음에 들어올 트럭의 무게`가 L보다 작거나 같으면 큐에 트럭을 넣어주었다. 메모리: 14444KB시간: 136ms언어: Java 11import java.util.*;import java.. 2024. 5. 17. [백준] 23883: 알고리즘 수업 - 선택 정렬 3 - JAVA https://www.acmicpc.net/problem/23883 풀이선택정렬은 O(n^2)의 시간복잡도를 갖기때문에 그대로 구현하면 시간초과가 났다. 따라서 정렬이 되는 TreeMap을 이용했다. TreeMap에 숫자와 처음 인덱스를 넣고 뒤에서 부터 꺼내면서 인덱스 교체가 필요할 경우 교체해주었다. 메모리: 122416KB시간: 1564ms언어: Java 11import java.util.*;import java.io.*;public class Main { static int[] arr; static int N, K, cnt, ans_a, ans_b; public static void main(String[] args) throws Exception { Buffered.. 2024. 5. 17. [백준] 22866: 탑 보기 - JAVA https://www.acmicpc.net/problem/22866 풀이N개의 건물의 높이가 주어진다. 각 건물의 옥상에서 양 옆을 볼 때, 현재있는 건물의 높이보다 큰 건물만 볼수있고, 큰 건물로 가려지면 볼 수 없다. 스택을 이용해 저장하면서 현재 빌딩보다 낮으면 없애주는 식으로 구현했다. 왼쪽부터, 오른쪽부터 두번에 걸쳐 스택에 저장하는 과정을 거쳤다. 왼쪽부터 진행할 때는 현재 건물의 왼쪽을 본다는 것이고 오른쪽부터 진행하면 오른쪽을 본다는 것이다. 메모리: 34648KB시간: 656ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Building { int idx; i.. 2024. 5. 17. [백준] 2179: 비슷한 단어 - JAVA https://www.acmicpc.net/problem/2179 풀이영단어들이 주어지고 두 단어를 앞에서부터 비교하여 공통적으로 나타나는 부분의 길이가 긴 두 단어를 출력해야한다. 한글자씩 비교하기 위해 트라이 알고리즘을 생각했으나, 시간이 충분하고 메모리 제한이 작아서 트라이를 사용하지 않았다. 길이가 같을 경우 주어진 순서대로 앞쪽에 있는 단어가 답이되므로 순서 유지가 되는 ArrayList를 선택했다. ArrayList에 단어를 담고 앞에서 부터 순서대로 비교하여 접두사의 길이와 인덱스를 저장했다. 메모리: 19328KB시간: 2008ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void .. 2024. 5. 17. [백준] 2075: 스카이라인 쉬운거 - JAVA https://www.acmicpc.net/problem/2075 풀이왼쪽부터 순서대로 좌표가 주어지므로 높이만 stack에 저장하면 된다. 스택에 높이를 저장하면서 stack.peek()보다 높이가 낮아지면 stack.peek()이 더 낮아질때까지 pop해주면서 답을 하나씩 늘린다. 그리고 새로운 높이를 스택에 저장한다. 주의할 점으로 높이가 0이면 저장을 안해도 되고, stack.peek()과 높이가 같으면 저장을 안해도 된다는 것이있다. 메모리: 19576KB시간: 212ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws Exception {.. 2024. 5. 17. [백준] 2075: N번째 큰 수 - JAVA https://www.acmicpc.net/problem/2075 풀이N \* N 개의 숫자 중에 N번째로 큰 숫자를 찾아야 한다. 우선순위큐를 사용해 정렬방식을 내림차순으로 하여 N개만큼 뽑는 방법이 있다. 이때는 `Collections.reverseOrder()` 를 사용해야 한다. 나는 오름차순 우선순위큐의 사이즈를 N으로 유지시키면서 값을 집어넣고 마지막에 하나를 뽑기로 했다. 이렇게하면 가장 큰 수 N개가 우선순위큐에 들어있게 되고, poll하면 N번째로 큰 숫자가 나온다. 메모리: 244104KB시간: 944ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void main(String[].. 2024. 5. 17. 이전 1 2 3 4 다음