[항해99 취업 리부트 코스 학습일지] 2024.04.03(수)

자료구조를 본격적으로 들어갔다.

새로운 조원과 멘토님(기술매니저님)을 만났다.. 내 실력에 비하여 잘하시는 분들을 만난 것 같아서 초큼 부담스럽지만

코드리뷰를 하면서 레벨업 되는 느낌이다..

 

오늘 배운 내용을 정리해서 따로 포스팅했다.

https://devdevleyy.tistory.com/27

[자료구조] Stack, Queue, Deque

 

저기에 적지 않았지만 추가적으로 공부했던 부분 (더 자세하게 해야 하지만, 7일차 일정에 있어서 간략하게)

1. 우선순위 큐

- 들어오는 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나가는 자료구조.

- (Heap, 힙) 을 이용해 구현한다 :  완전 이진트리

- 운영체제 작업 스케줄링, 허프만, 선형탐색 시간줄이기 등에 사용할 수 있다!

 

 

2. 클래스 만들기

백준 문제를 들고 왔습니다.

https://www.acmicpc.net/problem/2493

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) 를 사용했다.

그럼 임시저장보다는 전체 배열을 순환하면서 값을 찾아야 하기에 시간초과, 메모리초과.. 초과.. 자원 낭비일 수 있다는 것을 알았다.

 

우히히 생각하는 개발자가 되자! 꺄르르륵