코딩 테스트 합격자 되기 정리 #1

사전 준비

• 분석 먼저
• 예외 테스트 케이스
• 기록 - 못푼것도 기록은 해두자
• 나만의 언어로 요약

문제 분석

• 문제를 쪼개서 분석
• 제약사항과 테스트 케이스
• 입력값 분석하고 알고리즘 설정
• greedy, 완전 탐색 뭘로 할지
• 데이터 흐름과 구성 파악
• 의사 코드로 설계

채점기준

• 정확성 테스트
• 효율성 테스트

시간복잡도

• O(N) 허용 연산 횟수는 2000만
• 초당 연산 최대 횟수는 1억번, 제한시간이 1초면 연산 횟수가 3000만이 안넘도록
• 지수함수, 다항함수, 로그함수
• 입력 크기에 따른 연산 횟수의 추이를 활용해서 시간복잡도를 표현하는 방법 - 점근적 표기법
• 특정값을 계속 반으로 줄이는 동작을 한다면 O(logN)

코딩 테스트 필수 문법

프리미티브 타입 / 레퍼런스 타입

• int, long, float, double
• Integer, Long, Float, Double - 연산 속도는 느림
• 엡실론 epsilon - 부동소수형 데이터를 이진법으로 표현해서 생기는 오차
• 비트연산

&, |, ^ XOR, ~ NOT, <<, >>

• 논리연산

&&, ||, !(x>y)

컬렉션 프레임워크

배열

• 연속된 메모리 공간
• 생성이후 크기 변경 불가, 새 데이터를 삽입,삭제 불가. 변경만 가능
• index로 요소 접근 - index를 알고 있다면 접근,변경은 O(1)

int[] array = {1,2,3,4,5};
int[] array2 = new int[]{1,3,5,7,9};
int[] array3 = new int[5];

리스트 ArrayList (사실 LinkedList 도 있음)

• 가변 크기
• 맨 뒤 추가시 O(1), 삭제나 중간 삽입은 O(N)

해시맵 hashmap

• key, value

// Integer = 32bit = 4byte
HashMap<String, Integer> map = new HashMap<>();

// 삽입 
map.put("apple", 1);

// 검색
if(map.containsKey(key)) { ... }

map.get(key);

// 삭제
map.remove(key);

문자열

• immutable 객체 - 값을 변경할 수 없는 객체, 시간 복잡도 관점에서도 주의
• 추가, 삭제시 기존 객체를 수정하는 것이 아니라 새로운 객체를 반환한다.
• 수정

.replace("a", "");

StringBuffer, StringBuilder

Sytem.out.println(System.identityHashCode(s));

long start = System.currentTimeMillis();
StringBuilder s = new StringBuilder();
for(int i=0; i<=100_000; i++) {
    s.append(i);
} 
long end = System.currentTimeMillis();
System.out.println(((end-start)/1000.0) + "초"); 

• 차이 StringBuffer 는 Thread-Safe (코딩테스트에서는 거의 안씀)
• 속도면에서 StringBuilder 가 조금 더 빠름(코딩테스크 기준 권장)

sb.deleteCharAt(index)
sb.insert(index, 문자);

Stack

Queue

ArrayDeque (덱 혹은 데크 라고 읽음)

• 양방향 queue, 즉 앞쪽, 뒤쪽에서 pop 가능

메서드

• 람다식 / 익명함수 - 한번만 사용하거나 함수자체를 다른 함수의 인자로 전달(고차함수)

Node[] nodes = new Node[5];
Arrays.sort(nodes, (o1,o2) -> Integer.compare(o1.cost, o2.cost));


Arrays.sort(nodes, new Comparator<Node>() {
    @Override
    public int compare(Node o1, Node o2) {
        return Integer.compare(o1.cost, o2.cost);
    } 
}

• Integer.compare(int x, int y) 는 x<y면 -1, x>y면 1, x=y면 0

코드 구현 노하우

• 조기 반환
• 보호 구문

List<Integer> numbers
...
int total = numbers.stream().mapToInt(i->i).sum();

• 제네릭

List<Integer> genericList = new ArrayList<>();
// 빌드 레벨에서 타입체크하여 타입 강제