본문 바로가기
728x90

코딩테스트/BOJ49

[백준] 11650번 - 좌표 정렬하기 https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 이 문제는 2차원 배열 정렬만 신경쓰면 되었따 Arrays.sort(arr, (o1, o2) -> { if(o1[0] == o2[0]) { return o1[1]-o2[1]; } else { return o1[0]-o2[0]; } }); 우선 첫번째 좌표가 같으면 두번째 좌표 기준으로 정렬하기 떄문에 위와 같이 구현했다 자바 코드) packag.. 2022. 9. 28.
[BOJ] 2751번 - 수 정렬하기 2 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 이 문제는 Arrays.sort() 로 하면 시간 초과가 발생한다 Arrays.sort()는 primitive arrays에 대해 Dual-Pivot Quicksort를 수행한다 이는 평균 시간복잡도가 O(nlogn)이지만 최악의 경우 시간복잡도는 O(n^2) 가 된다 따라서 이 문제에서는 O(n^2)를 못하게 해서 시간 초과가 발생한다ㅠ 그래서 나는 2가지의 방식으로 성능을 개선했다!.. 2022. 9. 28.
[백준] 1451. 직사각형으로 나누기 - JAVA https://www.acmicpc.net/problem/1451 1451번: 직사각형으로 나누기 첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 50보다 작거나 같은 자연수이 www.acmicpc.net 와 이 문제 푸는데 거의 2시간 걸린듯,,, 왜이렇게 어렵지,,, 어렵다기보다 사각형 넓이 구하는 과정이 헷갈림 인덱스들 맞추는거,,,ㅠㅠ 암튼 참고한 블로그 내용을 설명해보겠다 직사각형을 나누는 방법 3개의 직사각형으로 나눌 수 있는 경우의 수는 위의 6가지가 전부이다 그래서 그냥 다 구해보는 수 밖에 없다~ 직사각형의 합을 구하는 방법 이걸로는 미리 sum 배열을 만들어둔다 해당 .. 2022. 9. 26.
[JAVA] 백준 11724번 - 연결 요소의 개수 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 각 노드가 몇 개나 연결되었는지 구하면 되는 문제다 그래서 난 DFS를 활용해서 풀었다 약간 고민했던 점은 dfs를 호출할 떄마다 answer++ 를 하면 각각 나눠진 영역의 개수를 구하게 된다 그래서 연결된 요소들의 개수를 구하기 위해 dfs가 호출되고 visited의 수가 바뀔때마다 answer를 증가해야할 줄 알았는데?! 아니었네.. 2022. 5. 18.
[JAVA] 백준 2179번 - 비슷한 단어 https://www.acmicpc.net/problem/2179 2179번: 비슷한 단어 첫째 줄에 S를, 둘째 줄에 T를 출력한다. 단, 이 두 단어는 서로 달라야 한다. 즉, 가장 비슷한 두 단어를 구할 때 같은 단어는 제외하는 것이다. www.acmicpc.net 문제 설명이 투박했던 문제.. 풀이 과정도 고민 시간도 그리 길지 않았는데 도대체 문자열 선택 기준이 어케 되는지 헷갈렸당 그냥 모든 문자열끼리 다 비교하고 비슷한 알파벳 수가 많은 단어를 앞에서부터 2개 출력하면 되는거였음~ 자바 코드) import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class boj2179 { public stati.. 2022. 5. 6.
[JAVA] 백준 9095번 - 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 이거 백준 강의 들을 때 풀었던 문젠데 고새 까먹음,, 나 완전탐색 진짜 못하는 듯,,, 역시 코테는 꾸준히 해야하나부다... 암튼... 이거 풀이 참고해서 풀었고 아래는 코드! 자바 코드) import java.util.Scanner; public class Main { static int dp[] = new int[11]; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int t = scan.. 2022. 5. 4.
728x90

티스토리툴바