Dev.baelanche

퀵정렬로 정렬하여 k-1 의 인덱스를 출력했는데 96%에서 계속 시간초과가 났다. 질문게시판을 보니 퀵정렬 대신 퀵셀렉트를 써야된다고 한다. 퀵셀렉트는 퀵정렬 도중 원하는 인덱스를 바로 캐치하는 알고리즘인데, 공부할 것도 많은데 알아보기 귀찮았다. 그래서 합병정렬로 해봤는데 역시나 풀린다.... '잘' 구현할거 아니면 퀵정렬보다는 합병정렬 쓰는걸 추천한다. public class Main { static int temp[]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new Bu..

Comparator 구현해서 5분만에 풀었다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String a[] = new String[n]; for(int i=0; i

정렬을 오름차순 혹은 내림차순으로 해주고 큰 수 > 작은 수 > 큰 수 > 작은 수 순으로 배치하여 넓이를 구하면 된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int a[] = new int[4]; for(int i=0; i

Comparator 클래스를 구현하여 문제에서 요구하는대로 정렬을 구현했다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[][] = new int[n][2]; for(int i=0; i

Set(집합) 라이브러리를 이용하여 풀었다. 다음번에는 자료구조를 직접 구현해서 풀어야겠다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int an = sc.nextInt(); int bn = sc.nextInt(); TreeSet a = new TreeSet(); TreeSet b = new TreeSet(); for(int i=0; i

예제로 트리 구조를 유추해보자. 전위 순회 : 3 6 5 4 8 7 1 2 중위 순회 : 5 6 8 4 3 1 2 7 전위 순회는 루트부터 시작하고, 중위 순회는 루트를 중심으로 왼쪽 서브트리, 오른쪽 서브트리로 나뉜다. 전위 순회의 첫번째가 3이므로 루트 노드는 3이고 5 6 8 4 는 왼쪽 서브트리, 1 2 7 은 오른쪽 서브트리이다. 양 서브트리의 루트(최상단) 노드는 전위 순회의 첫번째 노드 이므로 각각 6, 7 이다. 루트 노트를 찾았으면 또 이등분하여 서브트리를 구한다. 시작 위치, 끝 위치, 루트 노드의 위치를 받아 재귀하여 구현하였다. public class Main { static int pre[]; static int in[]; public static void main(String[]..

입력값들로 트리를 만들어 후위 순회를 한다. 늑대의 수 - 양의 수가 음수가 될때를 주의해주어야 한다. public class Main { static ArrayList a[]; static char sw[]; static int score[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); a = new ArrayList[n+1]; sw = new char[n+1]; score = new int[n+1]; for(int i=0; i

트리구조를 만든 후 BFS를 두번 수행하여 푼다. 1. BFS로 루트부터 하위 레벨로 순차적으로 접근한다. 2. 제일 하위 레벨의 노드일때는 접근하지 않는다. 3. 첫번째 BFS에서 접근하지 않은 노드들에 다시 접근해서 개수를 센다. public class Main { static ArrayList[] tree; static int[] parents; static boolean[] visited; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new..