[1. 배열/문자열] 중복확인, 순열확인, URLify(대체), 회문순열, 하나빼기, 문자열압축, 행렬회전, 0행렬, 문자열회전

 [ Q1. 중복이 없는가 ] 

문자열이 주어진 경우, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라. 추가적으로 자료구조를 사용하지않고 풀 수 있는 알고리즘 역시 작성하라.

 

- 내 풀이 -

1. 문자열을 char배열에 넣기

2. 각배열의 요소를 반복처리 > hashmap에 있다면 중복있음 종료, 없다면 hashmap에 요소로 추가

boolean charDup(String s) {
	char[] char_set=s.toCharArray();
	HashMap map=new HashMap();
		
	for(char c:char_set) {
		if(map.containsKey(c)) {
			return true;
		} else {
			map.put(c, 0);
		}
	}
	return false;
}

*map을 이렇게 사용해도 괜찮은가? 사실 문자열 하나하나 비교하려고 하다가 자료구조를 사용해 본건데..         => 안돼요,, 알고리즘은 시간과 공간복잡도를 고려해야야 한다는 것! 내 방법은 해법 3과 유사

아래 모범답안을 통해 알게된 것은

1. 문자열은 아스키인가 유니코드인가에 따라 처리 방법이 달라진다는 것(저장용량)

2. 문자열을 체크할때는 배열, 또는 맵, 비트백터 등을 활용할 수 있다는 것

 

- 모범답안 -

주어진 문자열이 아스키코드인가? 유니코드인가? 주의

(여기서 아스키코드로 가정하고 문제풀이)

 

 해법1) 문자는 한번밖에 사용할 수 없으므로 128개의 배열에 boolean형을 저장하여 활용

 : 이 경우 시간 복잡도는 O(n), 공간복잡도는 O(1)

boolean isUniquChars(String str) {
	// 문자열의 길이가 표현가능한 문자 개수보다 많다면 당연히 중복된 요소가 존재한다는 것
	if(str.length()>128) return false;
	// 아스키코드의 개수(128)에 해당하는 배열을 선언
	boolean[] char_set=new boolean[128];
	for(int i=0;i<str.length();i++) {
		int val=str.charAt(i);
		// 해당 문자열이 이미 체크되었다면 중복값 존재한다는 뜻
		if(char_set[val]) return false;
		// 처음으로 등장한 문자라면 배열의 값을 true로 체크
		char_set[val]=true;
	}
	return true;
}

 해법2) 비트백터사용

 : 필요한 공간을 1/8로 감소 

 : 이 문제는 문자가 a~z까지만 나온다고 가정

boolean isUniqeArphabet(String str) {
	// 기준 비트백터
	int checker=0;
	for(int i=0; i<str.length();i++) {
		// a~z까지의 표현을 0~하고싶기 때문에 -'a'함
		int val=str.charAt(i)-'a'; 
		// 중복요소가 있다면
		if((checker&(1<<val)) >0) {
			return false;
		} else {
			checker |= 1<<val;
		}
	}
	return true;
}

" 자료구조를 추가적으로 사용할 수 없다면? "

해법 3) 각문자를 모든 다른 문자와 비교한다

: 즉, 내가 푼 방법은 사실 map이 아니라 문자하나하나 비교 직접하는 것으로 해야했어..!

: 이때 시간복잡도는 O(n^2)이며 공간복잡도는 O(1)

해법4) 입력문자열 수정이 가능하다면 O(NlogN)시간에 문자열을 정렬한 뒤 문자열을 처음부터 훑으며 동일한지 검사

: 단, 정렬시에는 공간복잡도가 별도로 증가한다는 점

 

 

 

 

 

 [ Q2. 순열확인 ] 

문자열 두개가 주어진 경우, 이 둘이 서로 순열관계에 있는지 확인하는 메소드를 작성하라.

 

- 내 풀이 -

1. 문자열의 길이가 같아만함

2. 문자열의 문자수를 카운트하여 배열 값을 증가 > 다른 문자열의 문자수를 카운트하여 배열값을 차감

3. 마지막 모든 요소가 0이 어야만 순열이라 판단

boolean isPurmutation(String str1, String str2) {
	if(str1.length()!=str2.length()) return false;
	
	int[] char_set=new int[128];
	for (int i=0; i<str1.length();i++) {
		int val=str1.charAt(i);
		char_set[val]++;
	}
	for (int i=0; i<str2.length();i++) {
		int val=str2.charAt(i);
		char_set[val]--;
		if (char_set[val]<0) return false;
	}
	
	// 둘을 어떻게 비교할 것인가?
	for (int i=0; i<str1.length();i++) {
		if(char_set[i]!=0) return false;
	}
	
	return true;
}

"그런데? 모든 문자를 다 순회하고 마지막에 배열의 모든 요소가 0인것을 확인하는것은 좀 비효율적인 것 같아!"

=> 해답2가 내 방법과 비슷하게 풀이되었는데, 이미 길이가 같은것을 맨 처음에 확인했기때문에, 다른 문자가 있는 경우 두번째 문자열의 차감 작업시 반드시 음수값이 발생한다는것. 즉, 굳이 비교하지 않아도 두번째 for문 속 조건문 if (char_set[val]<0) return false; 에서 이미 판단된다는 소리! 따라서 마지막에 요소검사를 하지않아도 된다는 것! 

 

