Algorithm221 [백준] 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. [백준] 1189: 컴백홈 - JAVA https://www.acmicpc.net/problem/1189 풀이(R-1, 0)에서 (0, C-1)로 이동한다. T는 가지 못하는 부분이고, 한번 지나친 곳은 다시 방문하지 않는다. 이동거리가 K인 경우의 수를 구하는 문제이다. 따라서 방문처리를 하며 dfs탐색을 했다. 각각의 경우에 따른 방문처리가 서로 영향을 주어서는 안되기 때문이다. 이동 거리를 1씩 늘려가면서 다음 칸으로 이동했고, 이동 거리가 K가 됐을 때, 도착점에 도달하였을 때 사이클을 종료시켰다. 메모리: 14584KB시간: 136ms언어: Java 11import java.util.*;import java.io.*;public class Main { static int[][] vector = { { 1, 0 }, { 0, 1.. 2024. 5. 17. [백준] 14658: 하늘에서 별똥별이 빗발친다 - JAVA https://www.acmicpc.net/problem/14658 풀이N, M의 범위가 500000이기 때문에 이것을 기준으로 탐색을하면 시간초과가 난다. K가 100까지인것을 보고 K를 기준으로 탐색했다. 트램펄린의 어느 모서리에 별이 위치해있어야 많은 별을 담을 수 있다. 별 두개를 선택해 별a의 x좌표와, 별b의 y좌표를 한쪽 꼭지점으로 하는 길이 L의 사각형을 만들어 거기에 별이 얼마나 들어가는지 체크했다. 메모리: 14712KB시간: 160ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Node { int x; int y; public Node(int .. 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. [백준] 7490: 0 만들기 - JAVA https://www.acmicpc.net/problem/7490 풀이1부터 N까지의 수 사이에 +, -, 공백을 넣어서 수식을 만들고 그 수식을 계산하여 0이 되는 경우 출력해야 한다. 출력할 때 ASCII 순서에 따라 출력하라는 제한이 있어서 공백, +, - 순서로 dfs탐색을 통해 수식을 만들었다. N까지 진행하면 수식을 계산하는 메서드를 통해 0이 나오면 값을 출력한다. 메모리: 17200KB시간: 168ms언어: Java 11import java.io.*;public class Main { static int N; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws.. 2024. 5. 17. [백준] 13144: List of Unique Numbers - JAVA https://www.acmicpc.net/problem/13144 풀이길이 N의 수열에서 연속한 1개 이상의 수을 뽑았을 때 같은 수가 여러번 등장하지 않는 경우의 수를 구해야 한다. 처음에는 첫번째 원소부터 시작하여 dfs탐색을 통해 구하려고 했었다. 방문체크는 비트마스킹을 이용할 계획이었다. 하지만 N의 범위와 숫자들의 범위가 커서 안되는 것을 깨달았다. 따라서 투포인터 알고리즘을 떠올렸다. start, end를 0에서 부터 시작하여 방문처리를 하면서 end값을 증가시킨다. 이전에 나온 숫자가 나올때까지 end값을 증가시키고 ans에 end - start를 더해준다. 현재 start값에 대한 경우의 수를 구했으므로 현재 start값의 방문처리를 지우고 start값을 1늘려 다시 판단한다. 메모리:.. 2024. 5. 17. [백준] 22251: 빌런 호석 - JAVA https://www.acmicpc.net/problem/22251 풀이디지털 숫자의 눈금들을 반전시켜서 다른 숫자를 만들 수 있다. 다른 숫자가 되려면 몇 개를 반전시켜야 하는지 이차원배열 arr에 저장해놓고 시작했다. dfs탐색을 통해 숫자 X를 일의자리부터 앞으로 가면서 바꿔줬다. 반전한 개수 누적하고 만들어진 숫자를 저장하면서 숫자가 N보다 크거나 반전 횟수가 P보다 크면 성립하지 않는 것이므로 return해주었다. K자리 수까지 갔을 때 만족하면 result에 1을 더해주었다. 숫자가 0이 되는 경우를 제외했고, 현재 숫자와 같으면 안되므로 result에 -1해주었다. 메모리: 14292KB시간: 196ms언어: Java 11import java.util.*;import java.io.*;pu.. 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. [백준] 2668: 숫자고르기 - JAVA https://www.acmicpc.net/problem/2668 풀이사이클을 찾는 문제이다. `arr[i] -> arr[arr[i]]`이런식으로 뽑힌 정수를 인덱스로 하는 숫자를 다시 봐야한다. 처음 시작한 숫자와 같은 숫자가 나오면 사이클이 완성된다. dfs탐색을 통해 뽑힌 정수를 인덱스로 하여 탐색했고 처음 숫자가 나왔을 때 list에 넣었다. 메모리: 14216KB시간: 128ms언어: Java 11import java.util.*;import java.io.*;public class Main { static int[] arr; static ArrayList list; static boolean[] visit; public static void main(String[] ar.. 2024. 5. 17. 이전 1 ··· 7 8 9 10 11 12 13 ··· 23 다음