주의사항
주의사항
백준
- class 네임 Main으로
- import 패키지도 꼭 넣어야 한다.
프로그래머스
- 실제 시험 환경
- class solution{...}부터 시작, main함수 안만들어도 돼
=> 디버거 x , console print로 확인해야기본지식
Java String 관련 메서드 정리
https://velog.io/@mooh2jj/자바-메서드-정리
// 참고할 자바 기본문법
1) int vs long
2) i++ vs ++1
3) Array 오름차순 정렬 vs 내림차순 정렬
4) Comparable
5) static 변수
6) for vs while
7) if vs switch
8) 정답을 XX로 나눈 나머지를 출력하세요. // 하루코딩
// String
1) charAt(i) => 문자열의 위치
2) charAt(i) - '0' => int값 변화
3) toCharArray() => char[] 변화
4) indexOf(), subString(0, string1.indexOf(" "))
5) Palindrome // ex banana => anana
// Scanner vs BufferedReader & StringTokenizer
=> BufferedReader : why? 제한시간
// Scanner 방식
Scanner sc = new Scanner(System.in);
String str = sc.next();
String str1 = sc.nextLine();
char c = input.next().charAt(0);
int num = sc.nextInt();
// BufferedReader & StringTokenizer 방식
BufferedReader br = new BufferedReader(new InputStreamReader(System.in);
StringTokenizer st = new StringTokenizer(br.readLine());
코딩 테스트를 풀 땐 Scanner 보다 BufferedReader 더 효율적
BufferedReader의 속도가 더 빠른 이유는 Buffer의 차이입니다.
Scanner는 1kb의 buffer를 가진 반면, BufferedReader는 8kb의 buffer를 가집니다.
그래서 입력을 저장했다가 한 번에 전송할 수 있기 때문에 더 빠른 속도를 낼 수 있습니다.
https://velog.io/@postrel63/백준-BufferedReader-StringTokenizer
String str = st.nextToken();
String str1 = br.readLine();
char c = st.nextToken().charAt(0);
// AB CDD EFFF GH 입력
st.nextToken(); // AB
st.nextToken() // CDD
st.nextToken() // EFFF
st.nextToken() // GH
parsging String -> int
int a = Integer.parseInt(st.nextToken());
시간복잡도
시간복잡도란 입력크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며 주요로직의 반복횟수를 중점으로 측정됩니다.
시간복잡도 체크
int sum = 0;
for(int i = 0; i < 10; i++) { // 10* n ^ 2
for(int j = 0; j < n; j++) {
for(int k = 0; k < n; k++) {
sum += i ;
}
}
}
for(int i = 0; i < n; i++) { // n
sum += i ;
}
// 시간복잡도 : 10 n ^ 2 + n 생각정리
*빅오 표기법 -> 시간즉정도 최악을 가정한(적어도 이정도는 보완해준다는 뜻)
루프문 갯수가 n개로 치면 됨! 상수는 무시해도 되 2n -> n 개
logn -> log2N같음. 이진트리 logn임
*리턴이 void일시, retrun;의 의미 함수호출 끝 {}를 다 돌았다는 뜻
*재귀호출 '스택'이용 계속 함수호출하면 스택오버플로우오류...
재귀호출-> 메모리문제 보완한 게 Array 이용한 메모제이션(-> 이게 동적프로그래밍). 그래도 for문 성능 못이겨...
ex. 이진수, 피보나치, 팩토리얼 등등..
부분집합 경우수, 이진트리, dfs, 동적프로그래밍(dp), 백트래킹 등등에도 나오는 내용
*이진트리 정렬부터 해야 가능, sout위치에 따라 전위순회, 중위순회, 후위순회 등이 나눠짐.. 부모노드위치에 따라 전위, 순위, 후위로 나워어진 것임. 후위순위는 merge정렬 상향방식으로 활용
*분할정복 vs 동적프로그래밍
공통점 : 문제를 잘게 쪼개서, 가장 작은 단위로 분할
분할정복 - 하위문제중복x -> Memoization 기법을 활용x ex. merge정렬
동적프로그래밍 - 하위문제 중복o, Memoization 기법을 활용o ex. 피보나치정렬
표현식
// String
// 문자열 자르기
String string1 = "hello wordl!";
String substring = string1.substring(0, string1.indexOf(" "));
// hello
// data parsing
Long.parseLong(dealAmount.replaceAll(",", "").trim());
// result: 12,000 -> 12000
// 마지막 끝 위치 표현
String answer = ~;
answer.charAt(answer.length() - 1)
// 문자열 empty인지
answer.isEmpty()
// reverse()[Palindrome]를 위해서는 StringBuilder(str) 사용
String tmp = new StringBuilder(str).reverse().toString();
// 대소문자 구분없이 equalsIgnoreCase(받는 str)
str.equalsIgnoreCase(tmp);
// 문자배열을 char 로 받을 때 for문
for(char x : str.toCharArray()){...}
// 인라인으로 배열 출력 println x -> print
for(int x : main.solution(N))
System.out.print(x+" ");
// continue vs break
continue; // 건너뛰고 반복문계속 실행(skip)
break; // 가장 가까운 for문 탈출(jump)
// int [] 배열 정의 index 표현을 할 때는 List 대신해
int[] answer = new int[s.length()];
// 대알파벳 -> "" , 정규표현식 사용
str = str.toUpperCase().replaceAll("[^A-Z]", "");
// 그외
// Integer 고유 MIN값 정의 max를 일단 제일 작은 값으로 정의할 때 쓰임
int max = Integer.MIN_VALUE;
// 삼항연산자
return isPrimeNumber ? "소수입니다." : "소수가 아닙니다.";
// 정렬 : sort
int a[] = {5,3,2,4,1};
Arrays.sort(a); // 퀵정렬 사용, 기본이 오름차순
// Integer[] tmp =
Arrays.stream(a).boxed().toArray(Intger[]::new);
// Integer -> int, 내림차순
Arrays.sort(tmp, Collections.reverOrder());
// Comparable 구현
// Map count 값 넣기
map.put(ints[i], map.getOrDefault(ints[i], 0) + 1)
* getOrDefault(Object key, V DefaultValue) // 찾는 키가 존재한다면 찾는 키의 값을 반환하고 없다면 기본 값을 반환하는 메서드
// Map put 방식 => putIfAbsent
Map<Character, Integer> map1 = new HashMap<>();
for (Character c : str.toCharArray()) {
map1.putIfAbsent(c, 0); // 'c' 가 없으면 0, 'c'가 있으면 변경x
map1.put(c, map1.get(c) + 1);
}
// List 배열 합치기
students.addAll(new ArrayList<>(List.of(new Student(("이자요이"), 4444))));
// Queue는 추가/삭제가 더 쉬운 LinkedList로 구현체를 만든다.
Queue<String> queue = new LinkedList<>();기본 알고리즘
소수판별
public String solution(int n) {
boolean isPrimeNumber = true;
// 소수라면 1은 소수가 아님!(1은 뺌!) 소수는 1과 자기자신만을 약수로 가진 수
for (int i = 2; i < n/2; i++) { // 2로도 나누어서 시간복잡도 더 줄일 수 있어!
if (n % i == 0) {
isPrimeNumber = false;
}
}
return isPrimeNumber ? "소수입니다." : "소수가 아닙니다.";
}재귀함수(팩토리얼)
public int factorial(int n) {
if (n == 1) { // 이게 가장 중요
return 1;
}
return n * factorial(n-1);
}피보나치 수열(메모제이션)
참고사항
재귀호출 -> 메모제이션(동적 다이내믹, 분할계획법, Top-down방식) public List<Integer> solution() {
List<Integer> answer = new ArrayList<>();
int[] ints = new int[10];
ints[0] = 1;
ints[1] = 2;
answer.add(ints[0]);
answer.add(ints[1]);
for (int i = 2; i < ints.length; i++) { // 0,...99
ints[i] = ints[i-1] + ints[i-2]; // 메모제이션: 재사용 by 배열
answer.add(ints[i]);
}
return answer;
}
// [1, 2, 3, 5, 8, 13, 21, 34, 55, 89]swap 알고리즘
char tmp = ch[lt]; // 그냥 서로 바꾸는 거 tmp(임시변수)가 필요한 게 다임!
ch[lt] = ch[rt];
ch[rt] = tmp;최대값 알고리즘
String answer = "";
int max = Integer.MIN_VALUE; // max는 가장 작은 값으로 놓는게 포인트!
for (String x : split) {
int len = x.length();
if (len > max) { // 최대값 구하는 알고리즘 적용, len >= max (x)
max = len;
// ---- 여기까지가 최대값 알고리즘 별거 없음...
answer = x;
}
}최대값 알고리즘2(최빈수)
public int solution(int n, int[] ints) {
int answer = 0; // 최빈수
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(ints[i], map.getOrDefault(ints[i], 0) + 1); // count
}
int max = 0;
for (int tmp : map.keySet()) {
if (max < map.get(tmp)) {
max = map.get(tmp);
answer = tmp;
}
}
return answer;
}
//1 2 2 3
//2버블정렬
// 버블정렬 : 이중for + j=n-i 상태로 swap알고리즘 적용한 것!
public int[] solution(int n, int[] arr){
for(int i=0; i<n-1; i++){
for(int j=0; j<n-i-1; j++){ // i=0일때 j n-1까지, i=1일때 j n-2까지, i=2일때 j n-3까지 ...
if(arr[j]>arr[j+1]){ // 짝끼리
// swap 작은 것을 앞으로
int tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
}
}
}
return arr;
}숫자 뒤집기 + 소수 판별
private boolean isPrime(int tmp) { // 소수 판별
if(tmp == 1) return false;
for (int i = 2; i < tmp/2; i++) { 약수 되는 건 false
if(tmp%i == 0) return false;
}
return true;
}
public ArrayList<Integer> solution(int n, int[] arr){
/* ArrayList<Integer> answer = new ArrayList<>();
for(int i=0; i<n; i++){
int tmp=arr[i];
int res=0;
while(tmp>0){ // 숫자 뒤집기
int t=tmp%10;
res=res*10+t;
tmp=tmp/10;
}
if(isPrime(res)) answer.add(res); // 소수 판별
}
*/
List<Integer> answer = new ArrayList<Integer>();
// str 뒤집기
int tmp = 0;
for(int i =0; i < n; i++) {
StringBuilder sb = new StringBuilder(String.valueOf(ints[i])).reverse();
tmp = Integer.parseInt(sb.toString());
if(isPreime(tmp)) answer.add(tmp);
}
return answer;
}Palindrome(팰린드롬) - 문자열뒤집기
// 1) while
while (lt < rt) { // 뒤집기 단골 변수 : lt, rt => while(lt<rt)
// 알파벳 아닌 것들은 그냥 넘어가
if(!Character.isAlphabetic(ch[lt])) lt++;
else if(!Character.isAlphabetic(ch[rt])) rt--;
else { // 알파벳일 때
char tmp = ch[lt]; // swap 알고리즘 적용
ch[lt] = ch[rt];
ch[rt] = tmp;
lt++;
rt--;
}
}
// 2) for문
public String solution(String str) {
str = str.toUpperCase();
char c[] = str.toCharArray();
char tmp;
int len = c.length;
for (int i = 0; i < len / 2; i++) { // 반만 진행해야 됨!
// swap 알고리즘 적용
tmp = c[i];
c[i] = c[len - i - 1];
c[len - i - 1] = tmp;
}
// 1) for문
// for (int i = 0; i < len; i++) {
// tmp[len - 1 - i] = c[i];
// }
return String.valueOf(tmp);
}이중for문 - 등수구하기
public static void main(String[] args) {
// 정렬 할 필요x -> 또 answer 어떨 때 count를 칠 것이냐!
int[] arr = {87, 89, 92, 100, 76};
int[] answer = new int[arr.length];
for(int i=0; i<arr.length; i++){
int cnt=1; // rank = 1
for(int j=0; j<arr.length; j++){
if(arr[j]>arr[i]) cnt++; // 반대로 나보다 높은 애들 갯수 세기 그게 랭크!
}
answer[i]=cnt;
}
for (int i : answer) {
System.out.println(i);
}
}이중for문 - 주식가격
// 주식가격
int[] prices = {1, 2, 3, 2, 3};
int[] answer = new int[prices.length];
for (int i = 0; i < prices.length; i++) {
for (int j = i+1; j < prices.length; j++) {
answer[i]++;
if(prices[i] > prices[j]) break;
}
}
for (int x : answer) {
System.out.println(x);
}중복문자
// 중복문자 중복된 카운드 세기 -> Map으로
Map<String, Integer> map = new LinkedHashMap<>(); // LinkedHashMap 순서가 보장, List처럼
Integer count = null;
for (String s : str.split("")) {
count = map.get(s);
if (count == null) {
map.put(s, 1);
} else {
map.put(s, count+1);
}
}
for (String key : map.keySet()) {
System.out.println(key + ": " + map.get(key));
}
//j: 1
//a: 2
//v: 1
// 또다른 예시
String[] arr = {"AB", "AB", "RRT", "QWER", "RRT"};
// map 으로 중복문자 갯수 구하기
Map<String, Integer> myMap = new HashMap<>();
for (String s : arr) {
if (myMap.containsKey(s)) {
myMap.put(s, myMap.get(s) + 1);
} else {
myMap.put(s, 1);
}
}
System.out.println("myMap=" + myMap);
// 중복문자 축출
public String solution(String str) {
String answer = "";
/* for (int i = 0; i < str.length(); i++) {
if(str.indexOf(str.charAt(i)) == i ) answer += str.charAt(i); // indexOf() : 문자의 첫번째 index부터 먼저 반환됨!
}*/
for (char x : str.toCharArray()) {
if (!answer.contains(String.valueOf(x))) { // 중복문자 제거
answer += String.valueOf(x);
}
}
// map.getOrDefault(key,0)+1 이용
Map<Character, Integer> map = new HashMap<Character, Integer>();
for(char key : str.toCharArray()) {
map.put(key, map.getOrDefault(key, 0)+1); // 중복 카운트
if(map.get(key) > 1) answer += String.valueOf(key);
}
return answer;
}// 중복문자 카운트, 최대값인 key 축출 *학급회장 문제 참고
private char solution(String str) {
char answer = ' ';
Map<Character, Integer> map = new HashMap<>();
int max = Integer.MIN_VALUE;
for (char key : str.toCharArray()) {
map.put(key, map.getOrDefault(key, 0) + 1);
if( map.get(key) > max){
max = map.get(key);
answer = key;
}
}
return answer;
}중복문자 제거 - stack
// 중복 문자 제거 - 스택
Stack<Integer> stack = new Stack<>();
int[] ints = {1, 2, 2, 2, 3, 3, 4, 5};
for (int i : ints) {
if (stack.isEmpty() || stack.peek() != i) {
stack.push(i);
}
}
for (int x : stack) {
System.out.println(x);
}아나그램
// 아나그램 : 문자열을 재배열하면 다른 단어가 되는 일종의 말장난
// 두 문자열을 비교, 아나그램인지 아닌지 판별
public String solution(String s1, String s2) {
String answer = "YES";
HashMap<Character, Integer> map = new HashMap<>();
for (char x : s1.toCharArray()) {
map.put(x, map.getOrDefault(x, 0) + 1); // map의 value에 count값으로 1부터 계속 넣기
}
for (char x : s2.toCharArray()) {
// map의 value에서 같지 않은 게 나오면 return "No"
if(!map.containsKey(x) || map.get(x)==0) return "NO";
// 아니면 return "YES"
map.put(x, map.get(x) - 1); // count 다시 초기화
}
return answer;
}sliding window(최대 매출액, 연속합)
1) 최대 매출액
private int solution(int n, int k, int[] ints) {
int answer = 0;
int sum = 0;
for (int i = 0; i < k; i++) {
sum += ints[i];
}
answer = sum; // 처음 0,1,..k-1까지 합은 따로 구한다.
// 그다음부터 구하는 공식
for (int i = k; i < n; i++) {
sum += (ints[i] - ints[i - k]); // k=3, ints[3] - ints[0] , ints[4] - ints[1], ... 계속 한칸씩 밀려가
answer = Math.max(sum, answer);
}
return answer;
}
public static void main(String[] args) {
MaximumSales T = new MaximumSales();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] ints = new int[n];
for (int i = 0; i < n; i++) {
ints[i] = sc.nextInt();
}
System.out.println(T.solution(n, k, ints));
}2) 연속합
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int max = 0;
int[] arr = new int[n];
int[] dp = new int[n]; // max 값 비교를 위한 다이나믹프로그래밍 배열
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
// System.out.println("arr[i]: "+ arr[i]);
}
/*
* dp[0]은 첫 원소로 이전에 더이상 탐색할 것이 없기 때문에
* arr[0] 자체 값이 되므로 arr[0]으로 초기화 해준다.
* max 또한 첫 번째 원소로 초기화 해준다.
*/
dp[0] = arr[0]; // 초기화
max = arr[0]; // max 초기화
for (int i = 1; i < n; i++) { // n-1 까지
// (이전 dp + 현재 arr값) 과 현재 arr값 중 큰 것을 dp에 저장
dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
// max 갱신
max = Math.max(max, dp[i]);
}
System.out.println(max);
}Sliding Window(짧은 문자거리)
public int[] solution(String s, char t) {
// index 표현을 위해 int[]로 썼던 것
int[] answer = new int[s.length()];
int p = 1000;
// 왼쪽부터 시작하는 loop
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == t) {
p = 0;
answer[i] = p;
}
else {
p++;
answer[i] = p;
}
}
// 오른쪽부터 시작하는 loop
for (int i = s.length()-1; i >=0 ; i--) {
if(s.charAt(i)==t) p=0; // 이미 왼쪽 loop할 때 넣었으니 0처리
else{
p++;
answer[i] = Math.min(answer[i], p); // 기존의 배열값들 중 비교해서 작은 걸로 다시 넣는다.
}
}
return answer;
}문자열 압축
private String solution(String str) {
String answer = "";
int count = 1;
for (int i = 0; i < str.length()-1; i++) {
// char[] chars = str.toCharArray();
if (str.charAt(i) == str.charAt(i + 1)) { // 이것때문에 i < str.length()-1; 해주는 것!
count++;
// answer +=
} else {
answer += str.charAt(i);
if (count > 1) answer += String.valueOf(count);
count = 1;// count 초기화
}
}
return answer;
}각 자릿수 합
public int solution(String str) {
int answer = 0;
String[] split = str.split("");
for (int i = 0; i < split.length; i++) {
answer += Integer.parseInt(split[i]);
}
return answer;
}
// 1242
// 9 public int solution(int n) {
int answer = 0;
for (char chNum : String.valueOf(n).toCharArray()) {
System.out.println(chNum);
answer += chNum - '0';
}
return answer;
}
이진탐색트리 - DFS로 구현
class Node{
int data;
Node lt, rt;
public Node(int val) {
data=val;
lt=rt=null;
}
}
public class NodeDFS{
Node root;
public void DFS(Node root){
if(root==null)
return;
else{
DFS(root.lt);
System.out.print(root.data+" ");
DFS(root.rt);
}
}
public static void main(String args[]) {
NodeDFS tree=new NodeDFS();
// 중위순회
tree.root=new Node(1);
tree.root.lt=new Node(2);
tree.root.rt=new Node(3);
tree.root.lt.lt=new Node(4);
tree.root.lt.rt=new Node(5);
tree.root.rt.lt=new Node(6);
tree.root.rt.rt=new Node(7);
tree.DFS(tree.root);
}
}DFS(타겟넘버)
public class Main {
int[] numbers;
int target;
int answer;
void dfs(int index, int sum) {
// 1. 탈출 조건
if (index == numbers.length) {
if(sum == target) answer++;
return;
}
// 2. 수행동작
dfs(index+1, sum+ numbers[index]);
dfs(index+1, sum- numbers[index]);
}
private int solution(int[] numbers, int target) {
answer = 0;
this.numbers = numbers;
this.target = target;
dfs(0,0);
return answer;
}
}경로탐색(인접리스트, ArrayList)
/*
인접행렬과 인접리스트 두 가지 방법으로 풀이한다.
정점의 개수가 많은 경우 인접행렬을 사용하면 그만큼의 2차원 배열을 만들어야 하기 때문에,
정점의 개수가 1000개, 10000개와 같이 많을 때는 인접리스트를 사용하는 것이 좋다.
*/
class Main{
static int n, m, answer = 0;
static ArrayList<ArrayList<Integer>> graph;
static int[] ch;
public void DFS(int v) {
if(v==n) {
answer ++;
}else {
for(int nv : graph.get(v)) {
if(ch[nv] == 0) {
ch[nv] = 1;
DFS(nv);
ch[nv] = 0;
}
}
}
}
public static void main(String[] args) {
Main T = new Main();
Scanner in = new Scanner(System.in);
// 정점의 갯수
n=in.nextInt();
// 간선의 갯수
m=in.nextInt();
// 인접리스트 초기화
graph = new ArrayList<ArrayList<Integer>>();
for(int i=0; i<=n; i++) {
graph.add(new ArrayList<Integer>());
}
ch = new int[n+1];
// 값 넣기
for(int i=0; i<m; i++) {
int a = in.nextInt();
int b = in.nextInt();
graph.get(a).add(b);
}
ch[1] = 1;
T.DFS(1);
System.out.println(answer);
}
}BFS(그래프 최단거리)
import java.util.*;
class Main {
static int n, m, answer=0;
static ArrayList<ArrayList<Integer>> graph;
static int[] ch, dis;
public void BFS(int v){ // v : 현재 정점
// 초기화
ch[v]=1;
dis[v]=0;
Queue<Integer> queue=new LinkedList<>();
queue.offer(v);
while(!queue.isEmpty()){
// cv : 현재 정점
int cv=queue.poll();
for(int nv : graph.get(cv)){
// ch: 방문체크, 방문 안한 정점만 방문
if(ch[nv]==0){
ch[nv]=1;
queue.offer(nv);
dis[nv]=dis[cv]+1; // dis[nv] 다음 거리
}
}
}
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
n=kb.nextInt(); // 정점의 갯수
m=kb.nextInt(); // 간선의 갯수
graph=new ArrayList<ArrayList<Integer>>();
for(int i=0; i<=n; i++){
graph.add(new ArrayList<Integer>());
}
ch=new int[n+1]; // 방문체크배열
dis=new int[n+1]; // 거리
for(int i=0; i<m; i++){
int a=kb.nextInt();
int b=kb.nextInt();
graph.get(a).add(b);
}
// 출발지점은 1번 정점
T.BFS(1);
for(int i=2; i<=n; i++){
System.out.println(i+" : "+dis[i]);
}
}
}학생학번 검색 프로그램
https://velog.io/@mooh2jj/JAVA-학생-학번-검색-프로그램
// 학생 이름 -> 학번 확인
List<Student> students = new ArrayList<>();
students.add(new Student("도성곤", 1111));
students.add(new Student("이선경", 1222));
students.add(new Student("도명수", 1233));
String name = "도성곤2";
int answer = 0;
// 학번이 나오게
for (int i = 0; i < students.size(); i++) {
if (name.equals(students.get(i).getName())) {
answer = students.get(i).getStuNum();
}
}
if (answer == 0) {
throw new IllegalStateException("맞는 학생이 없습니다.");
}
System.out.println(answer);괄호문자제거 - Stack
public static void main(String[] args) {
String str = "(A(BC)D)EF(G(H)(IJ)K)LM(N)";
String answer = "";
Stack<Character> stack = new Stack<>();
for (char ch : str.toCharArray()) {
if (ch == '(') {
stack.push(ch);
} else if (ch == ')') {
stack.pop(); // 기존의 '('을 제거 하는 것
} else {
if (stack.isEmpty()) {
answer += ch;
}
}
}
System.out.println(answer);
}
배운 것을 기록합니다.