- 모범답안 -

* 늘 문제의 세부사항을 확인해야한다. 예를들면 대소문자를 구별하는지? 공백처리는 어떻게 할 것인지? 등 *

 

해법1) 정렬 : 순열 관계라면 정렬된 문자열은 동일해야 하기 때문

// 풀이 1 : 정렬하여 같은지 비교 >> 문자배열에 넣고 정렬하면 빠르지롱
public String sort(String s) {
	char[] content=s.toCharArray();
	Arrays.sort(content);
	return new String(content);
}
public boolean permutation(String s, String t) {
	if(s.length()!=t.length()) return false;
	return sort(s).equals(t);
}

해법2) 문자열에 포함된 문자의 출현 횟수가 같은지 검사

// 풀이 2 : 문자 출현 횟수 비교
//  => 내가 풀이한 방법과 동일하지만 내가 간과한것!
//     길이가 똑같다면 0보다 작은것이 없다가 의미하는 것 = 똑같다
//     그러므로 내가 한것처럼 마지막 비교는 불필요하다는것!
boolean purmutation_2(String str1, String str2) {
	if(str1.length()!=str2.length()) {
		return false;
	}
	
	int[] letter=new int[128];
	char[] str1_array=str1.toCharArray();
	for (char c:str1_array) {
		letter[c]++;
	}
	for (int i=0; i<str2.length();i++) {
		int c=str2.charAt(i);
		letter[c]--;
		if (letter[c]<0) {
			return false;
		}
	}
	return true;
}

 

 

 

 

 [ Q3. URL화 ] 

문자열에 들어있는 모든 공백을 '%20'으로 바꾸어주는 메소드 작성하라. 최종적으로 모든 문자를 다 담을 수 있을 만큼 충분한 공간이 이미 확보되어 있으며 문자열의 최종길이가 함께 주어진다고 가정해도 된다. (바로 구현한다면 배열안에서 작업할 수 있도록 문자배열 이용하길 바란다.)

예제

입력: "Mr John Smith", 13

출력: "Mr%20John%20Smith"

 

- 내 풀이 - 

배열을 활용해서 풀려고 하다가.. 그냥 stringBuilder나 String.replace()메소드를 사용하면 쉬우니까..

//1)sb이용 또는 string.replace(" ","%20"); 활용
char[] c_set=str.toCharArray();
StringBuilder sb=new StringBuilder();

for(char c:c_set) {
	if(c==' ') {
		sb.append("%20");
	} else {
		sb.append(c);
	}
}

return sb.toString();

내가간과한 부분 : 문제의 정보를 이해하지못하고 활용하지못함

1. 최종적으로 모든 문자를 다 담을 수 있을 만큼 충분한 공간이 이미 확보 & 배열안에서 작업할 수 있도록

   문자배열 이용 => 즉 이 배열 안에서 수정해야한다는것 : 그렇기때문에 문자 길이가 주어진것임

2. 자바의 String은 immutable! 따라서 문자배열 char Array를 사용해야한다는 것!

 

- 모범답안 - 

* 문자열 조작 문제 풀이시 보통 문자열을 뒤에서부터 거꾸로 편집해 나감 *

왜냐하면 마지막부분에 여유공간을 만들어 유용하게 사용할 수 있기 때문

= 즉, 덮어쓸 걱정없이 문자를 바꿔나갈 수 있다는 것

이게 무슨 말인가! 문자열 크기와 동일한 크기의 배열이 아니라, 충분한 크기의 배열이 주어진거고

새로운 곳에 수정한 문자열을 만들라는것이 아니라, 똑같은 배열에 덮어쓰라는것!

이 과정에서 덮어쓸 염려가 발생하지않게 하려면 총 수정길이(늘어나기때문)를 계산해서 뒤에서부터

편집해야 수정하지않은 글자들이 덮어쓰기 될 염려가 없다는 것!

 

해법1) 문자열을 두번 훑는다

처음에는 문자열의 공백을 확인하고, 두번째는 역방향으로 진행하며 문자열을 편집한다.

공백을 만나면 다음위치에 '%20'을 복사, 공백이 아니면 원래 문자를 복사

// 모범답안 : 문자열을 거꾸로 편집
//  => 문제 자체에서 문자열은 배열로 주어지며, 배열은 딱맞는 크기가 아닌 이미 큰 배열
//  => 아.. 이래서 배열을 새로 생성 안하고 그 배열 자체를 편집! 덮어쓸 걱정 이런의미가 이해됨!
void replaceSpaces(char[] str, int trueLength) {
	int spaceCount=0, index, i=0;
	for(i=0; i<trueLength; i++) {
		//공백세기
		if(str[i]==' ') {
			spaceCount++;
		}
	}
	
	index=trueLength+2*spaceCount;
	if(trueLength<str.length) str[trueLength]='\0'; //문자열의 최종길이가 배열의 길이(이미충분히큼)보다 작다? 배열의 끝을 표기해줌
	//뒤에서부터 편집(복사or치환)
	for(i=trueLength-1;i>=0;i--) {
		// index는 길기를 표현하니까 여기서 햇갈리지않게 위치 계산 조심
		if(str[i]==' ') {
			str[index-1]='0';
			str[index-2]='2';
			str[index-3]='%';
			index-=3;
		} else {
			str[index-1]=str[i];
			index--;
		}
	}
}

 

 

 

 [ Q4. 회문순열 ]

