본문 바로가기

Programming/알고리즘

 (33)
[백준] 1026 - 보물 - JAVA[자바] (feat. B 재배열 X, B sort X) [접근 방법] "B에 있는 수 를 재배열하면 안 된다" 라는 말에 꽂혀 여러 방법으로 풀어보게 되었다. B에 있는 수를 재배열하면 안된다는 말은 1. 단순히 "Sort하면 안된다." -> B의 배열을 손상시키면 안된다. Arrays.sort(B)를 하면 B는 sort 된 상태로 남아있게 되므로 B에 있는 수를 재배열하는 것이다 가장 나쁜 풀이라고 평가 하고 싶다. 개인적 평가: 1.0 / 5.0 근데, 구글에 검색해보니 해당 방법을 10중 8, 9 분이 사용하고 계신것 같다. 왤까.. import java.io.IOException; import java.io.InputStreamReader; import java.io.BufferedReader; import java.util.Arrays; import..
[백준] 18870 - 좌표 압축 - JAVA[자바] [접근 방법] "좌표 압축" 은 coordinate Compression(좌표 압축) 이라고 하는 문제의 한 카테고리를 차지하고 있다. 데이터의 범주가 너무 크거나, 단순화하여 문제를 세분화 시킬 때 사용할 수 있다. 이번 문제를 해석하면 배열의 각 원소에 대해 순위를 매긴다 라고 생각하면 된다. 예제 입력 1에서 {2, 4, -10, 4, -9} 가 있을 때 내림차순으로 순위를 매긴다면 {2, 3, 0, 3, 1} 이 된다. 즉, 1. 낮은 값이 높은 순위(0순위) 를 갖는다. 2. 중복되는 원소는 같은 순위를 갖는다. 이때 정렬을 떠올리는 것이 좋은 접근방법이다. 또, "2. 중복되는 원소는 같은 순위를 갖는다." 에서 중복되는 원소를 하나만 갖는게 중요하므로 자료구조 중 Set 혹은 Map을 사용하..
[백준]2108 - 통계학 - JAVA[자바] [접근방법] Counting 정렬(카운팅 정렬) 을 이용하려 한다. ( O(N) ) 정렬을 쉽게 하기위해 Arrays.sort(배열) 을 이용할 수 있지만, 3번째의 최빈값을 구할때 "두 번째로 작은 값" 을 출력해야 하므로 복잡하다. Arrays.sort를 사용시 ( O(NlogN) ) 중앙값 : (N+1) 위치 범위: (N-1) 번째 인덱스 값 - 0번째 인덱스 값의 차 최빈값 : 배열 첫 번째부터 탐색. 각 값별 최빈값을 count하면서 가장 큰 빈도수 중, 두 번째로 작은 값 찾아내야함 => 플래그(flag) 변수를 하나 두고, 빈도수가 같았던 적이 있는지 여부를 판별해야 한다. 최빈값 : 이전의 최빈값의 최댓값보다 현재 최빈값이 더 클 경우 즉, 처음으로 나타난 최빈값일 경우 해당 index(i..
[백준] 1712 - 손익분기점 -JAVA[자바] 문제의 개념이 다소 복잡하게 설명되어 있지만, 문제의 요지는 [가격(C) - 한대 생산에 드는 비용(B)] 이 고정비용(A) 보다 커지는 순간이 언제인가 하는 것이다. 따라서, C-B < 0일 경우에는 손익분기점이 존재할 수 없다. 손익분기점은 A / (C-B) 인 지점에서 1개가 더 팔렸을때! 이므로 import java.io.IOException; import java.io.InputStreamReader; import java.io.BufferedReader; import java.util.StringTokenizer; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new..
[백준] 5622 - 다이얼 - JAVA[자바] Switch 구문을 이용하면 편하다 https://ch-programmer.tistory.com/64 [조건문] switch-case vs if-else 조건문을 수행하는 구문에는 if-else 구문과 Switch-case 구문이 있다. if - else 구문 if(조건문) {조건문이 true일 때 수행할 실행문 } else { 조건문이 false일 때 수행할 실행문 } if 다음에 나오는 ()괄호 안 ch-programmer.tistory.com import java.io.IOException; import java.io.InputStreamReader; import java.io.BufferedReader; public class Main{ public static void main(String[] ..
[백준] 2908 - 상수 - JAVA[자바] 두가지 방법으로 나눌 수 있다. 입력이 세자리 수이므로, 직접 뒤집을 수도 있다. 1. 직접 뒤집는 방법. import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " ..
[백준] 10809 - 알파벳 찾기 - JAVA[자바] 1. 먼저 int형 배열을 하나 생성하여 모두 -1로 초기화 시킨다. 이 배열은 문자열 S에 각 문자의 위치를 가리킬 배열이다. int[] arr = new int[26]; for(int i = 0; i < arr.length; i++){ arr[i] = -1; } 2. S라는 문자열이 주어진다. String S = br.readLine(); for(int i = 0; i < S.length(); i++) { char ch = S.charAt(i); if(arr[ch - 'a'] == -1) {// arr 원소 값이 -1 인 경우에만 초기화 arr[ch - 'a'] = i; } } 3. 반복문을 통해 문자열의 각 문자를 검사한다. 즉, charAt()이라는 메소드를 사용하여 문자를 추출한 뒤 ch라는 변..
[백준] 11720 - 숫자의 합 - JAVA[자바] 2가지 방법이 있다. 1. Scanner 로 입력받아 charAt() 을 사용하여 푸는 방법 2. BufferedReader 로 입력받아 getBytes() 을 이용하여 푸는 방법 방법 1. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); String a = in.next(); in.close(); int sum = 0; for(int i =0; i < N; i++){ sum += a.charAt(i) - '0'; } System.out.print(sum); } } Scanner를 이용한 가장 ..

티스토리툴바