[임시] 슬라이딩 윈도우

공통: 블로그 글과 책 내용 및 필기를 내 병행해서 보기

[Java] 문제 009 (백준 12891번)

 

[java] 문제 010 (백준 11003번)

 

 

10번, 최솟값 찾기

핵심은 정렬 알고리즘을 사용하지 않고 슬라이딩 윈도우와 덱을 이용해 정렬 효과를 보는 것
이해 안 되는 건, 정렬은 nlogn의 시간 복잡도를 가져서 n, l의 최대 범위가 5,000,000인 이 문제에서 정렬은 사용 못 한다는 점이다
N이 500만일 때 nlogn 시간 복잡도를 가진 알고리즘의 연산 횟수는 약 111,267,500라고 챗 지피티가 말하네 
되는 거 아님? 시간 제한이 2.4초인데

=> 그렇긴 한데 문제 10번에서 내가 처음 푸려고 한 시도 주석 보면 안 될 것 같다는 추측 내용이 포함되어 있으니, 이게 맞는지는 모르나 참고는 해 보기

 

 

덱이란 양 끝에서 데이터를 삽입하거나 삭제할 수 있는 자료구조

addFirst(), removeFirst(), addLast(), removeLast() => 삽입, 삭제 함수

덱에서는 인덱스, 숫자 형태의 노드를 클래스로 구현하여 저장 => mydeque.addLast(new Node(now, i));

• BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
• Deque<Node> mydeque = new LinkedList<>();
• !mydeque.isEmpty() && mydeque.getLast().value > now
  • &&은 논리연산자, >는 관계 연산자 ⇒ 우선순위는 1. 관계 2. 논리
•         if (mydeque.getFirst().index <= i - L) {
              mydeque.removeFirst();
          }
  
  • Deque의 첫 번째 값이 슬라이딩 윈도우의 범위를 벗어나면 제거합니다.
•         bw.write(mydeque.getFirst().value + " ");
      }
      bw.flush();
      bw.close();
  }
  
  • • 현재 Deque의 첫 번째 값이 슬라이딩 윈도우 내의 최솟값이므로 이를 출력합니다.
    • BufferedWriter를 사용하여 결과를 출력합니다.
• static class Node {
      public int value;
      public int index;
      Node(int value, int index) { 
          this.value = value;
          this.index = index;
      }
  }
• 생성자는 뭔지는 교재 필기 참고

 

1. write()를 사용해도 데이터가 이어지는 이유

BufferedWriter의 write() 메소드는 데이터를 버퍼에 기록합니다. 주어진 코드에서 bw.write(mydeque.getFirst().value + " ");는 반복문 내에서 호출되고 있습니다. 중요한 점은 write() 메소드가 호출될 때마다 덮어쓰기를 하지 않는다는 것입니다. write() 메소드는 버퍼의 현재 위치에 데이터를 추가합니다. 버퍼가 가득 차기 전까지는 데이터가 누적됩니다.

예를 들어, 아래와 같은 코드가 있을 때:

 

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

bw.write("Hello ");

bw.write("World!"); bw.flush();

 

출력 결과는 Hello World!가 됩니다. 이처럼 write() 메소드를 반복적으로 호출하면 덮어쓰는 것이 아니라 버퍼에 데이터를 추가하는 형태로 동작합니다.

주어진 코드에서도 write() 메소드는 루프를 통해 여러 번 호출되며, 각각의 호출은 이전 호출의 데이터를 덮어쓰지 않고 버퍼에 데이터를 추가합니다. 버퍼가 가득 차거나 flush() 메소드가 호출될 때 버퍼의 모든 내용이 출력됩니다.

2. write() 대신 append()를 사용해야 하는지에 대한 의문

BufferedWriter 클래스에는 append() 메소드가 존재하지만, write()와 append() 메소드의 동작은 거의 동일합니다. BufferedWriter의 append()는 내부적으로 write()를 호출합니다. 따라서 실제로는 append()를 사용해도 write()와 같은 결과를 얻습니다.

하지만, append() 메소드는 주로 CharSequence를 추가하는 데 사용됩니다:

 

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

bw.append("Hello ");

bw.append("World!"); bw.flush();

 

위 코드의 결과도 Hello World!가 됩니다.

결론

1. write()를 사용해도 데이터가 이어지는 이유는 버퍼에 데이터를 누적하기 때문입니다. 각 write() 호출은 덮어쓰지 않고 버퍼의 현재 위치에 데이터를 추가합니다.
2. append() 대신 write()를 사용하는 것은 이 코드에서 동등한 효과를 얻을 수 있습니다. 따라서 append()를 사용해야 할 특별한 이유는 없습니다. 두 메소드 모두 데이터를 버퍼에 추가하는 역할을 하므로, write()를 사용하여도 문제없이 데이터를 이어 붙여서 출력할 수 있습니다.