주어진 문자열이 회문의 순열인지 아닌지 확인하는 함수 작성하라. 회문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은 구절을 의미하며 순열은 재배치를 뜻한다. 회문이 꼭 사전에 등장하는 단어로 제한될 필요 없다.

예제

입력: Tact Coa

출력: true (순열:"tca oact", "atco cta"등)

 

 

- 내 풀이 -

1. 문자열 길이가 짝수인지 홀수인지 확인

2. 짝수인경우 각 모든 문자수는 짝수, 홀수인경우 딱 하나의 문자 수만 홀수

3. 비트백터로 각 문자의 출현을 체크

=> 짝수일때는 0이여야 true, 홀수일때는 비트백터중 1비트가 1개여야 true

        => 이 부분에서 멈춤

boolean isPalindrome_m(String str) {
	// 비트백터의 활용
	int checkVector=0;
	// 문자개수 체크 : 홀수1 짝수 0
	for(int i=0;i<str.length();i++) {
		int val=str.charAt(i)-'a';
		checkVector=checkVector^(1<<val);
	}
	// 문자길이에 따른 반환
	if(str.length()%2==0&&checkVector==0) return true;
	// 1비트가 하나인지 확인
	checkVector&=(checkVector-1);
	if(str.length()%2==1&&checkVector==0) return true;
	return false;
}

"나는 '홀수일때는 비트백터중 1비트가 1개여야 true' 이 부분을 구현하지 못했어.."

아래 문제풀이를 보다가 3번 해법에서 힌트를 얻었음! 

1개만 1비트인 것을 확인할때! ★ 비트&(비트-1)==0 기억하기!!!! ★

 

- 모범답안 - 

회문순열이 되기 위해서는 문자열길이가 짝수일때 모든 문자의 각 개수는 반드시 짝수

문자열의 길이가 홀수라면 문자 하나는 홀수개 존재해야만 함

 

해법1) 해시테이블 사용 : 각 문자가 몇 번 등장했는지 카운트 후 홀수문자가 한개 이상인지 확인

(그런데 여기서 말하는 해시테이블은 그냥 int[]이고 인덱스가 의미있기 때문에 그렇게 말한건가...?)

// 해법1. 해시테이블 사용 : 각 문자가 몇번 등장했는지 카운트 > 해시테이블 훑으며 홀수문자가 1개이상인지 확인
boolean isPermutationOfPalindrome(String pharse) {
	int[] table=buildCharFrequencyTable(pharse); // 각문자 출현횟수 저장 테이블
	return checkMaxOneodd(table); 
}
// 홀수문자가 한개 이상인지 확인 : 
boolean checkMaxOneodd(int[] table) {
	boolean foundOdd=false;
	for(int count:table) {
		if(count%2==1) {
			if(foundOdd) {
				return false; // 홀수가 1개 이상인 경우 바로 종료하며 false반환
			}
			foundOdd=true; // 홀수 발견시
		}
	}
	return true; // 홀수가 하나도 발견 안되는 경우 true반환
	
}
// 각 문자에 숫자를 대응 : a-0, b-1, c-2,...
// => 대소문자 구분 없고 문자 아닌경우 -1반환
int getCharNum(Character c) {
	int a=Character.getNumericValue('a');
	int z=Character.getNumericValue('z');
	int val=Character.getNumericValue(c);
	if(a<=val && val>=z) {
		return val-a;
	}
	return -1;
}
// 각 문자가 몇번 등장했는지 카운트
int[] buildCharFrequencyTable(String pharse) {
	int[] table=new int[Character.getNumericValue('z')-Character.getNumericValue('a')+1]; // 인덱스니까 0까지 포함시켜야하므로
	for(char c:pharse.toCharArray()) {
		int x=getCharNum(c);
		if(x!=-1) {
			table[x]++;
		}
	}
	return table;
}

 

해법2)

모든 문자열을 최소한 한번은 훑어야 하기 때문에 big-O시간을 더이상 최적화는 불가. 하지만 개선은 가능

> 마지막에 문자의 홀수 개수를 확인하는 것이 아니라, 훑어나감과 동시에 홀수 개수 확인 가능

* 이 방법을 생각하다가 총 개수가 짝수인 문자도 처음에는 countOdd가 1 늘어나니까 버렸는데,

코드를 보면 총 개수가 짝수인 문자는 처음에는 countOdd가 1늘어나도 두번째 발견시에는 -1이니까 결국 0이된다는것

즉, 짝수개 문자는 결과적으로 0을 주고 홀수개 문자는 결과적으로 1을 주게되는 것

따라서 홀수의 수가 1개라면 1, 2개라면 2, 3개라면 3... 이렇게!

