世界で戦うプログラミング力を鍛える150問

会社の同期に借りた本の問題、ぼちぼち今の俺でも解けそうなのが出てきているので、解いてこうと思う。世界で戦いたいんじゃなくて、世界で戦います(ドヤ

世界で闘うプログラミング力を鍛える150問 ~トップIT企業のプログラマになるための本~

世界で闘うプログラミング力を鍛える150問 ~トップIT企業のプログラマになるための本~

Chapter 3 スタックとキュー

  1. 1つの配列で3つのスタックをどうデザインする?
  2. push と pop に加えて min を持つスタックをどうデザインする? push, pop, min、全部O(1)の実行時間ね。
  3. Stack を複数備え、あるスタックを使いつくしたら次の Stack を利用し始めるような、SetOfStacksを実装せよ。 SetOfStacks.pop(), SetOfStacks.push()は、通常の1 Stack のデータ構造と同様に振る舞うようにせよ。 ex) 任意のStackからpopするpopAt(int index) を実装せよ
  4. ハノイの塔(バー3本)のソルバーを実装せよ
  5. MyQueue という名で、2 つのスタックを用いてキューを実装せよ
  6. スタック上のデータを小さい順に並び替えるプログラムを書け。最小がトップに来る。スタック以外のデータ構造(配列など)にスタック滋養のデータをコピーしてはいけない。スタックは、push, pop, peek, isEmpty のみを備える。

回答

  1. dualんときみたいにやれば多分できそう。
  2. 現時点での最小値を末尾に持つ、配列minを用意する。関数minは、配列minの末尾を返すだけ。O(1)。配列minの要素数をカウントするフィールド numMin も用意する。
    • 擬似コードみたいなの
      int[] min = new int[1000]  // 最小値は配列に収める;
      int numMin = 0;  // 配列minの要素数
      void push(int e) {
      // (通常のpush処理)
      if (num == 0 || min[numMin] >= e)  {
         // 等号つけとかないと何度か間を空けて
         // 同じ最小値が出てくるときの処理が厄介
         min[numMin++] = e;
      }
      }
      int pop() {
      // (通常のpop処理)
      // popした値をfとしてローカル変数で持つ
      if (min[numMin - 1] == f)  {
          numMin--;
      }
      }
      int min() {
      return min[numMin - 1];
      }
    • プロダクションコード
      package ch03;
      class StackMin {
         private int[] stack; // スタック
         private int capacity; // 最大要素数
         private int num; // スタックの要素数
         private int[] min; // 最小値を収める配列スタック
         private int minNum; // 配列minの要素数
         // 実行時例外クラス
         class OverflowMinStackException extends RuntimeException {
             public OverflowMinStackException() {
             }
         }
         class EmptyMinStackException extends RuntimeException {
             public EmptyMinStackException() {
             }
         }
         // コンスタラクタ
         StackMin() {
             capacity = 100; // 仮置き
             num = 0;
             minNum = 0;
             try {
                 stack = new int[capacity];
                 min = new int[capacity];
             } catch (OutOfMemoryError e) {
                 capacity = 0;
             }
         }
         void push(int e) throws OverflowMinStackException {
             if (num >= capacity) {
                 throw new OverflowMinStackException();
             }
             stack[num++] = e;
             if (num == 0 || min[minNum] >= e) {
                 min[minNum++] = e;
             }
         }
         int pop() throws EmptyMinStackException {
             if (num <= 0) {
                 throw new EmptyMinStackException();
             }
             int pop = stack[--num];
             if (min[minNum - 1] == pop) {
                 minNum--;
             }
             return pop;
         }
         int min() {
             if (minNum <= 0) {
                 throw new EmptyMinStackException();
             }
             return min[minNum - 1];
         }
         int size() {
             return num;
         }
         int capacity() {
             return capacity;
         }
         int peek() throws EmptyMinStackException {
             if (num <= 0) {
                  throw new EmptyMinStackException();
             }
             return stack[num - 1];
         }
      }
    • テストコード出だし
      package ch03;
      import static org.hamcrest.CoreMatchers.is;
      import static org.junit.Assert.assertThat;
      import org.junit.Before;
      import org.junit.Test;
      import org.junit.experimental.runners.Enclosed;
      import org.junit.runner.RunWith;
      import ch03.StackMin.EmptyMinStackException;
      @RunWith(Enclosed.class)
      public class StackMinTest {
         public static class 初期状態から始める場合 {
             StackMin sut;
             @Before
             public void setUp() {
                 sut = new StackMin();
             }
             @Test
             public void pushで1がスタックされること() throws Exception {
                 sut.push(1);
                 int expected = 1;
                 int actual = sut.peek();
                 assertThat(actual, is(expected));
             }
             @Test(expected = EmptyMinStackException.class)
             public void popで例外エラーが返ること() throws Exception {
                 sut.pop();
             }
             @Test(expected = EmptyMinStackException.class)
             public void minで例外エラーが返ること() throws Exception {
                 sut.min();
             }
             @Test
             public void sizeで0が返ること() throws Exception {
                 int expected = 0;
                 int actual = sut.size();
                 assertThat(actual, is(expected));
             }
             @Test
             public void capacityで100が返ること() throws Exception {
                 int expected = 100;
                 int actual = sut.capacity();
                 assertThat(actual, is(expected));
             }
             @Test(expected = EmptyMinStackException.class)
             public void peekで例外エラーが返ること() throws Exception {
                 sut.peek();
             }
         }
      }
  3. (2013/02/10追記)とりあえず書いた。途中。
            package ch03;
            
            class MultiStack {
                int stackCapacity = 0;
                int stackPtr;
                SingleStack[] singleStackArray;
                class EmptyStackException extends RuntimeException {
                    EmptyStackException() {
                    }
                }
                class OverflowStackException extends RuntimeException {
                    OverflowStackException() {
                    }
                }   
                MultiStack(int stackCapacity) {
                    this.stackCapacity = stackCapacity;
                    try {
                        singleStackArray = new SingleStack[stackCapacity];
                    } catch (OutOfMemoryError e) {
                        stackCapacity = 0;
                        stackPtr = 0;
                    }
                }
                void push(SingleStack s) throws OverflowStackException {
                    if (stackPtr >= stackCapacity) {
                        throw new OverflowStackException();
                    }
                    singleStackArray[stackPtr++] = s;
                }
                class SingleStack {
                    int capacity;
                    int[] stack;
                    int ptr = 0;
                    SingleStack(int elementCapacity) {
                        this.capacity = elementCapacity;
                        try {
                            stack = new int[elementCapacity];
                        } catch (OutOfMemoryError e) {
                            elementCapacity = 0;
                            ptr = 0;
                        }
                    }
                    void push(int e) throws OverflowStackException {
                        if (ptr >= capacity) {
                            throw new OverflowStackException();
                        }
                        stack[ptr++] = e;
                    }
                    int pop() throws EmptyStackException {
                        if (ptr <= 0) {
                            throw new EmptyStackException();
                        }
                        return stack[--ptr];
                    }
                    int peek() throws EmptyStackException {
                        if (ptr <= 0) {
                            throw new EmptyStackException();
                        }
                        return stack[ptr - 1];
                    }
                }
            }
  1. まだ。再帰使うととりあえずは書ける。
    (1,2,3) = (1~N, 0, 0) → (N, 1~N-1, 0) → (0, 1~N-1, N) → (0, 0, 1~N)
    の流れ。
    (2013/02/06追記)
    とりあえず書き下した。
    package ch03;
     import java.util.Scanner;
     class Hanoi {
         static void move(int no, int from, int to) {
             if (no > 1) {
                 move(no - 1, from, 6 - from - to);
             }
             System.out.println(no + "枚目を、" + from + "軸から" + to + "軸に移動");
             if (no > 1) {
                 move(no - 1, 6 - from - to, to);
             }
         }
         public static void main(String[] args) {
             Scanner stdIn = new Scanner(System.in);
             System.out.print("枚数?: ");
             int no = stdIn.nextInt();
             int from = 1;
             int to = 3;
             move(no, from, to);
         }
     }
  2. まだ
  3. まだ

