0. 시간복잡도

  • 초당 100,000,000(1억)번 연산이 가능하다

★시간 제한이 1초인 경우

N의 범위 시간복잡도
10 O(n!)
20 O(2n)
500 O(N3)
10,000 O(N2)
5,000,000 O(NlogN)
100,000,000 O(N)

1. 자료구조

1. List

(1) Array

(1) length : 배열길이 출력

int[] arr = new int[n];       // 1차원 배열
int[][] arr = new int[n][m];  // 2차원 배열

Arrays 라이브러리

(1) sort(arr) : 배열 정렬
(2) copyOfRange(arr, s, e) : 배열 자르기

int[] array = {5,2,3,4,1};
int[] temp = Arrays.copyOfRange(array,1,3);   // [2, 3]

Arrays.sort(array);     // [1, 2, 3, 4, 5]
Arrays.sort(array, Collections.reverseOrder());     // [5, 4, 3, 2, 1]

(3) fill(arr, value) : 해당 배열의 모든 값을 value로 채움

int[] arr = new int[10];
Arrays.fill(arr, 7);

(4) toString(arr) : 배열 출력
(5) deepToString(arr) : 2차원 배열 출력

  • 배열 최대값, 최소값
    • Arrays.stream(arr).max().getAsInt()
Arrays.stream(arr).max().getAsInt();

(2) ArrayList

Method Complexity
insert O(n)
delete O(n)
get O(1)
sort O(nlogn)

(1) add(v) : 맨 뒤에 삽입
(2) add(i, v) : i에 삽입
(3) addAll(list) : 해당 리스트 뒤에 list의 값들 삽입

(4) get(i) : 조회
(5) set(i, v) : i의 값 변경
(6) indexOf(v) : 값의 인덱스 출력
(7) lastIndexOf(v) : 값의 마지막 인덱스 출력

(8) remove(i) : i의 값을 삭제
(9) remove(v) : 리스트에서 값 v를 삭제
(10) removeAll(list) : 해당 리스트에서 list의 값들 삭제
(11) retainAll(list) : 해당 리스트에서 list의 값들을 제외하고 삭제

(12) isEmpty() : 비어있는지 확인
(13) size() : 리스트 크기 출력
(14) contains(v) : 값이 있는지 확인
(15) sort() : 오름차순 정렬

  • 깊은 복사
    • addAll(list) 사용
ArrayList<Integer> old=new ArrayList<Integer>();
ArrayList<Integer> new=new ArrayList<Integer>();
new.addAll(old);

캐스팅

  1. String
    • array -> List
      • Arrays.asList(arr) 사용
String[] temp = {"a", "b", "c"};
List<String> list = Arrays.asList(temp);    // size 불변 리스트

// size 가변 리스트
List<String> list = new ArrayList<>(Arrays.asList(temp));
  • List -> array
    • toArray() 사용
List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c"));
String[] temp = list.toArray(new String[list.size()]);  // 배열 사이즈 설정까지
  1. int
    • List -> int[] 
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
int[] temp = list.stream().mapToInt(i->i).toArray();
  • int[] -> List 
int[] arr = {1, 2, 3};
List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());

// 쉬운방법
List<Integer> list = new ArrayList<>();
for (int num : arr) {
    list.add(num);
}

2. Set

Method Complexity
insert O(1)
delete O(1)
get O(1)

(1) add(v) : 삽입
(2) remove(v) : 삭제
(3) contains(v) : 값이 있는지 확인
(4) size() : 해당 셋의 크기출력
(5) iterator() : 해당 셋의 이터레이터 호출

Set<String> set = new HashSet<String>();
set.add("서울");
set.add("대전");
set.add("인천");
set.add("부산");

set.remove("인천");

set.size();     // 3

Iterator<String> it= set.iterator();
while (it.hasNext()) {
    String a= it.next();
    System.out.println(a);
}

캐스팅

  • Set -> List
Set<String> set = new HashSet<String>();
List<String> menuList = new ArrayList<>(set);

3. Map

Method Complexity
insert O(1)
delete O(1)
get O(1)

(1) put(k, v) : 삽입
(2) get(k) : value값 조회
(3) remove(k) : 삭제

(4) containsKey(k) : 키값 존재 확인
(5) containsValue(v) : 값 존재 확인
(6) isEmpty() : 비어있는지 확인

(7) keySet() : 모든 key값을 Set으로 출력
(8) values() : 모든 value값을 Collection으로 출력
(9) entrySet() : 모든 key-value쌍을 Set으로 출력

  • getOrDefault(value, default값) : 값 조회, 없을 시 디폴트값
HashMap<String, Integer> map = new HashMap<>();
for(int i=0; i<genres.length; i++){
    map.getOrDefault(genres[i], 0);
}

정렬

Map<String, Integer> map = new HashMap<>();
map.put("apple", 5);
map.put("banana", 2);
map.put("cherry", 5);
map.put("date", 3);
  • key로 정렬