// 해법2. 동시에 확인하기
boolean isPalindrome(String pharse) {
	int countOdd=0;
	int[] table=new int[Character.getNumericValue('z')-Character.getNumericValue('a')+1];
	
	for(char c:pharse.toCharArray()) {
		int x=getCharNum(c);
		if(x!=-1) {
			table[x]++;
			if (table[x]%2==1) {
				countOdd++; // 이게 홀수만 카운팅 된다는 의미가 아니라 
			} else { 
				countOdd--; // 같은 알파벳이 나오는 경우는 table숫자가 짝수라서 다시 빼줌 
			}
		}
	}
	return countOdd <=1;
}

 

해법3) 비트백터의 사용 

등장횟수를 굳이 세지않아도 짝수인지 홀수인지만 알면되는거야 마치 스위치처럼

비트값을 바꿔줄껀데, 마지막에 한개이하의 비트가 1로 세팅되어있는지 확인만 하면 OK!

(단지 1로 세팅된 비트가 없는지 확인하고싶다면 0과 같은지 비교하면 되지만~~!)

★1로 세팅된 비트가 단 한개 있는지 확인하고싶은 경우!!★

비트값에서 -1 한 뒤, AND연산 수행했을 경우 0인 경우!!!

* 1비트가 1개로 세팅된 경우만 해당! 2개이상인 경우에는 겹치는 비트가 발생하여 &"연산결과>0"임!

1) 000100000에서 1을 뺀 경우 000011111 => 겹치는 비트가 없다는 것!

2) 겹치는 비트가 없기때문에 '&'연산을 하면 0이 나온다는 것!

// 해법3. 비트백터 이용
boolean isPermutationPalindrome(String pharse) {
	int bitVector=createBiteVector(pharse);
	return bitVector == 0 || checkExactlyOnBitSet(bitVector);
}
// 문자열에 해당하는 비트백터 생성 : 값이 i라면 i번째 비트값을 변경
int createBiteVector(String pharse) {
	int bitVector=0;
	for(char c:pharse.toCharArray()) {
		int x=getCharNum(c);
		bitVector=toggle(bitVector,x);
	}
	return bitVector;
}
// 정수의 i번째 비트값을 변경 (스위치역할)
int toggle(int bitVector, int index) {
	if(index<0) return bitVector;
	int mask= 1<<index;
	if((bitVector&mask)==0) {
		bitVector|=mask;
	} else {
		bitVector&= ~mask;
	}
	return bitVector;
}
// 정확히 비트 한개만 1로 세팅되었는지 확인위해 주어진 정수값에서 1을 뺀뒤 AND연산
boolean checkExactlyOnBitSet(int bitVector) {
	return (bitVector&(bitVector-1))==0;
}

 

 

 

 [ Q5. 하나빼기 ] 

문자열을 편집하는 방법에는 세가지 종류가 있다. 문자삽입, 문자삭제, 문자교체.

문자열 두개가 주어진 경우 문자열을 같게 만들기 위한 편집회수가 1회 이내인지 확인하는 함수 작성.

예제

pale,ple -> true

pales,pale -> true

pale,bale -> true

pale,bake -> false

 

- 내답안 -

1. 문자의 길이가 같거나 1개 차이인 경우에만 편집 횟수 1이 가능

=> 문자열이 완벽 동일하면 true, 길이차이가 2이상인 경우 false

3. 길이가 같다면 한 문자만 달라야 교채가능

4. 길이가 다르다면 한문자만 빼고 같아야 추가 또는 삭제가 가능

boolean editableString(String str1, String str2) {
	if (str1.equals(str2)) return true;
	if (Math.abs(str1.length()-str2.length())>1) return false;
	
	char[] char1=str1.toCharArray();
	char[] char2=str2.toCharArray();
	int countDiff=0;
	
	// 길이가 같다면 교채방법 확인
	if(char1.length==char2.length) {
		for (int i=0;i<char1.length;i++) {
			if(char1[i]!=char2[i]) countDiff++;
			if(countDiff>1) return false;
		}
	} else { //길이가 다르다면 빼기나 더하기방법 확인
		int j=0;
		for (int i=0;i<char1.length;i++) {
			if (char1[i]==char2[j]) {
				j++;
				continue;
			} else {
				countDiff++;
				if (countDiff>1) return false;
				if (str2.length()>str1.length()) {
					i--;
					j++;
				}
			}
		}
	}
	return true;
}

"하지만 왜이렇게 복잡한것 같지?"

=> 모범답안을 보고 느낀것은 연산을 메소드로 활용하면 된다는 것!! : 해법1 처럼

=> 또는 해법2 처럼 공통 연산을 묶어서 표기하는것 참고

 

- 모범답안 -

각 연산이 무엇을 의미하는가를 파악

1. 교채 : 두 문자열에서 단 하나의 문자만 달라야 함

2. 삽입 : 한 공간만 빈공간으로 둔 경우 나머지 부분이 동일

3. 삭제 : 삽입의 반대

 

해법1) 따라서 삽입과 삭제는 하나로 합치고, 교채는 별도로 확인

=> 이때 문자열의 길이를 알고있어야 연산을 결정 가능

