#3 Search

1) Swap Nodes

그냥 이진바이너리 트리&Inorder Traversal 구현하면 된다. 다만, 처음에 그냥 array로 구현하려고 했다가 Swap Operation보고 다시 새로짰다-_-;; Swap operation이 생각보다 복잡해서 array로 다루려니 머리가 아파서.. 이런건 그냥 node둬서 left/right 두고 재귀로 하는게 편하다.

 

2) Hash Table:Ice Cream Parlor

특정값 money를 가지고 아이스크림 cost array중에 살 수 있는 set을 뽑아내는 문제.

for문을 돌면서 각 money-cost[i]를 map에서 찾으면 된다. 

없으면 cost를 map에 저장한다.답은 항상 unique한 조건이 있으니까..언젠간 찾아진다..

 

3) Pairs

정수 array의 pair중에 두 원소를 뺐을때 target value를 만족시키는 set을 찾는 문제. Two pointer 기법을 써야 한다.

일단 sort를 먼저 해주고, first pointer랑 second pointer를 둔다.

 

예를들어, arr = {1,5,3,4,2}라면 sort후엔 arr = {1,2,3,4,5} 이고, target value가 2라면

 

f   s

1  2   3  4  5

 

arr[second] - arr[first]는 target value보다 작으므로 second를 높인다.

f        s   

1   2   3  4  5

 

arr[second] - arr[first]는 target value이므로 결과값 +1 을 해주고, second pointer를 올린다.

 

 

f             s

1   2   3   4   5 

arr[second] - arr[frist} > target value이므로, first를 올린다.

그럼 그 다음에는 first가 2에 위치해있게되고, first와 second사이의 target value를 만족시킨다.

two pointer 기법.

 

4) Minimum Time Required

문제 설명이 많아서 쓰기 귀찮다.. 그냥 특정날짜마다 생산을 하는 기계들이 있다.

예를들어 기계 = { 2,3,2 } 가 있다고 치면. 2일마다 1개 만드는게 2대 있고, 3일마다 1개 만드는게 1대 있다.

그래서 2*n일마다 생산품은 2개씩나오고, 3*n일마다 생산품은 1개씩 나온다.

그래서 특정 goal개수를 만드는데까지 얼마가 걸릴까? 라는 문제다.

 

원래는 그냥 생산품의 개수가 goal이 될때까지 개수를 늘리면서 machine을 돌렸으나 time-out 뜬다.ㅎ..

현재 날짜보다 큰 machine 다 안돌게하고 별짓 다해봤으나 결국 실패.

 

이거는 binary search를 돌려야 함.

현재까지 counting 된 날짜를 기준으로, binary search를 해서 거기까지만 machine을 counting 해야된다.

요새 다시 알고리즘 공부를 하면서 느낀건데, 시간만 많다면 일단 직관적으로 무식하게 풀어놓고 점점 줄여나갈 방안을 찾는게 더 빨리 풀어지는것 같다. 처음부터 compact하게 짜려고 생각하다보면 그 idea만 파고들게되서, 잘못된 idead인경우 빠져나오기가 힘들다. 무식하게 짜놓고 optimization을 생각하자.