9주차 주말이 되었습니다.
저는 주말 아침에는 1~2시간 정도 프로그래머스에서 문제를 풉니다.
자기전에 문제를 풀면 밤새 자는동안 그 문제가 머리 속에 맴돌아서 밤늦게는 최대한 안풀려고 조심합니다.
시간이 좀처럼 나지 않아 틈날때 조금씩 하던게
이제 레벨1에서는 모든 문제를 끝내서 레벨 2 문제를 풀고 있습니다.
오늘도 그렇게 어려워 보이지는 않던 문제를 하나 골라
몇분만에 정확성 테스트를 모두 통과해서. 쉽게 해결하는 줄 알았는데,
프로그래머스 문제 풀때 가장 절망적인 순간
갑자기 까꿍 하고 등장한 효율성 테스트.. 그리고 결과적으로 이 문제 풀이에 소중한 주말을 모두 쏟아부었습니다.
'더 맵게' 라는 문제였는데, 스포일러가 될까봐 자세한 내용은 담지 않겠습니다.
간단하게만 문제를 설명하자면
- 주어진 배열의 최소값과 특정 값(K)를 비교하여 최소값이 더 크면 종료하며 반복횟수 리턴
- 최소값 2개가 빠지며 배열에 새로운 값 추가
- 끝까지 최소값이 특정 값보다 커지지 않으면 -1 리턴
이러한 작동을 하는 프로그램을 구현하는 문제 입니다.
1. 새로운 값 추가 될때마다 List 에 추가 후 정렬 하며 반복문을 돌렸습니다
저 위의 첨부사진처럼 정확성은 모두 통과했지만 효율성에서 바로 낙제당하는 결과를 받았습니다.
이때까지만 해도 조금만 시간을 줄여주면 효율성 통과가 가능하다고 생각하고 큰 틀에서 변화 없이 코드를 조금씩 다듬어 보았습니다.
2. 리스트가 이미 정렬되어 있고, 새로 추가되는 값이 작은 편에 속하기 때문에 List를 왼쪽부터 확인하며 새로운 값(result)가 들어갈 자리를 찾아서 index로 반환 한 뒤, list.add(index,result) 해 보았습니다.
static public int getIndex(ArrayList<Integer> list, int result){
final int SIZE = list.size();
for(int i=0 ; i<SIZE ; i++) {
if( result < list.get(i))
return i;
}
return list.size();
}여전히 통과할 수 없었습니다.
3. 효율성을 조금이라도 더 끌어내기 위해 코드가 복잡해지지만 이것 저것 수를 써보았습니다.
새로운 값 이 추가될때 해당 값이 특정값(K) 보다 크다면, 굳이 List에 추가 할 필요가 없기 때문에 list에서 2개만 delete 되고, 새로운 값을 따로 추가시키지 않았습니다. 다만 마지막에 -1이 리턴되지 않도록 boolean 값을 하나 변경해 주도록 해 보았습니다.
식이 굉장히 복잡해 졌는데, 효율성은 별반 차이가 없었습니다. 이쯤에서 이미 1시간 이상 지난 듯 합니다.
오전 11시가 되었습니다.
Covid 19의 영향으로 유투브를 통해 영상 예배가 가능해진 시대입니다.
저의 와이프는 예배시간에 코딩하고 있는걸 허용하지 않습니다.
얌전히 앉아 유투브속 목사님을 바라보고 있어도, 머리속에는 정렬과 검색이 수없이 떠다녔습니다.
예배가 끝나자 마자 바로 생각했던것들을 구현해 봅니다.
이번엔 학원 수업시간에 가볍게 배우고 지나갔던 Tree 구조를 써먹어 보기로 했습니다.
class Tree{
public int value;
public Tree leftChild;
public Tree rightChild;
public Tree parent;
public Tree(int value, Tree parent) {
this.value = value;
this.parent = parent;
this.leftChild = null;
this.rightChild = null;
}
}parent 는 원래 안만들었었는데, 최소값을 삭제하려고 하니 노드들을 다시 붙여줘야 할 일이 있길래 나중에 추가해서 넣어주었습니다.
class BinarySearchTree{
private Tree root = null;
public Tree insertKey(Tree root, int value,Tree parent) {
Tree p = root;
Tree newTree = new Tree(value, parent);
if(p==null) {
return root=newTree;
}else if(p.value < newTree.value) {
p.rightChild = insertKey(p.rightChild,value,root);
return p;
}else {
p.leftChild = insertKey(p.leftChild,value,root);
return p;
}
}
public void removeSmallest() {
Tree p = searchMin(this.root);
if(p.parent != null && p.rightChild != null ) {
p.parent.leftChild = p.rightChild;
p.rightChild.parent = p.parent;
}
else if(p.rightChild != null) {// parent is null and it has child
this.root = p.rightChild;
p.rightChild.parent = null;
}else if(p.parent !=null) { // parent is not null, and it doesn't have child
p.parent.leftChild = null;
}else { // parent is null and it doesn't have any children
this.root = null;
}
}
public void insertBST(int value) {
root= insertKey(root,value,root);
}
public void inOrder(Tree root) {
if(root != null) {
inOrder(root.leftChild);
System.out.print(root.value + " ");
inOrder(root.rightChild);
}
}
public Tree searchMin(Tree root) {
if(root.leftChild != null) {
return searchMin(root.leftChild);
}else return root;
}
public Tree searchMin() {
return searchMin(root);
}
}재귀호출은 해본적이 없다보니 구글에서 검색하며 재귀 호출하는 부분들을 많이 보고 따라 해 보았습니다.
출력부분은 사실 풀이에는 필요가 없는 부분이지만, 중간 중간 테스트를 위해서 참고자료를 보며 구현했습니다.
removeSmallest()나 searchMin()은 연습장에 연필로 끄적거려 가며 작성했는데, 별로 안복잡해 보여도 저게 정말 머리가 지끈 지끈 아플 정도로 어려웠습니다. else 달아가며 null을 쓰는건 몇번을 고쳐 쓰다가 볼때마다 헷갈려서 그냥 주석을 달아버렸습니다. 주석을 달았어도 봐도 헷갈리는건 마찬가지긴 했습니다.
효율성이 2배 이상 좋아졌지만..?
테스트 11 : 6.10ms - > 2.46ms
테스트 12 : 25.76ms -> 10.23ms
테스트 13 : 11.26ns -> 4.74ms
힘들게 풀어서 코드를 실행해 봤습니다. 테스트 통과 시간이 전보다 절반 이하로 내려갔기에 됐다 싶었습니다.
아! 힘들지만 보람은 있었다! 드디어 통과하는 구나 싶었지만..
왠걸 여전히 시간 초과였습니다.
이렇게 예배 끝난후에 2시간이 더 지났고 오후 2시가 되었습니다,
고맙게도 와이프가 식사를 차려줘서 편하게 식사를 했습니다.
여기부터는 와이프와 한참을 논의해 보았습니다.
제 와이프는 프로그래밍은 전혀 모르지만, 논리적인 사고력이 좋기 때문에 제가 풀이에서 막힐 때마다 전혀 다른 새로운 방식의 접근 실마리를 주곤 합니다.
논의 끝에, 트리구조가 자료 검색에는 훌륭하지만, 자료를 추가 하고 제거 할때에 효율성이 떨어지는 면이 있기에
배열과 트리의 각 장점을 섞어서 해결해보기로 결정했습니다.
자료의 구조 자체는 배열 (자료 추가를 위해 List) 형식으로 가지만,
이미 정렬된 리스트에 새로운 값이 추가될때 그 index를 찾는 알고리즘으로
'이진 탐색'을 사용해 보기로 했습니다.
여기 부터 이 글의 주제인 이진탐색 알고리즘을 시작해보도록 하겠습니다.
ArrayList<Integer> list = new ArrayList<>();
Arrays.sort(scoville);
for(int i : scoville) {
list.add(i);
}
int count = 0;
while(true) {
int SIZE = list.size();
if(list.get(0) >= K)
return count;
if(SIZE <= 2) {
if(SIZE==2) {
if(list.get(0) + list.get(1) *2 >= K)
return count+1;
else return -1;
}else if(list.get(0) >= K)
return count;
else return -1;
}
count++;
int small1 = list.get(0);
int small2 = list.get(1);
int result = small1 + small2 * 2;
list.remove(0);
list.remove(0);
int index=getIndex(list,result);
list.add(index,result);
}새로운 값 result ( small1+small2*2) 이 들어갈 자리 (index)를 찾아
list.add(index,result); 시키는 코드를 작성했습니다.
static public int getIndex(ArrayList<Integer> list, int result){
int mid = 0;
int left = 0;
int right = list.size() - 1;
while(left +1 <= right) {
mid = (right+left) / 2;
if(result < list.get(mid))
right = mid-1;
else
left = mid +1;
}
return list.get(left) < result ? left+1 : left;
}binary search를 하는 메서드 입니다.
일단 탐색할 범위의 양 끝을 left와 right 로 지정해 준 뒤, 그 중간값을 비교할 값(result)와 비교하며
한번 비교할 때 마다 반씩 범위를 좁혀갑니다.
이미 있는 값을 찾는 거라면 중간에 럭키로 얻어 걸릴 수도 있겠는데,
중복값이 있을지 없을지 확실하지 않고, 없을 확률이 대부분인 문제이다 보니
모든 경우에서 2^x > list.size() 횟수만큼 비교가 필요합니다.
log2(list.size()) 만큼의 횟수 계산이 매번 필요한게 불만스럽긴 하지만 배열의 최대길이인 100만 에서도 20번의 연산만 하면 되니깐, 괜찮지 않을까란 생각도 들었습니다.
어찌됐든, 찾고자 하는 값이 확실히 존재할때는 성능이 제법 좋지 않을까란 생각이 드는 탐색입니다.
열심히 만든 코드로 다시 한번 제출 해 보았습니다.
미세하지만 시간이 더 빨라졌습니다.
테스트 11 : 2.46ms -> 1.83ms
테스트 12 : 10.23ms -> 9.03ms
테스트 13 : 4.74ms -> 2.24ms
아 이건 정말 됐다 싶었는데 효율성에서 실패를 했습니다.
아... 코드를 처음부터 다시 들여다보며 조금이라도 더 빨라질 수 있을만한 여지를 찾아보았습니다.
아까 했던 , 새로운 값이 비교값보다 클때 List에 추가를 건너띄는 방법 등 이것저것을 해 보았지만 소용이 없었습니다.
오후 5시가 되었습니다
주말이 이렇게 다 끝나버렸습니다.
평일에는 혼자 공부할 수 있는 시간이 그닥 많지 않기때문에 주말에 최대한 공부를 많이 하려고 하는 편인데,
문제 하나에 하루를 다 써버렸습니다.
평소에 공부 하고 싶었던 '자료구조'에 대한 공부라고 긍정적으로 생각하며 했는데 이렇게까지 효율성 테스트를 통과 하지 못하니 너무 속상했습니다.
'힙(Heap)' 이 뭔지 모르지만, 힌트를 얻기 위해 지금부터라도 공부해 봐야겠단 생각이 들었습니다.
자바의 정석 3판
자바의 정석 책에서 관련 내용을 찾아 봤는데, '이 자료구조에 대한 설명은 책의 범위를 넘어서므로 자세한 설명은 생략한다.' 로 지나갔습니다.
시간을 너무 많이 써버린 관계로, 오늘 안에 해결은 해보기 위해 일단 라이브러리를 쓰기로 했습니다.
java 에서는 PriorityQueue를 이용하면 해당 자료구조를 사용할 수 있습니다.
while(q.size() > 1 && q.peek() < K) {
count++;
int min = q.poll();
int min2 = q.poll();
int result = min + 2 * min2;
q.add(result);
}문제에 대한 해답이 되기 때문에 코드의 반복문인 6줄 정도만 가져왔지만,
사실 전체 코드도 막상 써보니 10줄 가량밖에 안됩니다. 참 허무합니다.
테스트 11 : 1.83ms -> 1.91 ms
테스트 12 : 9.03ms -> 4.09 ms
테스트 13 : 2.24ms -> 2.64 ms
테스트 12번을 제외하곤 직전에 List와 이진탐색으로 구현했던 것과 큰 차이는 나지 않는 듯 한데
효율성 테스트에서 모두 통과가 되었습니다.
큰 차이가 나지는 않는 것 같아서 List풀이에 미련이 남아 몇번 코드를 좀 더 다듬어 봤지만, list를 이용해서는 끝내 통과해 내지 못했습니다.
오후 6시 30분
이렇게 하루를 괴롭힌 문제와 조금은 찝찝한 작별을 했습니다.
앞으로 이진 탐색과 정렬에 대해서는 따로 책을 구입해 혼자 공부해 볼 생각이었기때문에 더 큰 미련을 두진 않기로 합니다.
2주 전 주문한 맥북 에어가 2주 후 쯤에 배송 될 듯 합니다.
이번 맥북의 성능에 대해 조사를 해보니 너무 기대가 되어 주문을 했는데
하루에도 변하지 않는 애플 스토어 주문내역을 세번씩은 새로고침 해보고 있습니다.
앞으로 짧은 기간 안에 이루고 싶은 몇가지의 목표가 생겼습니다.
- java 책 공부 마치는 대로 ( 80% 가량 완료) 파이썬 시작해보며 익숙해지기
- 프로그래머스 코딩테스트 최대한 빠르시간 내에 파이썬으로 전환
- eclipse에만 의존하지 않기 위해 맥북 오는 대로IntelliJ 설치해 익숙해지기
- javascript 공부를 위해 JS를 이용한 토이 프로젝트 시작해보기
'Development > Fundamentals' 카테고리의 다른 글
| 2의 10000제곱을 MOD로 나눈 나머지 구하기 (0) | 2023.05.06 |
|---|---|
| java로 작성해보는 정렬 알고리즘과 성능 비교 (0) | 2021.08.03 |
| 네트워크 표준 모델 OSI 7 계층 ( OSI 7 Layer) (0) | 2021.07.22 |
| 객체지향설계 5대원칙 SOLID (4) | 2021.04.11 |