2022.11.21.MON

ronglong·2022년 11월 21일
0

코드스테이츠 Day23

  1. 자료구조
  • 데이터의 저장/활용 방식
  • 자주 등장하는 네 가지의 자료구조 : Stack, Queue, Tree, Graph
  1. Stack
  • LIFO(Last In First Out) 후입선출
  • 막다른 골목, 프링글스
  • 입출력 방향 같음. 단 하나의 입출력 방향.
  • push() & pop()
  1. Queue
  • FIFO(First In First Out) 선입선출
  • 톨게이트, 줄 서기
  • 입출력 방향 다름.
  • add() & poll()

<느낀 점>
간단하게 자료 구조의 개념만 확인하고, 자료구조 코플릿 문제 1~5번 푸는 날.
1,2 번은 개념 확인 용도였고,
Stack을 이용하여 푸는 3번 '브라우저 앞/뒤로 가기'도 조건이 거의 슈도 코드 수준으로 적혀있어서, 조건을 보고 코드 구현만 하면 되어서 잘 풀었다.

3번 풀고 약간 의기양양하다가,
4번에서 계속 7개 중에 4개만 통과했는데, 갖은 수를 써도 안 되길래 일단 넘어가서 5번을 풀기 시작.

5번은 너무 복잡하길래 고민 좀 하다가 제공된 풀이 영상을 보기로 했다.
풀이 영상 보면서 이해하고, 참고하면서 풀고 제출.

5번으로 어떻게 Queue를 쓰는지 봤으니, 4번은 직접 풀기로 했다.
원래 4번을 Queue가 아닌, ArrayList 써서 풀고 있었는데, 다시 큐로 바꿈.
'박스 포장' 문제인데 5 1 5 5 5 의 경우에서 막히고 있다.
아래는 내가 여러 방식으로 시도해 본 코드들.

	int count = 1;
    Queue<Integer> queue = new LinkedList<>();

    for(int i=0; i<boxes.length; i++){
      for(int j=i; j<boxes.length; j++){
        if(boxes[i] > boxes[j]) count++;
      }
      queue.add(count);
      break;
      }
      int max = Collections.max(queue);
      return max;

이렇게 하면 5 1 2 3 같은 경우는 잘 세어지지만, 5 1 5 5 는 못 셈.
4/7 통과.

	Queue<Integer> queue = new LinkedList<>(); 
    // 앞 숫자 보다 작은 숫자가 이어질 때 5 1 4 6 3
    // 앞 숫자들은 작고 같은 수가 이어질 때 5 1 5 5 
    // 맨 앞 숫자보다 큰 숫자가 나올 때  
    while(boxes.length>0){
      for(int i=0; i<boxes.length; i++){
        if(boxes[0]<boxes[i]){ 
        //첫 번째보다 많은 박스의 손님이 있다면, 
        // 해당 손님 앞까지 인원수를 전달하고
        // 남은 손님으로 새 배열.
        queue.add(i);
        boxes = Arrays.copyOfRange(boxes, i, boxes.length);
        continue;
        }
        else{ // 첫 번째 손님 박스가 제일 많으면
        queue.add(boxes.length);
        boxes = new Integer[]{};
        }
      }
    }
    return queue.stream().mapToInt(i->i).max().getAsInt();

레퍼런스 찾아봤으나 잘 안 나왔는데,
어떤 방식으로 접근하는지 슈도 코드가 있길래 참고해서 만들어 본 코드.
이건 2/7 통과.

참고한 레퍼런스는 이건데, Java 아니고 JS라서 다름. 그냥 슈도 코드만 참고함..
https://intrepidgeeks.com/tutorial/code-parsing-packing-queue-box

	int count = 1;
    Queue<Integer> queue = new LinkedList<>(boxes); 
    while(queue.size()>0){
      for(int i=0; i<queue.size(); i++){
        if(queue[0]>=queue[i]){ 
          queue.poll(); 
          count++; 
        }
        else{
          queue.poll(); 
        }
      }
    }

좀 더 적극적으로 큐를 써보려고 작성한 코드. 만들다가 말았음.

첫 번째 코드 좀 수정하거나, 두 번째 코드 수정하면 뭔가 될 것 같은데 안 된다..
오늘은 그만해야지.

0개의 댓글