배열과 List를 활용한 수 찾기

배열과 List를 활용해서 문제를 하나 더 풀어보았다. 

# 백준 1920 수 찾기

백준 1920번 수 찾기 문제이다. 문제를 정리해 보자면 입력받은 수만큼 정수를 입력받고, 다시 입력받은 수만큼 정수를 입력 받아, 그 두번의 입력과 같은 수는 1, 다른 수는 0을 출력하면 된다.

 

지난번 포스팅 때 배운 BufferedReader와 StringTokenizer를 이용하여 최대한 시간 단축을 할 수 있는 입력 방식을 적극적으로 사용해 보기로 했다. 

 

처음엔 List를 활용하려고 했으나, ArrayList의 구현 size는 10이기 때문에 길이 5만큼만 입력 받는 이러한 문제에서는 배열이 훨씬 메모리 소모가 적을 것으로 생각하고 배열로 구현했다. 

1. 배열을 선언하고 for문과 StringTokenizer를 활용하여 처음 배열을 입력 받고, Arrays.sort를 활용해 정렬을 해준다.

2. num에 다음 입력받을 수들을 for문과 StringTokenizer를 활용하여 입력받는다.

3. 수를 맞출 때, List를 활용하면 contains() 메소드를 활용하여 하나하나 찾을 수 있지만, 그건 너무 노가다기 때문에 배제 하고 시작했다. 

-> 그렇다면 뭐가 있을까? 업다운을 생각해보자. 업다운 게임 시 우리는 가장 효율적인 방법으로 중간지점을 잡고 업 다운에 맞추어 범위를 좁혀 나간다. 딱 그 개념을 생각해서, start가 stop보다 작을 경우 업, 다운의 경우는 줄여나가고 해당 숫자를 찾을 경우 1을 바로 출력시켰다. 또한 start>stop보다 큰 경우는 없는 경우니까 0을 출력시켰다. 

 

** 이 예제에서 StringTokenizer를 활용한 것들 중 18번째 줄과 27번째 줄을 보면 한 번더 StringTokenizer를 new로 써서 readLine() 한 것을 볼 수 있는데, StringTokenizer는 딱 한 번만 적용되어 계속 쓰게 될 경우 이런식으로 새롭게 선언해 주어야 했었다. 

 

백준에서 통과는 되었는데, 버퍼를 더 줄이기 위해 StringBuilder를 마지막에 활용하여 다시 풀어보았다. StringBuilder는 String의 경우 append 메소드를 사용하여 출력시 한꺼번에 움직일 수 있게 해준다. Scanner를 BufferedReader로 썼던 것과 같은 유사한 원리인데, 메모리가 확실히 줄어든다. 

 

뒷부분의 출력 부분만 이런식으로 바꾸어 보았다. 약 1700MB가 740MB가 될 정도로 메모리 효율이 확실했다.

 

**StringBuilder : String 형식으로 append를 사용하여 출력시 묶음 단위로 출력을 할 수 있다. 출력은 toString() 메소드를 사용하여 출력한다.