자료구조를 본격적으로 들어갔다.
새로운 조원과 멘토님(기술매니저님)을 만났다.. 내 실력에 비하여 잘하시는 분들을 만난 것 같아서 초큼 부담스럽지만
코드리뷰를 하면서 레벨업 되는 느낌이다..
오늘 배운 내용을 정리해서 따로 포스팅했다.
https://devdevleyy.tistory.com/27
저기에 적지 않았지만 추가적으로 공부했던 부분 (더 자세하게 해야 하지만, 7일차 일정에 있어서 간략하게)
1. 우선순위 큐
- 들어오는 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나가는 자료구조.
- (Heap, 힙) 을 이용해 구현한다 : 완전 이진트리
- 운영체제 작업 스케줄링, 허프만, 선형탐색 시간줄이기 등에 사용할 수 있다!
2. 클래스 만들기
백준 문제를 들고 왔습니다.
https://www.acmicpc.net/problem/2493
내가 제출한 답안 :
package src.com.company.week2.day1;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Stack;
import java.util.StringTokenizer;
public class BJ_2493_탑_2 {
/* 82908KB|732ms
* 자료구조, 스텍(stack)
* towers 배열에 탑의 높이를 저장
* receiveHeights 에 결과(수신한 높이) 를 저장하고,
* stack 에 수신을 기다리는 탑의 인덱스를 저장
* 현재의 탑이 수신할 수 있는 경우 pop()메서드를 사용하여 탑의 높이를 수신한 높이로 설정하였다.
--------------------------------------------------
*/
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
// 탑의 높이를 저장
int[] towers = new int[N];
for (int i = 0; i < N; i++) {
towers[i] = Integer.parseInt(st.nextToken());
}
int[] receiveHeights = new int[N]; // 수신한 높이를 저장할 배열
Stack<Integer> stack = new Stack<>(); // 수신을 기다리는 탑의 인덱스를 저장하는 스택
// 4-> 7이니까 스택 push
// 왼쪽부터 탐색
for (int i = N - 1; i >= 0; i--) {
while (!stack.isEmpty() && towers[stack.peek()] < towers[i]) {
// 현재 탑이 수신할 수 있는 경우
receiveHeights[stack.pop()] = i + 1; // 현재 탑의 높이를 수신한 높이로 설정
}
stack.push(i); // 현재 탑의 인덱스를 스택에 추가
}
StringBuilder sb = new StringBuilder();
for (int height : receiveHeights) {
// 위의 for 문에서 계속 출력로직 반복되는게 싫어 한번에 출력하도록 함
sb.append(height).append(" ");
}
System.out.println(sb.toString().trim());
}
}
팀원이 제출한 답안을 참고한 것
package src.com.company.week2.day1;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class BJ_2493_탑_2_refectoring {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(st.nextToken()); // 탑의 수
st = new StringTokenizer(br.readLine());
Stack<Tower> stack = new Stack<>(); // 탑을 저장하는 스택
// 첫 번째 탑은 무조건 수신할 수 없으므로 바로 스택에 저장
stack.push(new Tower(1, Integer.parseInt(st.nextToken())));
sb.append("0").append(" ");
// 두 번째 탑부터 시작하여 왼쪽으로 빛을 쏴 부딪히는 탑을 구함
for (int i = 1; i < N; i++) {
int currentHeight = Integer.parseInt(st.nextToken());
while (!stack.isEmpty() && stack.peek().height < currentHeight) {
// 현재 탑이 수신할 수 있는 경우
stack.pop();
}
if (stack.isEmpty()) {
sb.append("0 ");
} else {
sb.append(stack.peek().index + " ");
}
stack.push(new Tower(i + 1, currentHeight)); // 현재 탑의 인덱스와 높이를 스택에 추가
}
System.out.println(sb);
}
// 탑을 나타내는 클래스
static class Tower {
int index; // 탑의 인덱스
int height; // 탑의 높이
public Tower(int index, int height) {
this.index = index;
this.height = height;
}
}
}
이렇게 클래스를 만들어 두면 값을 담아두고 필요할 때 바꿔서 사용할 수 있어서 편하다.
불필요한 변수를 줄일 수 있어서 덜 헷갈린다.
+ 느낀점
여러개의 값이 필요할 때 Collection 함수들(Set, Map, LinkedList) 를 사용했다.
그럼 임시저장보다는 전체 배열을 순환하면서 값을 찾아야 하기에 시간초과, 메모리초과.. 초과.. 자원 낭비일 수 있다는 것을 알았다.
우히히 생각하는 개발자가 되자! 꺄르르륵
'항해99 취업 리부트 코스 학습일지' 카테고리의 다른 글
[항해99 취업 리부트 코스 학습일지] 2024.04.06(토) (0) | 2024.04.08 |
---|---|
[항해99 취업 리부트 코스 학습일지] 2024.04.04(목) (0) | 2024.04.05 |
[항해99 취업 리부트 코스 학습일지] 2024.04.01.(월) (0) | 2024.04.01 |
[항해99 취업 리부트 코스 학습일지] 2024.03.30.(토) (0) | 2024.03.31 |
[항해99 취업 리부트 코스 학습일지] 2024.03.29.(금) (0) | 2024.03.29 |