자바로 ps를 시작하기로 한 이유는 삼성SW 역량테스트 기준, 다양한 공채 코테에서 자바를 사용하는 비율이 높았기 때문이다.
아마도 이번 자바 코테 준비를 기점으로 취준용 코테 언어는 자바로 정착할 생각이다.
블로그에 코테 공부를 정리하기 전에는 파이썬으로 준비를 했다.
파이썬은 표준 라이브러리나 타입 안정성을 고려할 필요가 없어서 사용했었던 기억이 있다.
블로그는 작성자의 수준, 환경이 제각각이라
Do it! 알고리즘 코딩 테스트 - 자바편 책을 기준으로 공부를 시작하기로 했다.
책 목차가 코테에 최적화된 자료구조 알고리즘으로 나뉘어있어서 머리속에 혼재해있던 개념들을 정리하는 기회도 될 듯 싶다.
시간복잡도
학부생 시절 귀에 딱지나도록 들었던 시간 복잡도,
코테에 있어서 뿐만 아니라 실무에서도 너무나도 중요한 개념이 아닐까?
주어진 시간에 특정 문제를 해결하기 위한 연산 횟수를 의미하는 시간복잡도는 주로 3가지 방법으로 표현된다.
- 빅 오메가 : 최선일 때(best case)의 연산 횟수 표기법
- 빅 세타 : 보통일 때(average case)의 연산 횟수 표기법
- 빅 오 : 최악일 때(worst case)의 연산 횟수 표기법
당연하게도 코테에서는 빅 오 표기법을 기준으로 수행 시간을 계산한다.
그렇다면 시간복잡도는 어떻게 계산할 수 있을까?
두가지 기준만 고려한다면 빅 오 표기법의 시간복잡도를 계산할 수 있다.
- 상수는 시간 복잡도 계산에서 제외
- 가장 많이 중접된 반복문의 수행 횟수가 시간 복잡도의 기준(최고차항이 기준)
간단한 자바 코드로 알아보자,
# O(N)
public static void n_time_complex() {
int N=100;
int cnt=0;
for(int i=0;i<N;i++){
System.out.println(cnt++);
}
}
# O(N^2)
public static void n_quare_time_complex(){
int N=100;
int cnt=0;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
System.out.println(cnt++)
}
}
}앞서 서술한 두가지 조건만 따른다면 시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출된다.
이 예제는 단순이 for문의 중첩만 세어보면 간단히 시간복잡도를 알 수 있으나 앞으로 공부하게될 이진탐색, 트리, 분할정복같은 문제는 log N의 형태를 보이기도한다.
입출력 방식 최적화
Scanner와 System.out.print대신 BufferedReader와 BufferedWriter를 사용하면 입출력 처리 속도를 향상할 수 있다.
이 방법을 사용하지 않으면 입출력 시간 초과로 통과하지 못하는 문제들이 많기 때문에 어지간하면 BufferedReader와BufferedWriter를 사용하자.
그런데 왜 이 둘 사이에 시간차가 발생하는 것일까?
우선 이를 이해하기 전에 정규표현식에 대해 공부할 필요가 있다.
정규표현식(Regular Expression)
정규표현식이란 특정 규칙을 가진 문자열 집합을 표현하기 위해 존재하는 형식 언어로써 주로 문자열의 패턴을 표현하는 용도로 사용한다.
보통 이를 RegEx혹은 RegExp로 표현한다.
여러 메타문자로 특정 규칙을 가진 문자열을 탐색할 수 있는데, 예를 들어
^java: 문자열이 'java'로 시작하는 문자열java$: 문자열이 'java'로 끝나는 문자열\bjava\b: 좌우가 시작,끝,공백( ),콤마(,),개행(tab),온점(.),대시(-) 등 으로 한 단어 'java'로 구분되는 문자열
물론 이 정규식은 POSIX 표준식이고 grep엔진의 종류마다 사용하는 정규표현식은 다르다.
URL: 자바 정규표현식
Scanner는 입력할 때마다 해당 입력이 정규표현식인지 검사하고
private Scanner(Readable source, Pattern pattern) {
assert source != null : "source should not be null";
assert pattern != null : "pattern should not be null";
this.source = source;
delimPattern = pattern;
buf = CharBuffer.allocate(BUFFER_SIZE);
buf.limit(0);
matcher = delimPattern.matcher(buf);
matcher.useTransparentBounds(true);
matcher.useAnchoringBounds(false);
useLocale(Locale.getDefault(Locale.Category.FORMAT));
}
public Scanner(InputStream source) {
this(new InputStreamReader(source), WHITESPACE_PATTERN);
}// this로 private(Readable source, Pattern pattern) 호출
private static Pattern WHITESPACE_PATTERN = Pattern.compile("\\p{javaWhitespace}+");InputStreamReader는 byte를 char로 변환해주는데, Scanner 내부에도 있는걸 보면 결국 BufferedReader 쓰든 안쓰든 결국 regex분석 후 token화 하냐 안하냐의 차이인 것을 알 수 있다.
System.in 바이트 스트림을 char로 변환하긴 하는데, BufferStreamReader는 토큰화를 안하고 \n,\r이 나올 때까지 버퍼에 넣기만 하기 때문에 시간이 덜 걸리는 것이다.
BufferStreamReader,BufferstreamWriter 사용법
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int b = Integer.parseInt(st.nextToken());
bw.write(String.valueOf(b));
bw.write(b+"");
bw.flush();
}
}