Dev.baelanche

구현자체는 정말 쉬운 문제다. for(int i=0; i0) { st = new StringTokenizer(br.readLine()); a = Integer.parseInt(st.nextToken()); b = Integer.parseInt(st.nextToken()); ch = br.readLine().toCharArray(); len = ch.length; for(int i=0; i

문제에서 서술해준 대로 GCD = 1, LCM = A*B 인 경우를 찾아서 카운트한다. N = 30 일때 완전탐색으로 (1, 30), (2, 15), (3, 10), (5, 6), (6, 5), (10, 3), (15, 2), (30, 1) 을 찾을 수 있다. 총 개수/2 를 하게되면 N이 큰 수 일때 TLE 가 발생한다. (5, 6) => (6, 5) 로 넘어갈때 오른쪽수보다 왼쪽수가 더 커지게 된다. 이 부분을 체크하여 시간초과를 해결해 주었다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t-->0) { int n = s..

점 a, b, c 를 완적탐색으로 하면 O(n^3)으로 시간초과가 나게 된다. 점 a, b 를 고르고 이분탐색으로 c를 찾으면 O(n^2 log n)으로 AC를 맞을 수 있지만 O(n^2)의 방법으로 풀어보겠다. 점 a, b 를 정하고 b-a와 같은 값 c를 b < k < n 에서 찾는다. k == n-1 일때까지 모두 탐색했다면 b를 오른쪽 점으로 한칸 옮겨서 반복 수행한다. a점도 마찬가지로 b점이 b == n-2 이면 오른쪽으로 움직인다. public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.i..

예제를 예로 설명해보겠다. 입력값 배열 3 4 7 5 6 4 2 9 입력값따로, 부분합배열을 따로 만들어준다. 부분합 배열 3 7 14 19 25 29 31 40 43 47 for(int i=1; i0) { int n = sc.nextInt(); int m = sc.nextInt(); int k = sc.nextInt(); int a[] = new int[n]; for(int i=0; i

문자열체크 문제이다. +, -, *, / 가 나오기 전까지의 문자들을 왼쪽 숫자, 그 이후부터 = 이전까지의 문자들을 오른쪽 숫자 = 이후의 문자들을 결과값으로 저장한다. 왼쪽 숫자가 음수일 수 있으므로 그 부분을 유의해야한다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); sc.nextLine(); while(t-->0) { char c[] = sc.nextLine().replaceAll(" ", "").toCharArray(); String left = ""; char mid; String right = ""; String result..

A A A C B B B C가 맨처음 들어간 문자열이고 현재 문자열이 B라면, C와 B를 비교한다. B가 C보다 순서가 같거나 빠르므로 더 앞자리와 비교한다. A와 B를 비교한다. B가 A보다 순서가 느리므로 문자열 맨뒤에 붙이게된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t-->0) { int n = sc.nextInt(); int idx = 0; String result = sc.next(); for(int i=0; i= 0) { if(result.charAt(k) >= c) { k--; } else { s = fa..

직접 구현하기에는 까다로운 문제이다. Map이나 Set은 순서를 보장하지 않으므로 중복없이 보관해봤자 인풋 순서대로 보관되지 않는다. 자료구조를 직접 만들어서 구현하는게 베스트이지만, 필자는 랭작에 미쳐있는 관계로 기존에 있는 자료구조로 하기로 했다. 자바에서는 LinkedHashMap, LinkedHashSet 이 순서를 보장해주며 중복체크를 할 수 있다. Node가 서로 Linked 되어있으니 순서는 넣은 그대로 사용해주면 되고 Set을 사용했을때는 자동 중복제거를 해주고 Map일때는 key값을 비교하여 중복제거를 해주면 되겠다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in)..

포인터를 두개 놓고 국회의원의 명예 점수가 비어있을때의 경우를 체크해주어야 한다. 예시를 보자. 1 2 3 4 5 6 7 0 1 1 1 0 1 1 국회의원은 5명이고 모독한번으로 모두 박탈시키려면 점수가 1, 2, 3, 4, 5 가 되어야 한다. 먼저, 포인터를 left, right로 두고 left의 초기값은 무조건 1이다. right의 초기값은 국회의원의 명예점수중 최소값이다. 따라서 left=1, right=2가 된다. left 포인터가 가르치는 곳에 명예점수가 비어있다면 right포인터의 명예점수가 채워져 있을때 그 값을 당겨온다. a[left] = 0, a[right] = 1 이므로 2에서 1을 빼서 1로 당겨오고 그만큼 해커를 고용한다. 1 2 3 4 5 6 7 1 0 1 1 0 1 1 left..