자질구레한 알고리즘 모음

배열의 각 Elem을 곱하여 더한 값을 구하라

ex) arr = [1, 3, 5, 9]  →  {1*3 + 1*5 + 1*9} + {3*5 + 3*9} + {5*9}

 

방법1) 이중 for문 사용

for (int i=0; i<arr; i++) {
	for (int j= i+1; j<arr; j++) {
		answer += plan[i] * plan[j];
	}		
}

방법2) ab + ac + ad == a ( b + c + d ) 동치임을 이용

for (int i=0; i<numStick; i++) {
	arr[i] = Integer.parseInt(st.nextToken()); // arr = [1,3,5,9]
	total += plan[i]; // total = 18
}

for (int i=0; i<numStick; i++) {
	total = total - plan[i]; // (a+b+c+d - a) → (b+c+d - b) → (c+d - c) → (d -d)
	answer += plan[i] * total; // a * (b + c + d) += b(c + d) += c(d) += 0
}

※방법2를 사용하면 O(N^2) --> O(N) 훨씬 단축이 가능하다!

방법1 사용

방법2 사용

 

 

특정 길이만큼 문자열 잘라서 List에 저장

ex) str = "0123456789ㄱㄴㄷㄹㅁㅂㅅㅇㅈㅊabcdefghij!@#"

List = ["0123456789"] [ㄱㄴㄷㄹㅁㅂㅅㅇㅈㅊ] [abcdefghij] [!@#]

 

	public static void main(String[] args) {
		final int LIMIT = 10;
		String source = "0123456789abcdefghijABCDEFGHIJ!@#$%^&*()ZZZ";
		int length = source.length();
		List list = new ArrayList(length/LIMIT+10);
		
		for (int i=0; i<length; i+=LIMIT) { // 10단위로 스캔
			/*LIMIT개수만큼 String이 남아있다면 LIMIT만큼 담기*/
			if (i+LIMIT < length) 
				list.add(source.substring(i, i+LIMIT));
			/*LIMIT개수 미만으로 남아있다면 나머지 다 담기*/
			else 
				list.add(source.substring(i));
		}
		
		for (int i=0; i<list.size(); i++) {
			System.out.println(list.get(i));
		}
		
	}

추가설명

1. ArrayList의 가변기능은 처리시간이 많이 소요되기 때문에 약간 여유있게 선언하여 가변기능을 지양해야한다.

List list = new ArrayList(length/LIMIT+10);

ArrayList를 이용한 자료구조는 데이터를 읽어오고 저장하는 데는 효율이 좋지만, 용량을 변경해야할 때는 "새로운 배열을 생성"한 후 기존의 배열로부터 새로 생성된 배열로 데이터를 복사해야하기 때문에 상당히 효율이 떨어진다. 

 

 

Set 자료구조를 이용한 합,교,차집합 구하기

ex) A=[1, 2, 3, 4, 5],  B=[4, 5, 6, 7, 8]

A∩B = [4, 5]  → retainAll

A∪B = [1, 2, 3, 4, 5, 6, 7, 8]  →  addAll

A - B = [1, 2, 3]  →  removeAll

 

메소드를 이용해도 되지만, 파악은 해두자

Iterator it = setB.iterator();
/*교집합*/
while(it.hasNext()) {
	Object tmp = it.next();
	if (setA.contains(tmp)) {
		setKyo.add(tmp);
	}
}
/*차집합*/
it = setA.iterator();
while(it.hasNext()) {
	Object tmp = it.next();
	if(!setB.contains(tmp)) {
		setCha.add(tmp);
	}
}
/*합집합*/
it = setA.iterator();
while(it.hasNext()) {
	setHab.add(it.next());			
}
it = setB.iterator();
while(it.hasNext()) {
	setHab.add(it.next());			
}