boolean oneEditAway(String first, String second) {
	if(first.length() == second.length()) {
		return oneEditReplace(first,second);
	} else if (first.length()+1==second.length()) {
		return oneEditInsert(first,second);
	} else if (first.length()-1==second.length()) {
		return oneEditInsert(second, first);
	}
	return false;
}

boolean oneEditReplace(String s1, String s2) {
	boolean foundDifference=false;
	for(int i=0;i<s1.length();i++) {
		if(s1.charAt(i)!=s2.charAt(i)) {
			if (foundDifference) {
				return false;
			}
			foundDifference=true;
		}
	}
	return true;
}

// s1에 문자하나를 삽입해서 s2를 만들 수 있는가 확인
boolean oneEditInsert(String s1, String s2) {
	int index1=0;
	int index2=0;
	while(index2<s2.length() && index1<s1.length()) {
		if(s1.charAt(index1)!=s2.charAt(index2)) {
			if(index1!=index2) {
				return false;
			}
			index2++;
		} else {
			index1++;
			index2++;
		}
	}
	return true;
}

 

해법2) 위 해법1의 oneEditReplace와 oneEditInsert가 비슷하기 때문에 하나로 합칠 수 있다는 것

교채(oneEditReplace)시에는 플래그값만 바꾸어주고, 삽입/삭제(oneEditInsert)시에는 짧은 문자열의 포인터만

증가시키는 것으로 하나의 메소드로 합침

// 해법2) 위 두 메소드를 하나로 합침
boolean oneEditWay(String first, String second) {
	// 길이체크
	if(Math.abs(first.length()-second.length())>1) return false;
	
	// 길이가 짧은 문자열과 긴 문자열 찾기
	String s1=first.length()<second.length()? first:second; // 짧은 문자열
	String s2=first.length()<second.length()? second:first; // 긴 문자열
	
	int index1=0;
	int index2=0;
	boolean foundDifference=false;
	while(index2<s2.length() && index1<s1.length()) {
		if(s1.charAt(index1) != s2.charAt(index2)) {
			// 반드시 첫번째로 다른 문자여야한다
			if(foundDifference) return false;
			foundDifference=true;
			// 교채의 경우 짧은 문자열의 포인터를 증가 
			if(s1.length()==s2.length()) {
				index1++;
			}
		} else {
			index1++; // 두 문자가 같은 경우 
		}
		index2++; // 언제나 긴 문자열의 포인터는 증가
	}
	return true;
}

 

 

 [ Q6. 문자열 압축 ] 

반복되는 문자의 개수를 세는 방식의 기본적인 문자열 압축 메소드를 작성하라. 예를들어 문자열 aabccccaaa를 압축하면 a2b1c5a3이 된다. 만약 압축된 문자열의 길이가 기존 문자열 길이보다 길다면 기존 문자열을 반환해야한다. 문자열은 대소문자 알파벳(a~z)으로만 이루어져있다.

 

- 내 풀이 -

두개의 포인터를 이용하여 비교하며 같은 문자를 세는 변수를 사용, sb를 이용하여 반환값생성

String compressedString(String str) {
	// 두개의 포인터 이용
	int p1=0;
	int p2=1;
	int count=1;
	// 출력문자열생성
	StringBuilder sb=new StringBuilder();
	while(p2<str.length()) {
		if(str.charAt(p1)==str.charAt(p2)) {
			count++;
		} else {
			sb.append(str.charAt(p1));
			sb.append(count);
			count=1;
			p1=p2;
		}
		p2+=1;
	}
	sb.append(str.charAt(p1));
	sb.append(count);
	
	if(sb.length()>str.length()) return str;
	return sb.toString();
}

"뭔가 쓸데없이 반복되는 코드를 적은거같은데.."

1. 일단 return부분에서 if문을 사용하기보다 [ ? : ]문을 활용하는 것이 좋을 것 같다!

2. 굳이 포인터를 이용하지 않아고 for문을 활용하여 간단하게 표현이 가능하네? > 해법1참고.

 

- 모범답안 -

해법1) 문자열을 순회 > 새로운 문자열을 복사하고 반복되는 횟수세기

> 매번 현재문자와 다음문자가 같은지 체크 후 다른경우 압축형태로 문자열에 추가

문자열 길이p, 연속되는 문자열의 개수k라고 할 때, 코드 수행시간은 O(p+k^2) 

즉 String클래스를 이용하면 문자열을 합치는데 O(n^2)의 시간이 소요 : 비효율적!

따라서 같은 방법이어도 StringBuilder클래스를 사용하면 개선 가능

String compressBad(String str) {
	String compressedString="";
	int countConsecutive=0;
	for(int i=0;i<str.length();i++) {
		countConsecutive++;
		// 다음문자와 현재문자가 같지않다면 현재문자를 결과문자열에 추가
		if(i+1>=str.length() || str.charAt(i)!=str.charAt(i+1)) {
			compressedString+=""+str.charAt(i)+countConsecutive;
			countConsecutive=0;
		}
	}
	return compressedString.length()<str.length()? compressedString:str;
}