List<Map.Entry<String, Integer>> entryList = new ArrayList<>(map.entrySet());

entryList.sort(o1, o2) -> o2.getKey() - o1.getKey());   // key 내림차순
  • value로 정렬
List<Map.Entry<String, Integer>> entryList = new ArrayList<>(map.entrySet());

entryList.sort(o1, o2) -> o1.getValue() - o2.getValue()); // value 오름차순
  • value 1순위, key 2순위로 정렬
List<Map.Entry<String, Integer>> entryList = new ArrayList<>(map.entrySet());

// 정렬: value 기준으로 내림차순 -> key 기준으로 오름차순
entryList.sort((o1, o2) -> {
    if (o1.getValue().equals(o2.getValue())) {
        return o1.getKey().compareTo(o2.getKey()); // key 오름차순
    }
    return o2.getValue() - o1.getValue();   // value 내림차순
});


banana: 2
date: 3
apple: 5
cherry: 5

4. Stack

  • Stack 클래스 사용
Method Complexity
push O(1)
pop O(1)
peek O(1)

(1) push(v) : 삽입
(2) peek() : 조회
(3) pop() : 삭제
(4) empty() : 비어있는지 확인
(5) contains(v) : v 값이 있는지 확인

Stack<Integer> stack = new Stack<>();

stack.push(1);
stack.peek();     // 1
stack.pop();

stack.empty();    // true
stack.contains(1)   // false

5. Queue

  • LinkedList 클래스 사용 (Queue 인터페이스 다형성)
Method Complexity
offer O(1)
poll O(1)
peek O(1)

(1) offer(v) : 삽입
(2) peek() : 조회
(3) poll() : 삭제
(4) contains(v) : v 값이 있는지 확인

Queue<Integer> queue = new LinkedList<>();

queue.offer(1);
queue.offer(2);
queue.peek();   // 1
queue.poll();
queue.contains(2)   // true

6. Deque

  • LinkedList 클래스 사용 (Deque 인터페이스 다형성)

(1) offer(v) : 뒤로 삽입 (= offerLast(v))
(2) offerFirst(v) : 앞으로 삽입
(3) peek() : 첫번째 원소 조회 (= peekFirst())
(4) peekLast() : 마지막 원소 조회
(5) poll() : 앞으로 삭제 (= poolFisrt())
(6) pollLast() : 뒤로 삭제
(7) contains(v) : v 값이 있는지 확인

Deque<Integer> deque = new LinkedList<>();

deque.offer(1);
deque.offerFirst(2);
deque.peek();   // 2
deque.peekLast();   // 1
deque.pollLast();
deque.contains(2)   // true
deque.poll();

7. PriorityQueue

  • PriorityQueue 클래스 사용
Method Complexity etc
offer O(logn) .
poll O(logn) .
peek O(1) .
정렬 O(nlogn) n개를 모두 삽입한 후 삭제하면 정렬 가능 (삽입/삭제를 n번수행)
탐색 O(n) 최악의 경우 n개 노드 모두 탐색

(1) offer(v) : 삽입
(2) peek() : 조회
(3) poll() : 삭제
(4) contains(v) : v 값이 있는지 확인

PriorityQueue<Integer> pq = new PriorityQueue<>();    // 최소힙
PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder());  // 최대힙

pq.offer(1);
pq.peek();   // 1
pq.poll();
pq.contains(1)   // false

정렬

  • map의 value 내림차순으로 정렬
PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>( 
    (a, b) -> Integer.compare(b.getValue(), a.getValue()));

for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
    pq.offer(entry);
}
  • object 정렬 (나이 내림차순)

PriorityQueue<User> queue = new PriorityQueue<>(
  (o1, o2) -> o2.getAge() - o1.getAge()
);

2. 문자열

1. String

(1) charAt(c) : c의 인덱스 반환
(2) indexOf(str) : str의 인덱스 반환
(3) lastIndexOf(str) : str의 마지막 인덱스 반환

(4) substring(s, e) : 인덱스로 문자열 가져오기
(5) replace(a, b) : a를 b로 치환
(6) split(deli) : 문자열을 deli로 기준으로 나누어 반환
(7) join(deli, List) : 리스트 갑 사이에 deli 추가 후 String 반환

(8) toUpperCase(), toLowerCase() : 대소문자 변환
(9) trim() : 앞뒤 공백제거

(10) length() : 길이 출력
(11) equals(str) : 해당 문자열이 str과 같은지 확인
(11) contains(str) : 해당 문자열에 str이 있는지 확인
(12) compareTo(str) : 같으면 0, str보다 앞순이면 -1, 뒷순이면 1 출력

(13) startsWith(str) : str로 시작하면 true
(14) endsWith(str) : str로 끝나면 true

2. StringBuilder

(1) append(str) : 맨 뒤에 문자열 추가 (boolean, char, String, long, int, float, double 모두 가능)

StringBuilder sb = new StringBuilder();

