10818번 : 최소, 최대

배열은 별거 아니다. 별이 배열거 아닌 이유가 뭐냐면, 우선 별은 배열로 어렵지 않는 데다가 나는 남들보다 몇   배열   심히 별의배열 문제를 매열배일 풀고 있기 때문배열.replaceAll("배열", "별");
 
이번 문제는 그냥 아이디어만 있으면 2분만에 콧등 벅벅 긁으며 풀 수 있는 문제였지만, 메모리와 시간 비교를 위해 여러가지 시행착오를 겪었던 문제였다. 이번 문제로 깨달은 것으로 이번 문제 뿐 아니라 앞으로의 코테에 여러가지 도움을 받을 수 있을 거 같다. 
 

문제 풀이의 아이디어와 여러가지 시행착오를 공개하겠다. 
 
 
 
1. 정렬로 풀기

문제 보자마자 Arrays.sort() 안 떠오른 흑우 없제~~
간단한 아이디어로, input 받은 값들을 배열에 넣어서 정렬하면
맨 처음 index엔 가장 작은 수가, 맨 끝 index엔 가장 큰 수가 온다는 아이디어이다.
하지만 Arrays.sort로 푼다면 아주 큰 문제가 생기는데..

 

무수하게 많이 들어오는 숫자들을 넣기 위한 무수하게 큰 공간의 배열을 만들고, 거기다 또 일일이 숫자를 집어 넣고 또 정렬하는 작업 때문에 굉장히 크고 아름다운 메모리 크기와 실행 속도가 나온다. 아무래도 우리의 원활한 취업과, 평탄한 개발자의 여생을 위해서는 본 방법은 실용성이 없을 것 같다. 그럼 시간을 줄이는 방법은 뭐가 있을까?
 
 
2. 바로 숫자 비교하기

그냥 순서대로 하나씩 빼자마자 바로 연산하는 방법이다. 개별적인 연산 시간은 굉장히 짧고, 따라서 새로운 배열을 만드는 것보다야 당연히 더 적은 시간과 메모리가 소요된다.
 
초깃값으로 min에 큰 수를, max에 작은 수를 넣는 이유는 애초에 반대로 넣어야 논리적인 동작이 잘 되기 때문이다.
만약 min에 1을, max에 100을 넣었다고 가정해보자. 배열을 받았는데 배열에는 2부터 99까지 숫자가 들어있네?
그럼 2부터 99까지 비교 연산을 다 거치고 나와도 min은 여전히 1, max는 여전히 100이며, 이는 배열에는 들어 있지 않는 숫자들로 논리적인 오류가 발생한다.
따라서 아싸리~ min에 무한대를 넣고 max에 -무한대를 넣고 시작하면 처음 숫자를 받을 때 어차피 첫 숫자는 무한대보단 작고 -무한대보단 클 것이므로 min과 max에 동시에 같은 첫 숫자가 들어가고, 그럼 배열이에 어떤 숫자가 있든, 혹여 배열이 딱 하나의 숫자만 가지고 있더라도 논리적으로 맞는 연산이 되는 것이다.
 
 
 
자, 이 방법이 비교 방법으로서는 최선인 것 같고, 이제 이 다음부터는 디테일한 부분을 건드려 보았다.
 
 
 
2-1. 입력값 받기 교체. (Scanner -> BufferedReader + StringTokenizer)

벌써 이 방법만으로도 메모리를 3.5배, 속도를 4배가량 발전시켰잖아?!?!?!?!?!?!?!?!?!?
 
이 방식은 입력값을 한 숫자씩 따로 받는 방법이 아니라, 한 뭉텅이로 쭈욱 받아 놓고 그 후에 한 숫자씩 나누는 방식이다.
당신이 미니 이름표를 만든다고 생각하자. 100명의 이름을 쭉 프린트 해놓고 하나씩 잘라야 하는데, 이걸 하나 프린트해서 자르고.. 또 하나 프린트해서 자르고.. 보다는 이름표를 한 줄로 만들어 한번에 주욱~ 프린트하고 개별로 자르는 게 더 시간이 빠르지 않을까?
 
해당 코드는 그런 방법론의 코드이다. BufferedReader는 buffer이라고 하는 조그마한 공간에 넣을 수 있는만큼 입력값을 욱여넣고 한번에 전달한다. 100명의 이름이 한 줄에 담긴 이름표를 br.readLine()으로 읽었다면 가위질은 StringTokenizer가 해준다. StringTokenizer(문자열, 구분 문자) 는 문자열을 구분문자로 나누어 token의 형태로 담는다. 본 문제는 숫자마다 한 칸씩 띄어쓰기가 되어 있기 때문에, 구분 문자를 " " 으로 해놓으면 한 숫자씩 token에 담길 것이다. 그럼 이제 이 토큰을 가지고 하나씩 처리하면 된다. (StringTokenizer 관련 함수에 대한 질문이 있다면 댓글을 남겨주세용)
 
추가로, 아까 max에는 되게 작은 숫자를, min에는 되게 큰 숫자를 넣어야 한다고 했다. Integer 클래스에 존재하는 상수 변수 MAX_VALUE와 MIN_VALUE는 int 변수에 담길 수 있는 가장 큰 수와 작은 수를 반환해준다. 그리고 Math.max(a, b), Math.min(a, b) 함수는 a와 b 중 큰 숫자(max)와 작은 숫자(min)을 반환해준다.
 
 
 
나는 아직 배고픈 개발자. 더 적은 메모리와 더 적은 시간을 원해!!!!!!!!!!!!!!!!!!!!!
 
 
 
2-2. 최대/최소 값 교체. (Integer.MAX_VALUE/MIN_VALUE -> 1000001/-100001)

max와 min을 가능한 한 가장 작은 숫자와 가장 큰 숫자에서, 문제의 범위를 아주 조금만 벗어나는 숫자로 직접 수정을 해주었다. 메모리와 속도가 조금 줄어들었지만, 이렇다 할만큼의 큰 변화는 아니다. 하나만 더 해보자.
 
 
 
2-3. 비교 함수 교체. (Math.min/max(a, b) -> if (a > b))

의외로 함수를 쓰는 것보다 if문법을 쓰는 게 속도가 조금 더 빨라졌다. 메모리가 조금 더 늘어나긴 했지만.. 뭐 속도나 메모리나 역시 유의미한 차이로 보이진 않는 것 같다. 그래도 속도가 조금 더 빨라진 게 좋겠지?
 
 
 
그래서, 당신은 우리와 함께 갑시다!

 
가끔은 가장 기초적인 방법이 최선의 수가 될 수도 있다는 걸 배웠다. 화려한 API의 라이브러리 함수들에게 현혹되기보다는, 튼튼한 기본기로 코테를 맞서는 연습을 해보자. 코딩 거 참 겁만 먹었지 막상 해보니까 배열거 아니구만~~~