String compress(String str) {
	StringBuilder compressedString=new StringBuilder();
	int countConsecutive=0;
	for(int i=0;i<str.length();i++) {
		countConsecutive++;
		// 다음문자와 현재문자가 같지않다면 현재문자를 결과문자열에 추가
		if(i+1>=str.length() || str.charAt(i)!=str.charAt(i+1)) {
			compressedString.append(str.charAt(i));
			compressedString.append(countConsecutive);
			countConsecutive=0;
		}
	}
	return compressedString.length()<str.length()? compressedString.toString():str;
}

 

해법2) 위 풀이처럼 압축문자열을 먼저 만들고 나중에 길이를 비교하는 방법이 아닌

먼저 문자열의 길이를 확인해 볼 수 있다면, 연속적으로 반복되는 문자가 많지않은 경우 속도 감소 가능

(즉 압축문자열을 굳이 만들 필요가 없다는 이야기)

1. 단점 : 그러려면 문자열을 2번 순회해야하고 비슷한 코드를 2번 작성해야함

2. 장점 : StringBuilder크기를 미리설정가능

// 해법3) 문자길이 미리비교하여 압축문자열 만들지말지 결정
//  => 단점은 두번순회하고 비슷한 코드를 두번작성해야한다는것
String isCompressed(String str) {
	// 압축된 문자열의 길이가 입력 문자열보다 길다면 입력문자열 반환
	int finalLength=countCompression(str); 
	if(finalLength>=str.length()) return str;
	
	StringBuilder compressed=new StringBuilder(finalLength); // 처음크기만큼의 sb생성
	int countConsecutive=0;
	for(int i=0;i<str.length();i++) {
		countConsecutive++;
		// 마지막 문자거나, 다음 문자와 현재문자가 같지않다면 현재문자를 결과 문자열에 추가
		if(i+1>=str.length()||str.charAt(i)!=str.charAt(i+1)) {
			compressed.append(str.charAt(i));
			compressed.append(countConsecutive);
			countConsecutive++;
		}
	}
	return compressed.toString();
}
// countCompression : 압축문자열을 생성하지않고 길이만 세는 메소드
int countCompression(String str) {
	int compressedLength=0;
	int countConsecutive=0;
	for(int i=0;i<str.length();i++) {
		countConsecutive++;
		// 마지막 문자거나, 다음 문자와 현재문자가 같지않다면 길이를 증가시킨다
		if(i+1>=str.length()||str.charAt(i)!=str.charAt(i+1)) {
			compressedLength+=1+String.valueOf(countConsecutive).length(); // String.valueOf(*) : String으로 변환.
			countConsecutive++;
		}
	}
	return compressedLength;
}

 

 

 

 

 [ Q7. 행렬회전 ] 

이미지를 표현하는 NxN행렬이 있다. 이미지의 각 픽셀은 4바이트로 표현된다. 이때 이미지를 90도 회전시키는 메서드를 작성하라. 행렬을 추가로 사용하디 않고서 할 수 있겠는가?

 

 

- 내 풀이 -

아예 풀지를 못했어, 왜냐하면 행렬을 어떻게 저장해서 활용하는지 감도 안왔거든,,!

우선 행렬은 int[][]의 2차원 배열로 표현하며 > 인덱스를 활용하여 문제를 푸는 것!

이때 핵심은! 

인덱스의 시작과 끝은 어디인가? 인덱스를 어떻게 나눌것인가? 반복문에서 offset같은 변수를 잘 활용해야한다?

 

- 모범답안 -

1. 위쪽 모서리 배열 복사

2. 왼쪽 모서리를 맨위로, 아래쪽 모서리를 왼쪽으로, 오른쪽 모서리를 맨아래로 이동

하지만, 이때 O(N)만큼의 메모리가 추가로 소모된다 > 따라서 인덱스로 교체작업을 진행

3. 위와같은 교채작업을 레이어 바깥쪽에서부터 안쪽으로 진행해가며 수행(역으로도 무관)

아래 알고리즘의 복잡도는 O(N^2)인데 모든 원소를 다 건드려봐야하기 때문에 최선의 방법임!

boolean rotate(int[][] matrix) {
	// 행렬의 N이 0이거나, 행의개수와 열의개수가 다른경우 종료
	if(matrix.length==0 || matrix.length!=matrix[0].length) return false;
	
	int n=matrix.length;
	// 여기서 뜻하는 레이어는 행렬의 바깥 링 한줄을 말함 그렇기 때문에 n/2번 하는것
	//  => 홀수인 경우 마지막 레이어는 하나이기 때문헤 회전이 의미없음
	//  => 레이어 개수만큼 반복
	for(int layer=0; layer<n/2; layer++) {
		int first=layer;     // 행을 뜻함
		int last=n-1-layer;  // 뒤집기 할 열의 끝 : 하나는 꼭지점으로 제외,행만큼 제외
		//여기가 레이어내용 교체 부분
		for(int i=first;i<last;i++) { // 행의반복
			int offset=i-first;  // 열의 지정
			int top=matrix[first][i]; // 윗부분을 저장
			matrix[first][i]=matrix[last-offset][first];           // 왼 > 위
			matrix[last-offset][first]=matrix[last][last-offset];  // 아 > 왼
			matrix[last][last-offset]=matrix[i][last];             // 오 > 아
			matrix[i][last]=top;                                   // 위 > 오
		}
	}
	return true;
}

 

 

 

 

 [ Q8. 0 행렬 ] 