sb.append(true);
sb.append('A');
sb.append(123);
sb.append(45.67);
sb.append("abc");

// trueA12345.67abc
System.out.println(sb.toString());

(2) insert(i, v) : i에 v 추가
(3) setCharAt(i, c) : i의 문자 변경
(4) delete(s, e) : s~(e-1) 문자열 삭제
(5) deleteCharAt(i) : i의 문자 삭제
(6) length() : 문자길이 출력

(6) indexOf(str) : str의 인덱스 반환
(7) lastIndexOf(str) : str의 마지막 인덱스 반환

(8) reverse() : 문자열 뒤집기
(9) setLength(len) : 문자열 길이 변경

StringBuilder sb = new StringBuilder();

sb.append("abc");     // abc
sb.insert(2, "defgh");   // abdefghc
sb.setCharAt(1, 'z');    // azdefghc
sb.delete(0, 2);      // defghc
sb.deleteCharAt(2);   // deghc
sb.length();          // 5

sb.setLength(4);      // degh
sb.reverse();         // hged
  • 문자열 뒤집기
    • StringBuilder(str).reverse().toString() 사용
String str = "abc";
String str2 = new StringBuilder(str).reverse().toString();   // cba

캐스팅

  • String -> char[]
    • toCharArray() 사용
String str = "12345";
char[] arr = str.toCharArray();     // [1, 2, 3, 4, 5]

String str2 = new String(arr);      // 12345
  • String -> String[]
    • split() 사용
String str = "12345";
String[] arr = str.split("");     // [1, 2, 3, 4, 5]

3. 입출력

Scanner

  • 스페이스, 탭(\t), 줄바꿈(\n)을 경계로 인식함

  • nextxxx() : 입력 받는 즉시 해당 타입으로 캐스팅
  • next() : String으로 입력받음
  • nextLine() : \n을 포함한 String으로 입력받고 strip()을 함
Scanner sc = new Scanner(System.in);
int i = sc.nextInt();
double d = sc.nextDouble();
String str = sc.next();
boolean b = sc.nextBoolean();

System.out.println(i + ", " + d + ", " + str + ", " + b);

>> 3 5.678 안녕하세요 false
3, 5.678, 안녕하세요, false
  • next()와 nextLine() 의 차이
    • next()는 String만 읽어오고 \n은 포함시키지 않는다.
    • nextLine()은 개행문자까지 읽어오기 때문에 \n을 처리한다
Scanner sc = new Scanner(System.in);

int num = sc.nextInt();
String str = sc.nextLine();

System.out.println("num: " + num + ", str: " + str);

>>> 10
Hello

num: 10, str:
  • num에 10이 들어가고 str에는 \n이 들어가 strip()이 되어 결과적으로 비게된다
  • next()을 사용하면 된다
Scanner sc = new Scanner(System.in);

int num = sc.nextInt();
String str = sc.next();

System.out.println("num: " + num + ", str: " + str);

>>> 10
Hello

num: 10, str: Hello

BufferedReader

  • Scanner보다 속도가 빠르다
  • 입력 값을 모두 String으로 받아 파싱이 필수적이다
  • Exception 처리가 되어 있지 않아 try-catch를 사용해야 한다
  • readLine() : 개행문자까지 읽어옴
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String input = br.readLine();
int a = Integer.parseInt(input);

StringTokenizer

  • 문자열을 자를 때 사용한다
  • BufferedReader와 결합해 한 줄씩 입력받은 문자를 자를 때 많이 사용한다
  • StringTokenizer() : 기본 deli는 공백
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());

int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());

System.out.println(a + b);

>> 2 3
5

static class FastReader {
    BufferedReader br;
    StringTokenizer st;

    public FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    public FastReader(String s) throws FileNotFoundException {
        br = new BufferedReader(new FileReader(new File(s)));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String nextLine() {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

4. 라이브러리

1. Collections

(1) max(list), min(list) : 최대값, 최소값
(2) sort(list) : 오름차순 정렬
(3) sort(list, Collections.reverseOrder()) : 내림차순 정렬
(4) reverse(list) : 역순 정렬
(5) frequency(list, v) : list에서 v의 갯수 반환

2. Character

(1) isLetter(c) : Checks if c is a letter (a-z, A-Z)
(2) isDigit(c) : Checks if c is a digit (0-9)
(3) isLetterOrDigit(c) : Checks for letter or digit
(4) isWhitespace(c) : Checks for space, tab, newline, etc
(5) toLowerCase(c) : Converts char to lowercase
(6) toUpperCase(c) : Converts char to uppercase

3. Math

  • pow(a, b) : a^b
  • sqrt(a) : 제곱근
  • abs(a) : 절대값
Math.pow(4, 2)        // 16.0
(int) Math.sqrt(7)    // 2

4. 진법

String -> int

int num = Integer.parseInt("100", 2);   // 4

int -> String

String s = Integer.toBinaryString(4);   // 100