3794

http://www.aladin.co.kr/shop/wproduct.aspx?ItemId=553103

페인트공 알고리즘

도로 차선 페인트 작업을 하는 러시아 페인트공이 있었습니다. 작업 첫날 페인트공은 페인트 통을 들고 나가서 300야드를 칠했습니다. 깜짝 놀란 책임자는 "정말 놀라운데! 정말 손놀림이 좋군." 이라며, 페인트공에게 1코벡을 주었습니다.

다음날 페인트공은 겨우 150야드만 칠했습니다. 그래도 책임자는 "음, 어제 만큼은 못하지만, 여전히 손놀림이 좋아. 150야드도 대단하지." 라며, 1코펙을 주었습니다.

다음날 페인트공은 30야드를 칠했습니다. 책임자는 "고작 30야드라니! 용납할 수 없네! 첫날에는 어떻게 오늘보다 10배를 넘게 칠한건가? 도대체 뭐가 문제야?" 라고 윽박질렀습니다.

풀이 죽은 페인트공은 이렇게 말했습니다. "저도 어쩔 수 없었습니다. 매일 페인트 통에서 점점 멀어지니까요."

1. comparable과 comparator

Java 에서 object를 정렬 하기 위해서는 comparable interface 가 기본적으로 필요하다. 

@Test
public void sortObjects() {
    final String[] strings = {"z", "yy", "abc"};
    final String[] expected = {"abc", "yy", "z"};
	
    Arrays.sort(strings);
    assertArrayEquals(expected, strings);
}

String class는 comparable 인터페이스가 implements된 class 이므로 순서대로 정렬된다. 

comparable이 implements되지 않은 object를 sorting 하려고 하면 컴파일러가 comparable interface가 구현되어 있을거라고 예상하기 때문에 exception이 발생한다.

class Obj {
    private int orderNo;
	
    public Obj(int i) {
        this.orderNo = i;
    }

    public int getOrderNo() {
        return this.orderNo;
    }
}

@Test
public void sortNotComparable() {
    final List<Obj> objects = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        objects.add(new obj(i));	
    }
    // java.lang.ClassCastException: Sorting$Obj cannot be cast to java.lang.Comparable
    Arrays.sort(objects.toArray());
}

class Obj implements Comparable<Obj>{
    private int orderNo;
    ...
    @Override
    public int compareTo(Obj o) {
        return this.orderNo - o.orderNo;
    }
}

하지만 클래스 외부에서 compare 방법을 변경할 수 없기 때문에 보통 comparable을 설명 할때 natural order sorting(예를 들어 id순서나 날짜 순서 같은 자연스러운 sorting)을 구현할때 사용하라고 하는 경우를 볼 수 있다. 우리가 알고 있는 디자인 패턴에 맞는 방법은, 다양한 sorting방법을 변경하면서 사용하는 것인데, 그래서 comparator 가 필요하다.

class CustumOrder implements Comparator {
    @Override
    public int compare(Obj o1, Obj o2) {
        return o2.getOrderNo() - o1.getOrderNo();
    }	
}

class Obj {
    private int orderNo;
	
    public Obj(int i) {
        this.orderNo = i;
    }

    public int getOrderNo() {
        return this.orderNo;
    }

    @Override
    public boolean equals(Object other) {
        Obj self = (Obj) other;
        return this.orderNo == self.getOrderNo();
    }
}

class CustumOrder implements Comparator {
    @Override
    public int compare(Obj o1, Obj o2) {
        return o2.getOrderNo() - o1.getOrderNo();
    }	
}

@Test
public void sortNotComparable() {
    final List<Obj> objects = new ArrayList<>();
    for (int i = 0; i < 5; i++) {
        objects.add(new Obj(i));
    }

    final List<Obj> reversedExpectedObjects = Arrays.asList(new Obj(4), new Obj(3), new Obj(2), new Obj(1), new Obj(0));
    final List<Obj> expectedObjects = Arrays.asList(new Obj(0), new Obj(1), new Obj(2), new Obj(3), new Obj(4));
	
    // 내림차순
    Collections.sort(objects, new CustumOrder());
    assertEquals(reversedExpectedObjects, objects);
	
    // 오름차순
    // Comparator가 functional interface이기 때문에 lambda expression을 사용할 수 있다.
    Collections.sort(objects, new Comparator<Obj>() {
        @Override
        public int compare(Obj o1, Obj o2) {
            return o1.getOrderNo() - o2.getOrderNo();
        }
    });
    assertEquals(expectedObjects, objects);
}

2. TreeMap

자바에서 기본 자료구조로 TreeMap을 제공한다. HashMap과 달리 이진트리 자료구조이기 때문에 key를 가지고 comparable과 comparator interface를 사용해서 sorting한다. (그렇기 때문에 hashCode 메소드는 사용하지 않는다.)

@Test
public void treeMapTraversal() {
    final Map<Integer, String> counts = new TreeMap<>();
    counts.put(4, "four");
    counts.put(1, "one");
    counts.put(3, "three");
    counts.put(2, "two");
	
    final Iterator<Integer> keys = counts.keySet().iterator();
    assertEquals("one", counts.get(keys.next()));
    assertEquals("two", counts.get(keys.next()));
    assertEquals("three", counts.get(keys.next()));
    assertEquals("four", counts.get(keys.next()));
}

@Test
public void treeMapTraversalWithComparator() {
    final Map<Integer, String> counts = new TreeMap<>(new Comparator() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });
    counts.put(4, "four");
    counts.put(1, "one");
    counts.put(3, "three");
    counts.put(2, "two");
	
    final Iterator<Integer> keys = counts.keySet().iterator();
    assertEquals("four", counts.get(keys.next()));
    assertEquals("three", counts.get(keys.next()));
    assertEquals("two", counts.get(keys.next()));
    assertEquals("one", counts.get(keys.next()));
}

http://codingdojang.com/scode/539?answer_mode=hide

var assert = require('assert')
/**
 * 자기 자신을 제외한 모든 양의 약수들의 합이 자기 자신이 되는 자연수를 완전수라고 한다. 
 * 예를 들면, 6과 28은 완전수이다. 6 = 1 + 2 + 3 // 1, 2, 3은 6의 약수
 * 28 = 1 + 2 + 4 + 7 + 14 // 1, 2, 4, 7, 14는 각각 28의 약수
 *
 * 입력으로 자연수 N을 받고, 출력으로 N이하의 모든 완전수를 출력하는 코드를 작성하라.
 */

function divisorWithoutSelf(n) {
  var divisors = []
  for (var i = 1; i < n; i++) {
    if (n % i === 0) {
      divisors.push(i)
    } 
  }
  return divisors
}

function sumOfList(list) {
  return list.reduce((a, b) => (a + b), 0)
}

function isPerfectNumber(n) {
  return n === sumOfList(divisorWithoutSelf(n))
}

function perfectNumbers(n) {
  var numbers = []

  for (var i = 2; i <= n; i++) {
    if (isPerfectNumber(i)) {
      numbers.push(i)
    }
  }
  return numbers
}

describe('get perfect numbers', () => {
  it('divisors without self', () => {
    assert.deepEqual(divisorWithoutSelf(6), [1, 2, 3])
  })
  it('sum of list', () => {
    assert.equal(sumOfList([1, 2, 3]), 6)
  })
  it('is perfect number', () => {
    assert.equal(isPerfectNumber(6), true)
  })
  it('perfect numbers', () => {
    assert.deepEqual(perfectNumbers(500), [6, 28, 496])
  })
})