MxN행렬의 한 원소가 0일 경우, 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘을 작성하라.

 

- 내 풀이 -

1. 행렬을 훑으면서 0을 찾기 > 인덱스 저장

2. 해당 행과 열을 0으로 변경

void changeMatrix(int[][] matrix) {
	int m=matrix.length;
	int n=matrix[0].length;
	int zeroPointI=0;
	int zeroPointJ=0;
	
	for (int i=0;i<m;i++) {
		for(int j=0;j<n;j++) {
			if (matrix[i][j]==0) {
				zeroPointI=i;
				zeroPointJ=j;
			}
		}
	}
	for(int column=0;column<n;column++) {
		matrix[zeroPointI][column]=0;
	}
	for(int row=0;row<n;row++) {
		matrix[row][zeroPointJ]=0;
	}
}

"이렇게 하면 복잡도가 O(MN)인 것 같은데.."

=> 맞아, 정확한 위치를 기록하면 그만큼의 공간이 필요하다고 해, 어짜피 바꿀꺼잖아? 0을 찾기만하면? 정확한 위치는 필요없다는 거지!

그러니까 아래 해법처럼

방법 1. 부울배열로 체크 또는 비트백터로 체크

방법 2. 첫행과 첫열을 활용하여 체크하는 방법을 사용

* 아 그리고! 나 메소드를 분리하는 연습을 좀 해야할 것 같아..!

 

- 모범답안 - 

해법1) 부울배열/비트벡터 : 내 풀이처럼 정확한 위치를 기록하게되면 O(MN)만큼의 공간이 필요

=> 하지만 어짜피 이 행어딘가에, 이 열 어딘가에 있다면 다 0을 바꿀꺼니 정확한 위치가 필요하지않음!

void setZero(int[][] matrix) {
	// 부울배열로 체크한다 > 비트백터로 체크하면 공간 효율성을 줄일수있긴하지만 복잡도는 여전히 O(N)
	boolean[] row = new boolean[matrix.length];
	boolean[] column = new boolean[matrix[0].length];
	// 값이 0인 행과 열의 인덱스를 저장 
	for(int i=0; i<matrix.length;i++) {
		for(int j=0; j<matrix[0].length;j++) {
			if(matrix[i][j]==0) {
				row[i]=true;
				column[j]=true;
			}
		}
	}
	// 행의 원소를 전부 0으로 변경
	for(int i=0;i<row.length;i++) {
		if(row[i]) nullifyRow(matrix,i);
	}
	// 열의 원소를 전부 0으로 변경
	for(int j=0;j<column.length;j++) {
		if(column[j]) nullifycolumn(matrix,j);
	}
}
void nullifyRow(int[][] matrix,int row) {
	for(int j=0;j<matrix[0].length;j++) {
		matrix[row][j]=0;
	}
}
void nullifycolumn(int[][] matrix,int column) {
	for(int i=0;i<matrix.length;i++) {
		matrix[i][column]=0;
	}
}

하지만 여전히 공간복잡도는 O(N). 

 

해법2) 첫번째행을 row배열로, 첫번째 열을 column배열로 사용하면 공간효율성을 O(1)로 낮출 수 있다.

1) 첫번째 행과 첫번째 열안에 0이 있는지 검사한 다음,

=> 있다면 rowHashZero와 columnHashZero변수를 참으로 설정

=> 나중에 첫번째 행과 첫번째 열을 0으로 만드는 작업을 수행할 것

2) 배열의 나머지 부분을 순회하며 값이 0인 matrix[i][j]를 만날때마다 matrix[i][0]와 matrix[0][j]를 0으로 설정

3) 행렬의 나머지 부분을 순회하며  matrix[i][0]이 0인 모든 행 i를 0으로 만든다. 

4) 행렬의 나머지 부분을 순회하며  matrix[0][j]이 0인 모든 열 j를 0으로 만든다. 

5) 맨 처음 설정한 값에 따라 필요한 경우 첫번째행과 첫번째 열을 0으로 만든다.

void setZeros(int[][] matrix) {
	boolean rowHashZero=false;
	boolean colHashZero=false;
	
	// 첫번째 행에 0이 있는지 확인
	for(int j=0;j<matrix[0].length;j++) {
		if(matrix[0][j]==0) {
			rowHashZero=true;
			break;
		}
	}
	// 첫번째 열에 0이 있는지 확인
	for(int i=0;i<matrix.length;i++) {
		if(matrix[i][0]==0) {
			colHashZero=true;
			break;
		}
	}
	
	// 나머지 배열에 0이 있는지 확인
	for(int i=1;i<matrix.length;i++) {
		for(int j=1;j<matrix[0].length;j++) {
			if(matrix[i][j]==0) {
				matrix[i][0]=0;
				matrix[0][j]=0;
			}
		}
	}
	
	// 첫번째 열을 이용해서 행을 0으로 바꿈
	for(int i=1;i<matrix.length;i++) {
		if(matrix[i][0]==0) {
			nullifyRow(matrix, i);
		}
	}
	// 첫번째 행을 이용해서 열을 0으로 바꿈
	for(int j=1;j<matrix[0].length;j++) {
		if(matrix[0][j]==0) {
			nullifycolumn(matrix, j);
		}
	}
	
	// 첫번째 행을 0으로 바꾼다
	if(rowHashZero) nullifyRow(matrix, 0);
	// 첫번째 열을 0으로 바꾼다
	if(colHashZero) nullifycolumn(matrix, 0);
}

 

 

 

 

 

 [ Q9. 문자열회전 ] 