評価

  1. まだ
  2. まだ
  3. minを保持するデータ構造として、配列よりスタックのほうが良かったね。元から具備してる機能あるし。あと、初手からmin()叩くケースのエラー考慮漏れ。Integer.MAX_VALUE とか返してあげよう。
    • 解1: pushする値と、その時点での最小値をフィールドに持つクラスを作成。そいつスタックする。スタックがかさんでくると、メモリ食いつぶしが二倍なのがいただけない。
    • 解2: 最小値を押し込んでいくスタックを用意する。peekして最小値確認する感じ。自分の解法とほぼ同じ。スタックという構造を使うか、配列にマーカー付与するかの違い。
  4. 帰納的に一手一手書き出しながら一般の挙動をイメージして、実装した。一発ではないのでまだ染みこみ足りない。が、イメージを書き起こせるようにはなっているので、あと一歩。
  5. まだ
  6. まだ

総評

  • 望洋さんの『Javaによるアルゴリズムとデータ構造』で触れたような話が多い。データ構造の基礎。一度理解したら、あとは空でサクサク書けるようになる事が必要だろう。各データ構造のアウトプット数回して、もうちょっと染みこませることが今必要。

明解 Javaによるアルゴリズムとデータ構造

明解 Javaによるアルゴリズムとデータ構造

 

付随して出た疑問・メモ

  • JUnit のテストランナーで構造化 @Enclosed 指定した場合、テストクラスの内部クラスは static にしないと、テストケースとして拾われない。なんで?
  • preタグ内でコード表示したいとき、インデントは一段深くしてやらんと正常に表示されないので以降注意。置換^\t -> \t\t 的な。