알고리즘 구현 시 자주 등장하는 유형(개념) - JAVA

----

업데이트 중!

 

자주 까먹는 메소드

 

ArrayList, LinkedList의 .indexOf(Integer, String형 등) - 해당 element의 index 반환, 없으면 -1

ArrayList, LinkedList의 .addAll(List 형) - 해당 리스트에 parameter로 주어지는 리스트의 요소를 모두 추가

StringBuilder의 .setCharAt(index, char형) - 해당 index에 문자를 해당 요소로 바꿈

TreeMap의 .ceilingKey(int 형 등 숫자) - 인자 값으로 넘어온 숫자보다 큰 key 값들 중에 가장 작은 key 값 반환

Math 클래스의 .round(double 형 숫자) - 인자 값으로 넘어온 실수를 소수점 아래 첫째자리에서 반올림

 

문자열 parsing 구현 시

 

String 클래스의 .split() 메소드나 StringTokenizer 클래스를 이용하면된다.

 

1. .split(String delim) : 구분자를 문자열 형태로 넣어주면된다.

다만, 구분자 조건을 여러 개 주고 싶을 때는 | 로 구분해서 넣어주면 된다.

ex> "1&6*3#2"  -> .split("&|*|#")

(단, 구분자 조건 중에 개행 문자의 경우에는 앞에 \\를 추가해서 넣어주어야 에러가 나지 않는다.) ('+', '*'의 경우는 \\+, \\*으로 나타내기)

 

2. .split(String delim, -1) : 뒷 부분 문자열이 빈 문자열일 경우에도 그대로 파싱해해서 결과값을 리턴해준다.

ex> String str = "1::";String [] arr = str.split(":", -1);    -> 1, "", ""이 리턴된다.-1을 파라미터로 주지 않으면 arr 배열의 길이는 1이 된다!

 

2. StringTokenizer 클래스 (java.util 패키지)

 

StringTokenizer st = new StringTokenizer(String str, String delim, boolean returnDelims);

str: 자르고자하는 문자열

delim: 구분자

returnDelims: 리턴 결과에 구분자도 포함할지 여부

 

메소드 정리

.countTokens()    : 토큰 수 반환

.nextToken()       : 다음 토큰

.hasMoreTokens() : 리턴할 다음 토큰이 있으면 true, 없으면 false 반환

 

시뮬레이션 구현 시

 

특정 점에서 막힐 때까지 이동하기

int nextX = i;     //시작 위치

while(true){
	if(nextX + 1 >= A.length || A[nextX + 1][j] != 0) break;
	nextX++;
}

 

배열에서 오른쪽에 있는 수 중에서 가장 가까운 큰 수 or 작은 수 구하기

2

1

4

3

6

 ex> 2의 오큰수 구하기 => 4

스택 이용!

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

for(int i=0;i<A.length;i++){
	if(i == 0){
    	st.push(A[i]);
        continue;
    }
    if(st.peek() < A[i]){
    	while(st.peek() < A[i]){
        	st.pop();
        }
        st.push(A[i]);
    }else{
    	st.push(A[i]);
    }
}

 

가장 긴 연속된 수의 길이 구하기

int cnt = 1;
int max = Integer.MIN_VALUE;

for(int i=1;i<N;i++){
	if(A[i] == A[i-1]){
    	cnt++;
    }else{
    	if(max < cnt)
        	max = cnt;
    	cnt = 1;
    }
}

 

연속된 값의 이동 like 큐빙 주사위, 미세먼지 안녕

 

다음과 같은 배열에서 값을 이동시켜야 할 때

다음과 같이 배열에서 값을 한 칸씩 다음과 같은 방향으로 이동시켜야 한 다면 양 끝 모서리에 해당하는 값들을 미리 저장해 둔 후,

 

한 줄 씩

for (int i = 0; i < C - 1; i++) {
		A[0][i] = A[0][i + 1];
}

칸을 이동시켜주면 된다!