CS/자료구조 문제 30

문제 // 자료구조 // 문자열(String) // 유사문자열검증 // toJava

/** * [유사문자열] * 문자열을 편집하는 방법에는 세가지가 있습니다. * 문자 삽입 / 문자 삭제 / 문자 교체 * 문자열 2개가 주어졌을때 문자열을 같게 만들기 위한 편집 횟수가 1회 이내인지 확인하는 함수 * * [풀이] * => 케이스분류 * => 문자열 교체일 경우, 문자열의 갯수가 같아야 * => 문자열 추가일 경우, 변경할 문자열이 1개 적어야 * => 문자열 삭제일 경우, 변경할 문자열이 1개 많아야 * */ public class Q05 { public static void main(String[] args) { System.out.println(checkSimilarity("abc", "abc")); // true System.out.println(checkSimilarity("ab..

문제 // 자료구조 // 문자열(String) // 회문순열검증 // toJava

/** * [회문순열] * 주어진 문자열이 회문의 순열이지 아닌지 확인하는 함수 * 주어진 문자열이 재배치를 통해서 회문이 되는 문자열인지 아닌지 판단하는 함수 * * [풀이] * => 회문이란 ? 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은 구절을 의미 * => 순열이란 ? 문자열을 재배치하는 말함 * => * 결국 각각의 문자열이 모두 짝수개 거나 1개만이 홀수여야 함 * * [추가사항] * => 아스키코드에 한해 알파벳만 처리하도록 하겠습니다. * */ public class Q04 { public static void main(String[] args) { System.out.println(Character.getNumericValue(' ')); // -1 System.out.println(Cha..

문제 // 자료구조 // 문자열(String) // replace 만들기 // toJava

/** * [문자열변경] * 문자열에 들어 있는 모든 공백을 '%20'으로 바꿔 주는 메소드를 작성 * 최종적으로 모든 문자르 다 담을 수 있는 만큼 충분한 공간이 이미 확보되어 있으며 * 문자열의 최종길이가 함께 주어진다고 가정해도 된다. * * [풀이] * => replace를 사용하지 말것 * => StringBuilder를 사용할 수 있는가 ? * => 문자열을 앞에서 부터 순회하며 StringBuilder로 조건에 맞게 이동 * => 사용할 수 없다면 * => 미리 변경될 문자열 크기의 배열을 만들어서 삽입 * * */ public class Q03 { /* main */ public static void main(String[] args) { String helloworld = "h e l l..

문제 // 자료구조 // 문자열(String) // replace // toJava

/** * [문자열변경] * 문자열에 들어 있는 모든 공백을 '%20'으로 바꿔 주는 메소드를 작성 * 최종적으로 모든 문자르 다 담을 수 있는 만큼 충분한 공간이 이미 확보되어 있으며 * 문자열의 최종길이가 함께 주어진다고 가정해도 된다. * * [풀이] * => replace를 사용하지 말것 * => StringBuilder를 사용할 수 있는가 ? * => 문자열을 앞에서 부터 순회하며 StringBuilder로 조건에 맞게 이동 * => 사용할 수 없다면 * => 미리 변경될 문자열 크기의 배열을 만들어서 삽입 * * */ public class Q03 { /* main */ public static void main(String[] args) { String helloworld = "h e l l..

문제 // 자료구조 // 문자열(String) // 순열검증 // toJava

/** * [순열확인] * 문자열 두개가 주어졌을때 이 둘이 서로 순열 관계에 있는지 확인하는 메서드 * * [풀이] * => 순열이란, 문자열을 재조합해서 해당 문자열을 만들 수 있는가의 관계 ( god dog 순열관계 ) * => 두 문자열을 정렬해서 같다면 순열관계 * * [추가사항] * => 문자열은 모두 아스키코드인가 * => 아스키코드라면 플래그를 만들어서 채우는 방식으로 비교 * * */ public class Q02 { public static void main(String[] args) { System.out.println(checkPermutation("abc", "aaa")); System.out.println(checkPermutation("abc", "cba")); } /* che..

문제 // 자료구조 // 문자열(String) // 중복확인 // toJava

/** * [중복이없는가] * 문자열이 주어졌을때 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘 작성 * 자료구조를 사용하지 않고 풀 수 있는 알고리즘을 고민 * * [풀이] * => 문자열정렬 * => 앞뒤에같은문자가 나온다면 중복발생 * * [추가사항] * => 면접관에게 문자열이 ASCII 문자열인지 유니코드 문자열인지 물어 봐야한다. * => 여기서는 간단하게 ASCII 문자열이라고 가정하면, 128개의 플래그로 처리할 수 있음 * */ public class Q01 { /* main */ public static void main(String[] args) { System.out.println(checkDuplicationA("abcdefg")); // false System.o..

문제 // 자료구조 // 큐(Queue) // 병합큐 // toJava

/** * [동물보호소 - 병합큐 처리하기] * 먼저 들어온 동물이 먼저 나가는 동물 보호소 * 개와 고양이만 수용 * 개와 고양이중 선택 * 하지만 특정 동물을 지정해서 데려갈 수 는 없음 * enqueue dequeueAny dequeueDog dequeueCat * LinkedList 사용가능 * * [풀이] * => 개와 고양이가 객체여야 하는가 ? * => 개와 고양이의 큐를 따로 사용해도 되는가 ? * => dequeueAny는 랜덤을 말하는 건가 ? * => 개와 고양이중 먼저들어온 것을 가져오는 것 * * [주의] * => 상속으로 Animal클래스를 사용하면 좋음 * => 객체에 우선순위 ( 타임스탬프 ) 를 설정해 줄 것 */ public class Q06 { public static ..

문제 // 자료구조 // 스택(Stack) // StackSort // toJava

/** * [스택정렬] * 가장 작은 값이 위로 오도록 스택을 정렬하는 프로그램을 작성 * 추가적으로 하나 정도의 스택은 사용해도 괜찮지만 * 스택에 보관된 요소를 배열등의 다른 자료구조로 복사할 수 없다 * 스택 push pop peek isEmpty 를 제공 * * [풀이] * => get()을 제공하면 탐색이 가능 * => 지그재그식 처리 큰값이라면 넘기고 작은값이라면 다시 넘어옴 * */ public class Q05 { /* Main */ public static void main(String[] args) { Stack stack = new Stack(); stack.push(13); stack.push(12); stack.push(11); stack.push(10); stack.push(15..

문제 // 자료구조 // 스택(Stack)과 큐(Queue) // 두 스택으로 큐 만들기 // toJava

/** * [스택으로큐] * 스택 두 개로 큐 하나를 구현 * * [풀이] * => 주어지는 자료구조 스택을 사용해도 되나요 ? * => 들어오는 스택 & 나가는 스택을 따로 만든다. * => 스택이 들어오면 "Reverse"시켜서 나가는 스택에 넣어준다. * * */ public class Q04 { /* Main */ public static void main(String[] args) { MyQueue mq = new MyQueue(); mq.add(1); mq.add(2); mq.add(3); mq.print(); System.out.println(mq.remove()); // 1 mq.print(); mq.add(4); System.out.println(mq.remove()); // 2 mq.p..

문제 // 자료구조 // 스택(Stack) // SetOfStacks // toJava

/** * [접시무더기] * 접시무더기를 생각, 접시를 너무 높이 쌓으면 무너짐 * 따라서 현실에서는 접시를 쌓다가 무더기가 어느정도 높아지면 새로운 무더기를 만듬 * 이것을 흉내내는 자료구조 SetOfStacks를 구현하라 * SetOfStacks는 여러개의 스택으로 구성되어 있으며 * 이전 스택이 지정된량을 초과하는 경우 새로운 스택을 생성 * * [연관문제] * 특정 하위 스택에 대해 pop을 수행하는 popAt(int index)를 만들어라 * * [풀이] * => 접시당 크기는 ? * => 접시 무더기를 ArrayList로 구현해도 되는가 ? * => 주어진 자바의 스택으로 사용해도 되는가 ? * * */ public class Q03 { /* Main */ public static void m..