Ehwaz's DevLog

[ehwaz-t]

코딩 문제 템플릿 업데이트

저번에 블로그에 올린 코딩 문제 템플릿을 사용하다 세 가지 수정한 점을 정리해본다.

1. 문제 풀이 메소드의 입력 클래스로 Scanner 대신 InputStream 사용

Sorting 알고리즘을 테스트하는 과정에서 한 줄이 1000000개의 int값으로 이뤄진 테스트 케이스를 읽어오게 되었다. 역시나 익히 알려진 대로 Scanner 클래스의 nextInt()로는 역부족이었고[1], 몇 십초를 넘게 기다려도 입력 처리가 끝나지 않아 BufferedReader + StringTokenizer를 사용해야 했다. 따라서 입력 방식으로 Scanner와 BufferedReader를 필요에 따라 쓸 수 있도록 문제 풀이 메소드가 Scanner 대신 InputStream을 입력받도록 수정했다. 애당초 abstraction 관점에서도 InputStream을 받는 것이 더 적합하기도 했고.

2. 여러 개의 테스트 케이스를 하나의 클래스에서 실행하기

예전 버전의 템플릿은 각 테스트 클래스당 하나의 테스트 케이스를 실행하도록 구성되어 있었다. 그러다보니 입출력 파일 여러 쌍 각각에 대해서 테스트 케이스를 구성하려면 파일을 복붙하고 클래스명과 입출력 파일명만 바꾸는 작업을 반복적으로 해야 했다. 이게 지루하기도 하거니와, 각 테스트 케이스들을 비교하면 중복되는 코드가 대부분이라 미관을 해친다.

공통되는 부분을 정리한 방법 설명은 아래 예제 코드로 갈음한다. 지금 이 방법의 한계는, 각 @Test 메소드들마다 System.out을 각자 생성한 ByteArrayOutputStream 객체로 set하기 때문에, 반드시 순차적으로 실행되어야 한다는 점이다. 만약 각 @Test 메소드들을 parallel하게 실행한다면 테스트가 제대로 실행되지 않을 것이다.

3. 테스트 추가시 수정해야 하는 코드 영역 한정시키기

테스트를 추가하기 위해 복붙 후 수정해야 하는 값들이 여기저기 있어 혼동의 여지가 있으므로 한데 모아 정리했다. 이 과정에서 테스트할 문제 풀이 메소드를 함수 객체로 assign하기 위해 Java 8에서 추가된 java.util.Function.Consumer 인터페이스를 사용했다. Consumer 인터페이스는 반환 값이 없이 입력 객체만을 받는 함수의 타입으로 사용할 수 있다. [2, 3] (아래 SolutionTest 클래스의 SOLUTION_TO_TEST 객체 참고)

아래 코드는 수정된 템플릿의 문제 풀이 클래스와 테스트 클래스다. 전체 코드는 Github 저장소에서 확인할 수 있다.

