2019. 9. 5. 23:25ㆍ면접코딩
package cb.datagujo.one;
/*
* 중복은 없는가: 문자열이 주어졌을때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라.
* 자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘 또한 고민하라.
*/
public class Code1_1_p281 {
public static void main(String[] args) {
Code1_1_p281 jc = new Code1_1_p281();
String inputStr = "ABCDEFGijkmngg";
if (!jc.isUniqueChars(inputStr)) {
System.out.println("중복글자가 있다!!!");
} else {
System.out.println("중복글자가 없다!!!");
}
String inputStr2 = "adbb";
if (!jc.isUniqueChars_az(inputStr2)) {
System.out.println("비트연산체크_중복글자가 있다!!!");
} else {
System.out.println("비트연산체크_중복글자가 없다!!!");
}
}
boolean isUniqueChars(String str) {
if (str.length() > 128) return false;
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;
}
char_set[val] = true;
}
return true;
}
boolean isUniqueChars_az(String str) {
int checker = 0;
for (int i = 0; i < str.length(); i++ ) {
//알파벳 소문자 0~25값으로 표현
int val = str.charAt(i) - 'a';
if ( (checker & ( 1 << val)) > 0) {
return false;
}
checker |= (1 << val);
}
return true;
}
}
package cb.datagujo.one;
/*
* 순열 확인: 문자열 두개가 주어졌을때 이 둘이 서로 순열 관계에 있는지 확인하는 메서드를 작성하라.
*/
public class Code1_2_p282 {
public static void main(String[] args) {
Code1_2_p282 wis = new Code1_2_p282();
wis.permulation("aZ12DDE", "DD12EZa");
if (wis.permutationArr("aZ12DDE", "DDD12EZ")) {
System.out.println("동일순열");
} else {
System.out.println("다른순열");
}
}
public String sort(String s) {
char[] content = s.toCharArray();
java.util.Arrays.sort(content);
return new String(content);
}
// permulation : 순열
public boolean permulation(String s, String t) {
if (s.length() != t.length()) {
return false;
}
return sort(s).equals(sort(t));
}
boolean permutationArr(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] letters = new int[128]; // 가정
char[] s_array = s.toCharArray();
for (char c : s_array) { // s 내에서 각 문자의 출현횟수를 센다.
letters[c]++;
}
for (int i = 0; i < t.length(); i++) {
int c = (int) t.charAt(i);
letters[c]--;
if (letters[c] < 0) {
return false;
}
}
return true;
}
}
package cb.datagujo.one;
/*
* URLify: 문자열에 들어 있는 모든 공백을 '%20'으로 바꾸는 메서드를 작성하라.
* 최종적으로 모든 문자를 다 담을 수 있을 만큼 충분한 공간이 이미 확보되어 있으며
* 문자열의 최종길이가 함께 주어진다고 가정해도 된다.
* (자바로 구현한다면 배열 안에서 작업할 수 있도록 문자 배열(character array)을 이용하라.)
*/
public class Code1_3_p284 {
public static void main(String[] args) {
Code1_3_p284 bv = new Code1_3_p284();
System.out.println(bv.replaceSpaces("Mr John Smith".toCharArray(), 13));
}
String replaceSpaces(char[] str, int trueLength) {
int spaceCount = 0, index, i = 0;
for (i = 0; i < trueLength; i++) {
if (str[i] == ' ') {
spaceCount++;
}
}
index = trueLength + spaceCount * 2;
char[] resultStr = new char[index];
if (trueLength < str.length) str[trueLength] = '\0'; // 배열의 끝
for (i = trueLength - 1; i >= 0; i--) {
if (str[i] == ' ') {
resultStr[index - 1] = '0';
resultStr[index - 2] = '2';
resultStr[index - 3] = '%';
index = index - 3;
} else {
resultStr[index - 1] = str[i];
index--;
}
}
//System.out.println(resultStr);
return String.valueOf(resultStr);
}
}
package cb.datagujo.one;
/*
* 회문 순열: 주어진 문자열이 회문(palindrome)의 순열인지 아닌지 확인하는 함수를 작성하라.
* 회문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은 구절을 의미하며,
* 순열이란 문자열을 재배치하는 것을 뜻한다. 회문이 꼭 사전에 등장하는 단어로 제한될 필요는 없다.
* 예제) 입력: tact coa
* 결과: True(순열:"taco cat", "atcocta"등등)
*/
public class Code1_4_p285 {
public static void main(String[] args) {
Code1_4_p285 p = new Code1_4_p285();
if (p.isPermutationOfPalindrome("taco cat")) {
System.out.println("회문순열이다.");
} else {
System.out.println("회문순열이 아니다.");
}
if (p.isPermutationOfPalindrome2("atco cta")) {
System.out.println("회문순열이다.2");
} else {
System.out.println("회문순열이 아니다.2");
}
if (p.isPermutationOfPalindromeBit("atco cta")) {
System.out.println("회문순열이다.3");
} else {
System.out.println("회문순열이 아니다.3");
}
}
boolean isPermutationOfPalindrome(String phrase) {
int[] table = buildCharFrequencyTable(phrase);
return checkMaxOneOdd(table);
}
boolean isPermutationOfPalindrome2(String phrase) {
int countOdd = 0;
int[] table = new int[Character.getNumericValue('z') - Character.getNumericValue('a') + 1]; // 26개
for (char c : phrase.toCharArray()) {
int x = getCharNumber(c);
if (x != -1) {
table[x]++;
if (table[x] % 2 == 1) {
countOdd++;
} else {
countOdd--;
}
}
}
return countOdd <= 1;
}
/* 홀수 문자가 한 개 이상 존재하는지 확인한다. */
boolean checkMaxOneOdd(int[] table) {
boolean foundOdd = false;
for (int count : table) {
if (count % 2 == 1) {
if (foundOdd) {
return false;
}
foundOdd = true;
}
}
return true;
}
/* 각 문자에 숫자를 대응시킨다. a -> 0, b -> 1, c -> 2 등등.
* 대소문자 구분이 없고, 문자가 아닌 경우에는 -1로 대응시킨다. */
int getCharNumber(Character c) {
int a = Character.getNumericValue('a'); // a 10
int z = Character.getNumericValue('z'); // z 35
int val = Character.getNumericValue(c); // 빈칸 -1
if (a <= val && val <= z) {
return val - a;
}
return -1;
}
/* 각 문자가 몇 번 등장했는지 센다. */
int[] buildCharFrequencyTable(String phrase) {
int[] table = new int[Character.getNumericValue('z') - Character.getNumericValue('a') + 1]; // 26개
for (char c : phrase.toCharArray()) {
int x = getCharNumber(c);
if (x != -1) {
table[x]++;
}
}
return table;
}
boolean isPermutationOfPalindromeBit(String phrase) {
int bitVector = createBitVector(phrase);
return bitVector == 0 || checkExactlyOneBitSet(bitVector);
}
/* 문자열에 대한 비트 백터를 만든다. 값이 1인 문자가 등장하면 i번째 비트값을 바꾼다. */
int createBitVector(String phrase) {
int bitVector = 0;
for (char c : phrase.toCharArray()) {
int x = getCharNumber(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 checkExactlyOneBitSet(int bitVector) {
return (bitVector & (bitVector -1)) == 0;
}
}
package cb.datagujo.one;
/*
* 하나 빼기: 문자열을 편집하는 방법에는 세가지 종류가 있다.
* 문자 삽입, 문자 삭제, 문자 교체.
* 문자열 두 개가 주어졌을때, 문자열을 같게 만들기 위한
* 편집횟수가 1회 이내인지 확인하는 함수를 작성하라.
* 예제) pale, ple -> true
* pales, pale -> true
* pale, bale -> true
* pale, bake -> false
*/
public class Code1_5_p289 {
public static void main(String[] args) {
Code1_5_p289 cs = new Code1_5_p289();
cs.oneEditAway("pale", "pele");
}
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개 메소드를 합친 것 */
boolean oneEditAwayAllinOne(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;
}
}
package cb.datagujo.one;
/*
* 문자열 압축: 반복되는 문자의 개수를 세는 방식의 기본적인 문자열 압축 메서드를 작성하라.
* 예를 들어 문자열 aabccccaaa를 압축하면 a2bc4a3이 된다.
* 만약 '압축된' 문자열의 길이가 기존 문자열의 길이보다 길다면 기존 문자열을 반환해야 한다.
* 문자열은 대소문자 알파벳(a~z)으로만 이루어져 있다.
*/
public class Code1_6_p292 {
public static void main(String[] args) {
Code1_6_p292 p292 = new Code1_6_p292();
System.out.println(p292.compressBad("aaabbbccddddaa"));
System.out.println(p292.compress("aaabbbccddddaa"));
System.out.println(p292.compress2("aaabbbccddddaa"));
}
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 compressed = 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)) {
compressed.append(str.charAt(i));
compressed.append(countConsecutive);
countConsecutive = 0;
}
}
return compressed.length() < str.length() ? compressed.toString() : str;
}
String compress2(String str) {
/* 압축된 문자열의 길이가 입력 문자열보다 길다면 입력 문자열을 반환한다. */
int finalLength = countCompression(str);
if (finalLength >= str.length()) return str;
StringBuilder compressed = new StringBuilder(finalLength); // 처음 크기
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 = 0;
}
}
return compressed.toString();
}
int countCompression(String str) {
int compressionLength = 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)) {
compressionLength += 1 + String.valueOf(countConsecutive).length();
countConsecutive = 0;
}
}
return compressionLength;
}
}
package cb.datagujo.one;
/*
* 행렬회전: 이미지를 표현하는 MxN 행렬이 있다.
* 이미지의 각 픽셀은 4바이트로 표현된다.
* 이때, 이미지를 90도 회전시키는 메소드를 작성하라.
* 행렬을 추가로 사용하지 않고서도 할 수 있겠는가?
*/
public class Code1_7_p294 {
public static void main(String[] args) {
Code1_7_p294 p294 = new Code1_7_p294();
int[][] m = new int[][] {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
//int[][] m = new int[][] {{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25}};
if (p294.rotate(m)) {
System.out.println("90도 회전");
};
for (int i=0; i < 4; i++) {
//System.out.println(m[i][0]+","+m[i][1]+","+m[i][2]+","+m[i][3]+","+m[i][4]);
System.out.println(m[i][0]+","+m[i][1]+","+m[i][2]+","+m[i][3]);
}
}
boolean rotate(int[][] matrix) {
if (matrix.length == 0 || matrix.length != matrix[0].length) return false;
int n = matrix.length;
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; // 오른쪽 <- 미리 저장해 놓은 top
}
}
return true;
}
}
package cb.datagujo.one;
/*
* 0행렬: MxN 행렬의 한 원소가 0일 경우,
* 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘을 작성하라.
*/
public class Code1_8_p295 {
public static void main(String[] args) {
Code1_8_p295 p295 = new Code1_8_p295();
int[][] m = new int[][] {{1,0,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25}};
//p295.setZeros(m);
p295.setZeros2(m);
for (int i=0; i < 5; i++) {
System.out.println(m[i][0]+","+m[i][1]+","+m[i][2]+","+m[i][3]+","+m[i][4]);
}
}
void setZeros(int[][] matrix) {
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 < row.length; j++) {
if (row[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 col) {
for (int i = 0; i < matrix[0].length; i++) {
matrix[i][col] = 0;
}
}
void setZeros2(int[][] matrix) {
boolean rowHasZero = false;
boolean colHasZero = false;
// 첫번째 행에 0이 있는지 확인
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[0][j] == 0) {
rowHasZero = true;
break;
}
}
// 첫번째 열에 0이 있는지 확인
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][0] == 0) {
colHasZero = 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 (rowHasZero) {
nullifyRow(matrix, 0);
}
// 첫번째 열을 0으로 바꾼다.
if (colHasZero) {
nullifyColumn(matrix, 0);
}
}
}
package cb.datagujo.one;
/*
* 문자열회전: 한단어가 다른 문자열에 포함되어 있는지 판별하는 isSubstring이라는 메소드가 있다고 하자.
* s2가 s1을 회전시킨 결과인지 판별하고자 한다. (가령 'waterbottle'은 erbottlewat'을 회전시켜 얻을수 있는 문자열이다.)
* isSubstring 메서드를 한번만 호출해서 판별할 수 잇는 코드를 작성하라.
*/
public class Code1_9_p298 {
public static void main(String[] args) {
Code1_9_p298 p298 = new Code1_9_p298();
String s1 = "waterbottle";
String s2 = "lewaterbott";
if (p298.isRotation(s1, s2)) {
System.out.println("포함되어 있다.");
} else {
System.out.println("포함되어 있지 않다.");
}
}
boolean isRotation(String s1, String s2) {
int len = s1.length();
/* s1과 s2의 길이가 같고 빈(empty) 문자열이 아닌지 확인한다. */
if (len == s2.length() && len > 0) {
/* s1과 s1을 합친 결과를 새로운 버퍼에 저장한다. */
String s1s1 = s1 + s1;
return isSubstring(s1s1, s2);
}
return false;
}
boolean isSubstring(String s3, String s4) {
int len = s4.length();
for (int i = 0; i < s3.length(); i++) {
if (i + len <= s3.length()) {
if (s3.substring(i, i + len).equals(s4)) {
return true;
}
}
}
return false;
}
}