B. n개의 원소를 가지는 1차원 벡터를 i만큼 왼쪽으로 회전시켜라. 예를 들어 n=8, i=3 일 경우 abcdefgh 라는 벡터를 회전시키면 defghabc 가 된다. 간단한 코드로는 n개의 원소를 가지는 임시 벡터를 사용하여 n번의 단계를 통해 해결할 수 있다. 여분의 메모리가 수십 바이트 밖에 안되는 상황에서도 n에 비례하는 시간 내에 벡터를 회전시킬 수 있겠는가?
B는 n개의 원소를 가지는 벡터 x를 i만큼 왼쪽으로 회전 시키는 문제이다. 메모리의 한계를 생각할 때 가능한 방법으로 ①저글링 조작(juggling action)을 사용한 회전과 ②반전을 이용한 회전이 소개되어 있으며 이는 연습문제3 에서 코드로 구현한다
연습문제3 (1) - 저글링 조작(단계별 순차 이동)
/* 생각하는 프로그래밍 칼럼2 B문제1
시작일 : 2009-07-30
완료일 : 2009-07-30
1. 저글링 알고리즘을 이용하여 B문제 풀이
2. vector 는 문자 배열이라고 생각한다
3. 우선 총 8자리에서 3자리 옮기기를 구현한다(n=8, i=3)
4. 사용자 입력 부분은 구현하지 않았다
*/
public class JugglingShift {
public static void main(String[] args) {
String[] vector = {"a","b","c","d","e","f","g","h"};
int i = 3;
int blockCount = (int)Math.ceil((double)vector.length / i); // 블럭 단위 갯수 구하기
String[] block = new String[blockCount]; // 저장할 공간
String temp; // 임시 저장 공간
// 8개 원소를 3블럭으로 분배
for ( int j=0 ; j<block.length ; j++ ) {
for ( int l=0 ; l<vector.length ; l++ ) {
if ( (j*i+l%i) == l ) {
if ( l%i == 0 ) {
block[j] = new String(vector[l]);
} else {
block[j] += vector[l];
}
}
}
}
System.out.println( block[0]+" "+block[1]+" "+block[2] );
// 블럭 저글링
temp = block[0]; // 이동할 블럭을 temp 로
block[0] = block[1]; // 하나씩 당겨 넣는다
block[1] = block[2];
block[2] = temp; // 마지막에 빈 곳에 temp 를
System.out.println( block[0]+" "+block[1]+" "+block[2] );
}
}
|
연습문제3 (2) - 반전을 이용한 회전
반전 코드를 이용한 회전은 책에도 나와 있지만 '배열의 특정 부분의 원소들을 반전시키는 함수' 가 존재 할 때 가능하다. Java 는 StringBuffer 에 reverse() 메서드를 제공하지만, 간단하게 배열을 역으로 대입하는 방식으로 구현하였다. 물론 배열의 부분 반전도 구현하였다
/* 생각하는 프로그래밍 칼럼2 B문제2
시작일 : 2009-08-02
완료일 : 2009-08-03
1. 반전을 이용한 B문제 풀이
2. vector 는 문자라고 생각한다
3. 우선 총 8자리에서 3자리 옮기기를 구현한다(n=8, i=3)
4. 사용자 입력 부분은 구현하지 않는다
5. reverse() 메서드를 구현한다
*/
public class ReverseShift {
public static void main(String[] args) {
String vector = "abcdefgh";
int i = 3;
System.out.println(vector);
vector = reverse(vector, 0, i-1); // 처음부터 i까지 반전시킨다
System.out.println(vector);
vector = reverse(vector, i, vector.length()-1); // i부터 끝까지 반전시킨다
System.out.println(vector);
vector = reverse(vector, 0, vector.length()-1); // 전체를 반전 시킨다
System.out.println(vector);
}
// vector 문자열을 i 만큼 회전
public static String reverse(String vector, int start, int end) {
String ReverseVector = new String();
ReverseVector += vector.substring(0,start); // 반전하지 않는 앞부분 붙이기
// StringBuffer의 reverse() 를 이용해도 되지만
// 단순하게 배열을 역으로 넣어서 구현하였다
for ( int i=end ; i>=start ; i-- ) {
ReverseVector += String.valueOf(vector.charAt(i));
}
ReverseVector += vector.substring(end+1,vector.length()); // 반전하지 않는 뒷부분 붙이기
return ReverseVector;
}
}
|