public class Solution { public static void solveProb(InputStream istream) { Scanner sc = new Scanner(istream); ... // Scanner로부터 입력을 받아 stdout으로 결과 출력 } public static void main(String[] args) { solveProb(System.in); } }

public class SolutionTest { ///////////// Test-specific codes: you only need to modify these lines. ///////////////// // Requires Java 8 Consumer<InputStream> SOLUTION_TO_TEST = istream -> Solution.solveProb(istream); private final int numOfTestCases = 2; private final String[] INPUT_FILE_PATHS = { "src/ehwaz/problem_solving/template/input1.txt", "src/ehwaz/problem_solving/template/input2.txt" }; private final String[] OUTPUT_FILE_PATHS = { "src/ehwaz/problem_solving/template/output1.txt", "src/ehwaz/problem_solving/template/output2.txt" }; @Test private void runTestCase1() throws Exception { runTest(0, SOLUTION_TO_TEST); } @Test private void runTestCase2() throws Exception { runTest(1, SOLUTION_TO_TEST); } ///////////////////////////////////////////////////////////////////////////////////////// private FileInputStream istream; private ByteArrayOutputStream outContent; private Path outputFilePath; PrintStream original = System.out; public void runTest(int testIdx, Consumer solutionToTest) throws Exception { // Input file로부터 테스트 input 준비 istream = new FileInputStream(INPUT_FILE_PATHS[testIdx]); // 테스트 output을 ByteArrayOutputStream으로 받도록 준비 outContent = new ByteArrayOutputStream(); System.setOut(new PrintStream(outContent)); solutionToTest.accept(istream); // Consumer.accept(...) 호출로 문제 풀이 메소드 실행 String result = outContent.toString().trim(); // Output answer 읽기 outputFilePath = Paths.get(OUTPUT_FILE_PATHS[testIdx]); String answer = new String(Files.readAllBytes(outputFilePath)).trim(); // Test 통과 여부 판별 Assert.assertEquals(result, answer, "Test case #" + (testIdx+1) + " is failed."); istream.close(); outContent.close(); System.setOut(original); } }

BufferedReader(+StringTokenizer)가 Scanner보다 빠른 이유로는 클래스 내부 buffer의 크기가 BufferedReader(8192 chars)가 Scanner(1024 chars)보다 더 크다는 점이 주로 거론된다. [링크] Scanner는 BufferedReader에 비해 regex 매칭으로 문자열을 읽어서 변환하는 과정이 추가로 수행되긴 하지만, 대부분의 성능 비교에서는 BufferedReader와 StringTokenizer를 함께 사용하므로 두 경우 다 수행되는 과정은 같은 셈이다. Scanner의 내부 구현을 살펴보지 않는 이상 Scanner에서 regex와 value parsing이 수행되는 것이 속도 저하의 원인이라고 단언할 수는 없는 것 같다. ↩︎

Consumer 외에도 입력 객체 없이 객체를 반환하는 Supplier 인터페이스와, 객체를 입력받아 객체를 반환하는 Function 인터페이스가 있다. ↩︎

Java 8에서 함수형 프로그래밍 인터페이스가 추가됬다는 건 알고는 있었지만 이렇게 소소하게나마 적용해본건 처음이라 기쁘다. Java 8에 대한 좋은 튜토리얼을 찾았는데 잘 정독하고 적용해보고 싶다. ↩︎

[ehwaz-t]

코딩 문제 템플릿 with 테스팅

나는 코딩 문제 사이트로 HackerRank를 즐겨 이용하고 있다. 이 사이트가 다른 서비스들과 소소하게 다른 점은 문제를 풀면 원하는 테스트 케이스를 열 수 있는 Hacko라는 포인트를 준다는 것이다. 끙끙 앓지 않고 내가 통과하지 못한 케이스를 직접 받아서 테스트해볼 수 있다는게 참 마음에 든다.1

테스트 케이스는 input, output txt 파일으로 각각 주어지는데, 사실 이런 웹기반 online judge에서는 입력 파일이 조금만 커도 입력이 안되는 경우가 다반사라서 결국 로컬 환경에서 직접 돌려야 한다. 하지만 암만 익숙한 코드여도 File I/O API를 써넣을 때마다 여간 거슬리는게 아니었다.

그래서 이 참에 파일 입출력도 적절히 처리하고 결과 테스트도 자동 판별할 수 있는 적절한 IDE 템플릿을 만들어보자고 마음먹었다. 애당초 테스트 주도 개발이라는 개발 프로세스도 있는 마당에 테스트 라이브러리 적용해보자 생각도 하고 있었고. 그리고 코딩 문제는 성공/실패 조건이 분명하게 주어지니 어찌보면 테스트 케이스를 적용하기에 가장 간편한 예제다.

사용하기 편리한 템플릿의 조건으로 다음 세 가지를 생각해보았다.

테스트 라이브러리를 사용하여 테스트 케이스를 간편하게 구성할 수 있다.

Online judge 서비스에서 짠 문제 풀이 코드를 최대한 그대로 사용할 수 있다.

테스트를 수행하기 위해 짜야 하는 코드량을 되도록 줄인다.

다행히도 스스로 생각하기에 세 조건을 모두 만족하는 템플릿을 만들 수 있었다. 다음은 그 과정을 정리한 내용이다.

테스트 라이브러리 선택

코딩 문제 풀이에는 Java를 주로 사용하고 있다. Java 테스트 라이브러리로는 Junit과 TestNG가 많이 사용되는 것 같다. 차이점을 비교한 포스트를 보니 TestNG에서는 test group 구성과 method간의 dependency test가 추가로 가능하다고 한다. 필요한 기능들은 아니지만 두 라이브러리의 interface가 거의 같기 때문에 이왕이면 기능이 더 많은 TestNG를 선택했다. 사용 방법은 IntelliJ의 친절한 도움말을 참고했다.

Junit과 TestNG 둘다 아래와 같은 테스트 클래스 구조를 사용한다.

package example; import org.testng.annotations.*; public class ExampleTest { @Beforetest public void setUp() { // 이 메소드는 각 테스트가 실행되기 전에 실행된다. } @AfterTest public void tearDown() { // 이 메소드는 각 테스트가 실행된 후에 실행된다. } @Test public void test1() { String answer = "정답"; // 주어진 정답과 실행 결과가 같음을 확인한다. Assert.assertEquals("정" + "답", answer); } @Test public void test2() { ... } }

시도 1: 입출력 코드와 문제 풀이 코드의 분리

어디서 유닛 테스트에 대해 주워들은 건 있었던지라, 맨처음 생각했던건 아래처럼 문제를 풀때 입출력 부분은 별도 코드로 빼고, 입력 구조체를 인자로 받고 결과를 리턴하는 문제 풀이 메소드를 따로 구현하는 형식이었다. 이렇게 분리한 이유는 문제 풀이와 입출력의 기능적인 분리 뿐 아니라, 테스트에서 문제 풀이 코드를 그대로 사용하고(조건2) 또 표준 입출력 코드를 파일 입출력으로 교체할 수 있도록 하기 위해서이기도 했다.

public class Solution { public static int[] solveProb(int a, String[] b) { ... // a, b를 사용해서 문제를 처리하고 결과를 리턴 } public static void main(String[] args) { int a, maxSize = 50; String[] b = new String[maxSize]; ... // stdin의 내용을 받아 입력 자료 구조체 a, b에 저장한다. int[] result = solveProb(a, b); ... // result의 내용을 출력한다. } }

이 경우 테스트 케이스는 아래처럼 짜게 된다.

public class SolutionTest1 { int a; String []b; int[] answer; @BeforeTest public void setUp() { ... // input txt 파일을 연다. ... // input 파일을 읽어 값들을 입력 구조체 int a와 String[] b에 입력한다. ... // output txt 파일을 연다. ... // output 파일을 읽어 int[] answer에 입력한다. } @Test public void test1() { int[] result = Solution.solveProb(a, b); Assert.assertEquals(result, answer); // result와 answer가 같은지 비교한다. } }

이 방향으로 시험삼아 짜보다 두 가지 문제를 발견했다.

생각보다 테스팅 클래스에서 입력 구조체를 구성하는 것이 너무 번거롭다. '@BeforeTest' 메소드에서 파일로부터 입력 구조체를 구성해야 하는데, 표준 입력 경우에서 사용한 코드를 복붙하는 식이라 여전히 품이 많이 든다. 게다가 입력 구조체는 각 문제마다 대부분 다르므로 매 문제마다 따로 코드를 짜야 한다. 특히 한 파일에 여러 테스트 케이스가 들어있는 경우는 입력 구조체가 기본적으로 2차원 배열이나 벡터가 되기 때문에 더 끔찍해진다. (조건3 X)

입출력 처리와 풀이 메소드를 나누는 방식 자체가 코드 작성 방식을 제한한다. 대부분의 간단한 풀이들은 입출력 처리와 문제 풀이 로직이 함께 돌아간다. (예: for문 내에서 stdin에서 값을 받아 처리하고 stdout으로 출력) 풀이 메소드와 입출력 처리를 분리하느라 간단한 문제도 복잡하게 짜게 된다. 그리고 코드를 테스트에서 그대로 사용하기 위해 Online judge 사이트에서 간단하게 짠 코드를 일일이 수정하는 것은 너무 비용이 크다.

조건2, 3을 만족할 수 없을 뿐더러 애당초 코드를 짜기가 너무 불편했다. 따라서 문제 풀이와 입출력을 분리하는 방식은 사용하지 않기로 했다.

시도 2: 표준 입출력과 파일 입출력을 같은 코드로 처리하기

문제 풀이 코드와 입출력 처리 코드를 별도로 분리하지 않는 대신, 풀이 코드를 최대한 그대로 사용하기(조건2) 위해 같은 코드로 표준 입출력과 파일 입출력 모두를 처리하는 방향을 선택했다.

입력의 경우, 문제 풀이 메소드는 Scanner 객체를 입력받고 Scanner 객체를 만들때 System.in 또는 File 객체를 사용하는 방식으로 간편하게 인터페이스를 통일할 수 있었다. (참고)

출력의 경우 입력과 동일한 방식으로 문제 풀이 메소드에서는 인자로 받는 OutputStream에 출력하도록 구현하고 필요에 따라 System.out 또는 ByteArrayOutputStream을 메소드에 넘겨주는 방식을 쓸 수 있다. 그러나 System.out 대신 OutputStream 객체를 사용하도록 의식하면서 코드를 짜고 또 지금까지 짠 코드들을 일일이 바꾸는 것도 역시 비용이 꽤 크다고 생각했다.

더 좋은 방법을 찾던 와중에 발견한 것이 테스트 실행 전에 System.out을 임시로 다른 OutputStream 객체로 set하고, 테스트가 끝난 뒤 다시 되돌려놓는 방법[참고1, 참고2]이었다. System.out으로 출력한 내용이 OutputStream으로 들어가기 때문에 실행 결과는 OutputStream 객체로부터 얻을 수 있다. 이 방법은 System.out을 사용한 코드를 그대로 쓸 수 있을 뿐만 아니라 테스트 라이브러리에서 제공하는 '@beforeTest', '@afterTest' annotation으로 깔끔하게 구현할 수 있어서 정말 마음에 쏙 들었다.

위에서 정리한 입출력 방식을 코드로 옮기면 아래와 같다. 문제 풀이 코드의 경우:

public class Solution { public static void solveProb(Scanner sc) { ... // Scanner 객체로부터 입력을 받아 문제를 풀고 stdout으로 출력한다. } public static void main(String[] args) { Scanner stdSc = new Scanner(System.in); // 표준 입력 solveProb(stdSc); } }

테스트 클래스의 경우:

public class SolutionTest2 { private final ByteArrayOutputStream outContent = new ByteArrayOutputStream(); PrintStream original = System.out; ... @BeforeTest public void setUp() throws Exception { ... System.setOut(new PrintStream(outContent)); // System.out 변경 } @AfterTest public void tearDown() throws Exception { System.setOut(original); // System.out 복구 ... } @Test public void testSolveProb() throws Exception { Scanner fileSc = new Scanner(new File("file_path")); // 파일 입력 solveProb(fileSc); // 풀이 메소드를 호출한다. ... // output file의 내용을 answer에 넣는다. String result = outContent.toString(); // 문제 풀이 결과 얻기 Assert.assertEquals(result, answer); } }

정리

중간에 기능별로 구분하기 위해 입출력 처리와 문제 풀이 메소드을 나누었던 것이 제약으로 작용하는걸 겪으며 Knuth옹께서 말씀하신 'Premature optimization is the root of all evil'이 떠올랐다.

어쨌든 이렇게 원하던 조건을 나름 만족하는 템플릿을 만들고 써보니 꽤 마음에 든다(사실 그러니 블로그로 정리까지 하는거지만ㅎㅎ). 앞으로도 두고두고 유용하게 써보련다.

위의 코드들은 내 Github의 problem solving 저장소에 올려놓았다. (SparseArrays, SparseArraysFileTest가 첫번째 방법, SparseArrays2, SparseArrays2FileTest가 두번째 방법의 풀이와 테스트다.) SparseArrays2FileTest가 SparseArraysFileTest보다 훨씬 간단한 것을 확인할 수 있다.

덧) 그외에 자잘하게 문제가 됬던 부분들은

Windows에서 돌리다보니 System.out.println(...)으로 출력하면 [캐리지 리턴]이 붙어서 매 행마다 '\r'이 추가되는 점

'\r'을 제거하는 방법으로 해결

TestNG 실행시 아래 같이 NullPointerException이 나오는 문제

java.lang.NullPointerException at org.testng.SuiteRunnerWorker.runSuite(SuiteRunnerWorker.java:80) at org.testng.SuiteRunnerWorker.run(SuiteRunnerWorker.java:86)

참고 코드에 System.out을 되돌려 놓는 코드가 System.setOut(null);으로 구현이 되어 있어 발생. null 대신 따로 저장해놓은 System.out 객체를 넘겨주는 것으로 해결.

leetCode, Algospot 등의 다른 서비스들보다 HackerRank를 선호하는데는 이것 외에도 다른 이유들이 몇 개 있는데, 나중에 별도 포스트로 간단히 정리해보련다. ↩︎

[ehwaz-t]

개발 블로그, Tumblr, Code snippet

개발 블로그로 사용할 서비스로 Tumblr를 고른 이유는

별도의 설치나 설정없이 간편하게 시작할 수 있을 것 (시작이 반이므로!)

마음에 드는 테마를 쉽게 사용할 수 있을 것 (화단이 예쁘면 더 꾸미고 싶어지므로!)

이렇게 두 가지였다. 더군다나 글 작성 방식으로 Markdown을 지원한다는게 무척 마음에 들었다. WYSIWYG 에디터는 각 서비스들마다 미세하게 다르다는 점이, HTML은 소잡는 칼로 닭잡는 느낌이라는 점 때문에 아무래도 호감이 가지 않았다.

다만, 다른 분들의 개발 블로그 셋업 글들을 읽다보니 개발 블로그 용으로서 Tumblr는 소스 코드를 붙이기 어렵다는 점이 단점으로 지적[1, 2]되는게 맘에 걸렸다. 하지만 포스팅하신지 꽤 시간이 지난 글들이었기에 일단 먼저 구글님께 “tumblr posting code snippets"라고 공손히 물어보았다.

찾아보니 누군가 2달 전 글로 구글의 code-prettify라는 Javascript 라이브러리를 Tumblr theme에 import하여 syntax highlighting을 하는 방법을 그럴듯하게 올렸길래 냉큼 적용해보았다.

아래처럼 HTML 코드를 입력하면

public static helloWorlds(int num) { for (int cnt=0; cnt < num; cnt++) { System.out.println("Hello world!"); } }

아래처럼 나온다!

public static helloWorlds(int num) { for (int cnt = 0; cnt < num; cnt++) { System.out.println("Hello world!"); } }

보이는 결과만으로는 꽤 만족스럽지만, '<', '>'를 일일이 변환해줘야 한다는건 좀 성가시다. 사실 코드를 붙이기 어렵다라고 지적하셨던 건 syntax highlighting이 아니라 이 점을 가리켰던 것 같은데, Tumblr가 작성한 내용 자체를 별도의 변환 없이 그대로 Markdown이나 HTML로 처리하는 이상 어쩔수 없는 것 같다. 결국 내게 장점으로 느껴졌던 점이 단점으로도 작용한 셈이 되었다. (양날의 검?)

HTML이나 CSS 코드의 경우, StackOverflow에 관련 질문이 있어 우회적인 방법으로 일단 출력되게는 할 수 있었다. <code> 대신 <xmp>를 사용하는 방식인데, 사실 저 글의 댓글에서도 지적하듯이 W3C 표준에서는 <xmp> 자체를 부적절한(Obsolete and non-conforming feature) 기능으로 명시하고 있어서 올바른 방향이라고 보긴 어려울 것 같다. 표준에서는 <xmp> 대신 <pre>와 <code>를 사용하고 '<'는 '<', '>'는 '>'로 대체하도록 권장하고 있다.

일단 지금은 호스팅 없이 Markdown으로 블로깅을 해보고 싶은 마음이 문자 변환의 귀찮음보다는 커서 계속 Tumblr를 써볼 생각이다. 긴 코드를 첨부해야겠다 싶으면 Github Gist로 embed해도 될거 같고. 블로그에 재미를 붙였다 싶었을때 본격적으로 Octopress로 넘어가면 좋을 것 같다.

참고) Line number가 매 5줄마다 표시되는게 기본 설정이었는데(대체 왜?) 공식 README 대로 아래 css 코드를 Tumblr theme에 입력해서 해결했다.

li.L0, li.L1, li.L2, li.L3, li.L5, li.L6, li.L7, li.L8 { list-style-type: decimal !important }

덧) Post를 올린 후 수정하려고 다시 열어보니 에디터에는 <, >가 죄다 다시 <, >로 바뀌어서 올라온다?! 덕분에 무심코 저장을 눌렀다가 변환된 HTML 태그들 때문에 글이 작살나버렸다. 일단 글 작성/수정은 atom의 Markdown preview로 하고 백업용으로 어디다 repo를 하나 파야겠다.