[코딩테스트] 준비 및 유형별 풀이 정리

 

*  코딩테스트 보는 이유?

 

- 개발자의 능력은 빠르고 많이 만드는 것이 아닌 정확하고 효율적으로 만드는 것

- 코딩테스트를 통과하려면 코드 효율성을 고려하면서 코드를 작성해야 하기에 이를 준비하는 과정에서 개발자에게 필요한 최소한의 역량을 갖추는데 도움이 됨

 

* 잘 작성한 코드란?

- 가독성과 효율성

- 가독성 높이기 위해서는 코드가 길어지거나 중복되는 부분이 발생한다면 변수와 메서드, 클래스를 적극적으로 활용

- 효율성 높이기 위해서는 시간복잡도를 고려

 

* 디버깅과 시행착오 줄이기

1. 코드 단계별로 작성

2. 하나의 단계 작성 후, 로그를 찍어보며 검증

3. 단계 검증 실패 시, 실패한 단계내에서 자세히 로그 탐색

 

 

1. 배열

 

- 2차원 배열 : y 좌표 접근 후 -> x 좌표 접근

 

ex) int arr[][]={{8,5,9}, {2,6,1}, {3,4,8}, {8,5,9}};

int element=arr[3][2]; -> y좌표인 3에 접근 후, x좌표인 2에 접근

 

- 상하좌우 비교

int dx[]={-1,0,1,0}, int dy[]={0,1,0,-1};

-> 상하좌우의 위치한다고 가정 후, 배열의 범위에 벗어나는지 체크

 

 

2. 문자열

 

- 문자의 배열

 

> String.charAt(int idx) : 주어진 인덱스에 있는 문자를 char 형식으로 반환 (하나)

> String.toCharArray() : 모든 문자가 들어있는 char[] 형식의 데이터를 반환 (여러개)

 

- 아스키 코드

 

문자는 내부적으로 정수로 취급되고 연산됨

따라서, 문자를 정수로 정수를 문자로 바꿀 수 있음

 

ex) 대문자 :  'A' ~ 'Z' : 65 ~ 90

소문자 :'a' ~ 'z' : 97 ~ 122

 

- StringBuilder

 

문자열을 이어붙이는 데 이용

 

> StringBuilder.toString() : 문자열을 String 형식으로 반환

> StringBuilder.append(char c) : 문자c를 문자열 끝에 이어 붙임

> StringBuilder.length() : 문자열 길이를 반환

> StringBuilder.reverse() : 문자열을 뒤집음

 

- Character 클래스

 

> Character.isAlphabetic(char c) : 알파벳이 아닌 문자는 그대로 반환할 수 있도록 함

> Character.isDigit(char c) : 문자 c가 숫자형인지 검사

 

ex) if(!Character.isAlphabetic(c)) return c;

-> 문자 c가 알파벳이 아닌 경우 출력하도록 함

 

 

 

> Character.toUpperCase(char c) : 해당 문자를 대문자로 변환

> Character.toLowerCase(char c) : 해당 문자를 소문자로 변환

 

- String 클래스

 

> toUpperCase() : 대상 문자열을 모두 대문자로 변환

> toLowerCase() : 대상 문자열을 모두 소문자로 변환

 

> indexOf(String str) : 특정 문자열의 위치를 찾아 인덱스 반환 (없는 경우 -1)

> indexOf(String str, int fromIdx) : 문자열이 길게 이어졌을 때 특정한 문자열의 빈도 체크 후 인덱스 반환

 

- 문자열 변환

 

> Integer.toString(int v) : String형 반환

-> 숫자를 문자열로 변환

> Integer.toString(int v, int radix) : 10진수 -> n진수

-> 10진수를 n진수로 변환시에는 값을 int형으로 받아 String형으로 출력

 

> Integer.parseInt(String s) : int형 반환

-> 문자열을 숫자로 변환

> Integer.parseInt(String s, int radix) : n진수 -> 10진수

-> 10진수를 제외한 나머지 진수는 값을 String으로 받아 int형으로 출력

 

-> 둘의 차이는 10진수만 int형으로 취급된다라고 생각하면 됨

 

> str.substring(int idx) : idx부터 문자열 끝까지 반환

> str.substring(int startIdx, int lastIdx) : startIdx부터 lastIdx까지 반환 (lastIdx 불포함)

 

 

- 포함여부를 검사하는 메서드

 

> contains(String s) : 대상 문자열 s가 특정 문자열에 포함되어 있는지 확인

> startsWith(String s) : 대상 문자열 s로 시작하는지 검사

> endsWith(String s) : 대상 문자열 s로 끝나는지 검사

> indexOf(String s) : 대상 문자열 s가 몇 번째 인덱스에 있는지 검사

 

- 정규표현식 관련 메서드

 

>> replaceAll(String regex, String replacement) : 반환형(String)

전달받은 정규표현식에 매칭되는 패턴을 모두 replacement로 치환

>> matches(String regex) : 반환형 boolean

문자열이 전달받은 정규표현식에 매칭되는지 여부를 반환

>> split(String regex) : 반환형 String[]

전달받은 정규표현식에 매칭되는 패턴을 기준으로 원본 문자열을 잘라서 반환

 

 

3. 탐색

<완전 탐색>

- 모든 경우의 수를 확인하는 탐색 기법으로, 정확성이 높은 탐색

- 단, 모든 경우의 수를 확인하기 때문에 시간 복잡도를 잘 확인해봐야 함

 

<이진 탐색>

- 이진 탐색이란, 찾고자 하는 정답이 포함된 범위 중 가운데를 검사하고, 정답과 비교하여 절반의 범위를 제외하며 찾아나가는 탐색 기법이다.

- 전제 조건 = 배열이나 리스트가 정렬이 되어 있어야 대소 비교를 하며 정답이 없는 구간을 확실히 제외할 수 있음

 

- HashSet 출력

 

HashSet<Integer> set=new HashSet<>();

 

Iterator iter=set.iterator();

while(iter.hasNext()){

  System.out.println(iter.next());

}

 

4. 정렬

 

- 오름차순 / 내림차순 정렬

 

(1) 배열인 경우

오름차순 : Arrays.sort()

내림차순 : Integer 타입으로 변환 후, Arrays.sort(배열명, Collections.revserseOrder()) 

(2) 컬렉션인 경우

오름차순 : Collections.sort()

내림차순 : Collections.sort(컬렉션명, Collections.revserseOrder())

 

- 사용자 지정 함수

 

Arrays.sort(배열명, new Comparator<타입>(){

    public int compare(타입 o1, 타입 o2) {

           return 0;

      }

});

(람다 표현식)

Arrays.sort(배열명, (o1,o2) -> {

 

});

 

5. 동적 프로그래밍

동적 프로그래밍이란 완전 탐색의 일종으로, 이미 계산된 결과를 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 설계함으로써 수행시간 효율성을 향상시키는 방법