한 단어가 다른 문자열에 포함되어 있는지 판별하는 isSubstring이라는 메소드가 있다고 하자. s1과 s2의 두 문자열이 주어졌고, s2가 s1을 회전시킨 결과인지 판별하고자한다(가령 'waterbottle'은 'erbottlewat'를 회전시켜서 얻을 수 있는 문자열이다). isSubstring메서드를 한번만 호출해서 판별할 수 있는 코드를 작성하라.

 

- 내답안 -

1. 메인 문자열의 첫 글자를 서브 문자열에서 찾아 리스트에 저장

2. 리스트에 저장된 체크시점마다 짤라서 원형만들기 > 같은지체크

*아 근데 또 비효율적이라 생각 듬..* 그이유 문제를 잘못이해함 메소드가 ㅇㅆ다고하자.. 이거... 이 ㅏ오ㅑ!!!

boolean isRotation(String mainString, String subString) {
	// 1. main의 첫글짜를 sub에서 찾기
	char firstLetter=mainString.charAt(0);
	ArrayList<Integer> checkPoint=new ArrayList<Integer>();
	for(int i=0;i<subString.length();i++) {
		if(subString.charAt(i)==firstLetter) {
			checkPoint.add(i);
		}
	}
	// 2. 짤라서 원형과 같은지 비교
	for(int i:checkPoint) {
		StringBuilder sb=new StringBuilder();
		sb.append(subString.substring(i));
		sb.append(subString.substring(0,i));
		if(mainString.equals(sb.toString())) return true;
	}
	return false;
}

"아.. 근데 또 비효율적인거같아.. 완벽하게.."

왜 그런 생각이 들었는지 해법을 보고 알았지. 문제를 잘 이해하지못했고 조건을 활용하지 않았기 때문이야!!

한 단어가 다른 문자열에 포함되어 있는지 판별하는 isSubstring이라는 메소드가 있다고 하자.

이 문장을 보면 저 메소드를 사용하라는 거잖아....^^!!

 

- 모범답안 - 

1. 회전지점 찾기 : 회전이란 s1을 x와y로 분리한 후 재배치 한것

2. 여기서 핵심은 회전된 yx가 아니라! 언제나 s2(yx)는 s1(xyxy)의 부분문자열이 된다는 것!

// => 회전 글자를 yx라 하면 원문자2번(xyxy)에 대해 언제나 부분문자열이라는 점!
boolean isRotationStr(String s1, String s2) {
	int len=s1.length();
	//s1과 s2의 길이가 같고 빈 문자가 아닌지 확인
	if(len==s2.length() && len>0) {
		String s1s1=s1+s1;
		return isSubstring(s1s1, s2);
	}
	return false;
}

 

 

 

 

---

 

 

1. 문제의 의미를 파악하는 연습

문제를 잘 풀기 위해서 어떤 알고리즘을 구현해야 하는가를 정리하는것이 최우선.

즉, 이 문제에서 이 단어의 의미는 무엇인가를 정확히 파악해야만 함. 예를 들면 아래와 같이 말이다.

• 회문순열 : 회문순열은 어떤뜻이지? 아 앞뒤로 읽어도 똑같은 단어+순열 처럼 바꿀수도 있어 순서! 그러면 이 회문순열을 만들기 위해서 어떻게해야하지? 반으로 접었을때 똑같아야지! 아 그렇다면, 문자열의 길이가 중요하구나, 문자열이 짝수일때는 각 문자가 모두 짝수개여야해! 만약 총길이가 홀수라면 홀수문자는 딱 하나만 있어야해! 
• 연산: 문자빼기는 어떤 조건일때 실행가능하지? 아 문자열의 길이가 딱 1개만 차이나야하고 그 차이나는 부분을 공백으로 채우면 그거때고 다 같아야하는구나!! 아? 그럼 문자더하기는 반대로 생각하면 똑같네? 

 

2. 주어진 조건을 활용했는가 체크. 이 조건이 주어진 이유가 무엇인가를 파악.

문제에 쓸데없는 문장 따위는 존재하지않는다. 마지막 문제가 그 대표적인 예.

이미 문제에 '어떠한 메소드가 있다고 가정하자~'라면 그 부분은 구현하지 않아도 되니 그 기능을 사용할 수 있도록 알고리즘을 구현해라 라는 뜻이야. 이런걸 놓치면 답은 산으로 가겠지..

 

 

3. 이건 차근차근 연습해가자.

• Big-O : 알고리즘이 효율적으로 짜여졌는지를 감으로, 또는 코드 줄로 보는게 아니라 정확히 계산하는 노력을...!
• 메소드 분리 : 하나의 메소드에 처리하기보다 분리하도록 노력해보자!