6주차 (07월 27일)
목표
- <이진탐색, 해시> 자료구조 복습
- 복습 후 <이진탐색, 해시> 알고리즘 문제 2~3개 풀기(난이도 : 실버4 이상)
- 팀장 최수연이 추천해준 <해시> 문제 "완주하지 못한 선수" 풀어보기
회고
- 알고리즘 <이진탐색> 문제 : 백준 10815번 (난이도 : 실버4)
해결 방법 : 숫자를 하나 입력 받을 때마다 이진탐색을 사용해서 그 숫자가 있는지 확인한다.
코드일부
int search(int goal, int[] card) {
int left = 0;
int right = card.length - 1;
int mid;
while(left <= right) {
mid = (left + right) / 2;
if(card[mid] < goal) {
left = mid + 1;
}
else if(card[mid] > goal) {
right = mid - 1;
}
else if(card[mid] == goal){
return mid;
}
}
return -1; // 숫자가 없을 경우 -1 return
}
- 알고리즘 <이진탐색> 문제 : 백준 2805번 (난이도 : 실버3)
해결 방법 : 이진탐색을 이용해서 나무의 절반을 잘랐을때 필요한 나무보다 양이 많을 경우 자르는 위치를 높여 더 적게 자르고, 필요한 나무보다 양이 적을 경우 자르는 위치를 낮춰서 더 많이 자르도록 한다.
코드일부
Arrays.sort(tree);
while(left <= right) {
long sum = 0;
mid = (left + right) / 2;
for(int i = 0; i < n; i++) {
if(tree[i] > mid) {
sum += tree[i] - mid;
}
else {
continue;
}
}
if(sum >= m) {
left = mid + 1;
}
else if(sum < m) {
right = mid - 1;
}
}
- 프로그래머스 <해시> 문제 : "완주 하지 못한 선수"
해결 방법 : 참가자들을 모두 HashMap에 넣은 후 완주를 했을 경우 HashMap의 value값을 바꿔줘서 완주하지 못한 사람을 찾는다.
코드일부
Map<String, Integer> m = new HashMap<String, Integer>();
for(int i = 0; i < participant.length; i++) {
if(m.containsKey(participant[i])) {
m.put(participant[i], m.get(participant[i]) + 1);
}
else {
m.put(participant[i], 1);
}
}
for(int i = 0; i < completion.length; i++) {
m.put(completion[i], m.get(completion[i]) - 1);
}
Iterator<String> it = m.keySet().iterator();
while(it.hasNext()) {
String s = it.next();
if(m.get(s) == 1) {
answer = s;
}
else {
continue;
}
}