Techit 13th 4th

Huisu·2023년 7월 13일
heapifymessage brokerpriority queuewebsocket
0

Techit

목록 보기
33/42
post-thumbnail

Heap

N 번째 큰 수

2075번: N번째 큰 수

문제

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

1279155
13811196
2110263116
4814283525
5220324149

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

출력

첫째 줄에 N번째 큰 수를 출력한다.

예제 입력 1

5
12 7 9 15 5
13 8 11 19 6
21 10 26 31 16
48 14 28 35 25
52 20 32 41 49

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class two2075 {
    public int solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        // 우선 순위 큐 만들기
        // 최소값이 먼저 나오는 우선 순위 큐
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer token = new StringTokenizer(reader.readLine());
            for (int j = 0; j < n; j++) {
                priorityQueue.offer(Integer.parseInt(token.nextToken()));
                // 우선 순위 큐의 크기를 일정하게 유지
                if(priorityQueue.size() > n) {
                    // n개의 숫자만 남기고 작은 숫자를 우선 순위 큐에서 빼고 있기 때문에
                    // 최종적으로 남은 숫자는
                    // 큰 숫자 n 개
                    priorityQueue.poll();
                }
            }
        }
        return priorityQueue.peek();
    }

    public static void main(String[] args) throws IOException {
        System.out.println(new two2075().solution());
    }
}

카드 합체 놀이

15903번: 카드 합체 놀이

문제

석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!

아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.

  1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
  2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 목표이다.

아기 석환이는 수학을 좋아하긴 하지만, 아직 아기이기 때문에 점수를 얼마나 작게 만들 수 있는지를 알 수는 없었다(어른 석환이는 당연히 쉽게 알 수 있다). 그래서 문제 해결 능력이 뛰어난 여러분에게 도움을 요청했다. 만들 수 있는 가장 작은 점수를 계산하는 프로그램을 만들어보자.

입력

첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.

두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 1,000,000)

출력

첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.

예제 입력 1

3 1
3 2 6

예제 입력 2

4 2
4 2 3 1

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/15903
public class one15903 {
    public long solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer infoToken = new StringTokenizer(reader.readLine());
        int cardCount = Integer.parseInt(infoToken.nextToken());
        int actions = Integer.parseInt(infoToken.nextToken());
        StringTokenizer cardToken = new StringTokenizer(reader.readLine());
        // 우선 순위 큐에 넣어 주기
        PriorityQueue<Long> smallestCard = new PriorityQueue<>();
        for (int i = 0; i < cardCount; i++) {
            smallestCard.offer(Long.parseLong(cardToken.nextToken()));
        }

        // 두 개의 숫자를 뽑아서 합한 뒤
        // 다시 우선 순위 큐에 두 번 넣기
        for (int i = 0; i < actions; i++) {
            // TODO
            long x = smallestCard.poll();
            long y = smallestCard.poll();
            smallestCard.offer(x + y);
            smallestCard.offer(x + y);
        }
        long answer = 0;
        for (int i = 0; i < cardCount; i++) {
            answer += smallestCard.poll();
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {
        System.out.println(new one15903().solution());
    }
}

Heap Sort

Heap의 특성을 사용해서 정렬하는 알고리즘이다. 그냥 힙에 다 넣었다가 빼는 방법이 있고, 주어진 배열을 최대 힙으로 변환한 다음 제일 큰 원소를 반복해서 뒤로 보내는 방법이 있다. 최악의 경우 시간복잡도는 O(nlogN)O(nlogN)이고 병합 정렬과 같은 추가 데이터 할당이 필요하지 않는다.

이때 주어진 배열을 힙의 형태로 변환하는 과정을 Heapify라고 한다.

  1. 자식을 가지고 있는 가장 높은 레벨의 노드 위치부터 시작
  2. 노드와 자식 노드들의 관계가 힙 속성을 만족하도록 교환을 진행
  3. 이후 상위 노드에서 반복
public class BinaryMaxHeap {
    private int[] heap;
    private int size;

    public BinaryMaxHeap() {
        heap = new int[32];
        size = 0;
    }

    // arr는 힙이 아니라고 가정
    public BinaryMaxHeap(int[] arr) {
        // TODO
        // 주어진 arr를 heap의 형태로 저장
        heap = Arrays.copyOf(arr, arr.length);
        size = heap.length;
        // 마지막 자식이 존재하는 노드
        int lastIndex = (size - 1);
        int lastParentIndex = (lastIndex - 1) / 2;
        // reHeapDown

        for (int i = lastParentIndex; i >= 0 ; i--) {
            reHeapDown(i);
        }
    }

    public boolean isEmpty() {
        return size == 0;
    }

    private void reHeapDown(int index) {
        while(index < size) {
            int leftChild = index * 2 + 1;
            int rightChild = index * 2 + 2;
            int maxIndex = index;
            // 왼쪽 자식이 존재하며 왼쪽 자식이 현재 루트보다 클 때
            if (leftChild < size && heap[leftChild] > heap[maxIndex]) {
                maxIndex = leftChild;
            }
            // 오른쪽이 제일 크다면 갱신되었을 것
            if (rightChild < size && heap[rightChild] > heap[maxIndex]) {
                maxIndex = rightChild;
            }

            // 부모 인덱스가 제일 큰 경우는 힙 만족이라 조건
            if (maxIndex == index) break;

            int temp = heap[index];
            heap[index] = heap[maxIndex];
            heap[maxIndex] = temp;
            index = maxIndex;
        }
    }

    public static void main(String[] args) {
        BinaryMaxHeap binaryMaxHeap = new BinaryMaxHeap(
                new int[] {
                        1, 21, 14, 6, 10, 2, 5, 6, 8
                }
        );
        while(!binaryMaxHeap.isEmpty()) {
            System.out.println(binaryMaxHeap.remove());
        }
    }
}

이제 힙 구조를 사용해 Heap Sort를 구현해 보자.

import java.util.Arrays;

public class HeapSort {
    public void sort(int[] arr){
        // 배열의 크기를 조사
        int size = arr.length;
        // 전체 배열을 힙의 형태로
        for (int i = 0; i < size / 2 - 1; i++) {
            heapify(arr, size, i);
        }
        // 정렬 안 된 마지막 노드랑 루트 노드를 교환해 가며 남은 원소들을 힙의 형태로 유지
        for (int i = size - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i, 0);
        }
    }

    // 본래 heap의 reHeapDown 연산과 동일한데 그 범위 한정
    // size: heap의 크기 한정
    private void heapify(int[] arr, int size, int index) {
        while(index < size) {
            int leftChild = index * 2 + 1;
            int rightChild = index * 2 + 2;
            int maxIndex = index;
            // 왼쪽 자식이 존재하며 왼쪽 자식이 현재 루트보다 클 때
            if (leftChild < size && arr[leftChild] > arr[maxIndex]) {
                maxIndex = leftChild;
            }
            // 오른쪽이 제일 크다면 갱신되었을 것
            if (rightChild < size && arr[rightChild] > arr[maxIndex]) {
                maxIndex = rightChild;
            }

            // 부모 인덱스가 제일 큰 경우는 힙 만족이라 조건
            if (maxIndex == index) break;

            int temp = arr[index];
            arr[index] = arr[maxIndex];
            arr[maxIndex] = temp;
            index = maxIndex;
        }
    }

    public static void main(String[] args) {
        int[] array = {9, 4, 7, 1, 2, 6, 3};
        new HeapSort().sort(array);
        System.out.println(Arrays.toString(array));
    }
}

Spring Web Socket

WebSocket

푸시나 채팅 알림은 내가 요청을 해야 오는 알림들이 아니다. 서버에서 변동 사항이 있으면 사용자에게 알림을 자동으로 보내 주게 된다. 이런 기능은 HTTP로도 일정한 시간이 지나면 HTTP 요청을 발생시켜서 정보를 얻어낼 수도 있다. 이를 HTTP polling이라고 한다. 그러나 서버 측에서 먼저 응답을 보내는 요청을 발생시키기 위해서는 고민해 볼 부분이 많다. 대표적으로 채팅 기능이 있다.

채팅창에서 내 데이터를 입력하고 서버로 전송하는 것은 일반적인 HTTP 요청과 다를 바 없지만, 상대방의 메시지가 도착하기 위해서 나는 아무 행동을 할 필요가 없다. 따라서 클라이언트와 서버간의 TCP 연결을 길게 유지하고, 서로 양방향으로 데이터를 전달하게 해 주는 통신 규약의 일종이 WebSocket이다. 푸시 알림과 같은 서버 쪽에서 보내 주는 알림은 Server Side Event (SSE)를 사용하기도 한다.

HTTP에 Upgrade라는 헤더를 포함해서 보내는 방식으로 WebSocket을 사용할 것이라고 명시해 준다. 이를 Protocol Handshake라고 한다.

이후 서버에서 사용해도 된다며 100번대 Handshake 응답을 보내고, 웹 소켓을 사용하기 위한 준비 단계에 들어간다.

이후 연결이 종료될 때까지 웹과 서버는 양방향 통신을 하게 된다.

Chat

채팅에 대한 Entity, Dto, Controller를 만들었다면, SimpleChatHandler를 만들어서 TextWebSocketHandler를 상속받아 구현한다. 기존 WebSocketHandler는 데이터를 바이트 형식으로 주고받기 때문에 현재 채팅 기능에서는 String으로 주고받겠다고 설정해 주면 된다.

import lombok.extern.slf4j.Slf4j;
import org.springframework.stereotype.Component;
import org.springframework.web.socket.handler.TextWebSocketHandler;

@Slf4j
@Component
public class SimpleChatHandler extends TextWebSocketHandler {
}

이후 어떤 사용자인지를 판단하는 기준인 WebSocketSession를 매개체로 받는다. 이 객체를 통해 연결된 사용자를 구별할 수 있다. 클라이언트에게 보낼 때도 이 객체를 사용하면 된다. 따라서 이 session 들을 멤버로 가지고 있게 한다. 이후 오버라이드를 통해 afterConnectionEstablished 함수를 구현한다. 연결이 된 이후 최초로 일어날 동작을 구현한다.

@Slf4j
@Component
public class SimpleChatHandler extends TextWebSocketHandler {
    private final List<WebSocketSession> sessions
            = new ArrayList<>();
    @Override
    public void afterConnectionEstablished(
            WebSocketSession session
    ) throws Exception {
        // 방금 참여한 사용자를 저장
        sessions.add(session);
        log.info("connected with session id: {}, total sessions: {}", session.getId(), sessions.size());
    }
}

이후 웹소켓 메시지를 받으면 실행하는 메소드를 오버라이드한다. 메시지를 받는 메소드이다.

		@Override
    protected void handleTextMessage(
            WebSocketSession session,
            TextMessage message) throws Exception {
        String payload = message.getPayload();
        log.info("recieved: {}", payload);
    }

마지막으로 연결이 끝난 이후 최초로 실행할 메소드를 작성해 준다.

		@Override
    public void afterConnectionClosed(
            WebSocketSession session, 
            CloseStatus status) throws Exception {
        log.info("connection with {} closed", session.getId());
        // 더 이상 세션 객첼ㄹ 보유하지 않도록 함
        sessions.remove(session);
    }

SimpleChatHandler 를 구현했으면 이 Handler를 WebSocket 통신에 사용하겠다는 설정을 진행해 준다. 이를 위해서 WebSocketConfigurer 인터페이스를 구현하여, WebSocketHandlerRegistry 에 WebSocketHandler 등록을 진행한다.

@Configuration
@EnableWebSocket
public class WebSocketConfig implements WebSocketConfigurer {
    // TODO @Bean 객체로 SimpleChatHandler 가져오기
    private final SimpleChatHandler simpleChatHandler;

    public WebSocketConfig(SimpleChatHandler simpleChatHandler) {
        this.simpleChatHandler = simpleChatHandler;
    }

    @Override
    // WebSocketHadler 등록을 위한 메소드
    public void registerWebSocketHandlers(WebSocketHandlerRegistry registry) {
        registry.addHandler(simpleChatHandler, "ws/chat")
                .setAllowedOrigins("*");
    }
}

이때 registry에 들어가는 “ws/chat”은 Controller에 들어가는 url이다. 이후 서버를 실행해 보면 메시지가 잘 뜨는 것을 확인할 수 있다.

사용자를 만들어서 시도해 보자.

이후 화면에 다 나오게 코드를 수정하고 브로드캐스트 기능도 넣을 수 있다.

		public void broadcast(String message) throws IOException {
        for (WebSocketSession connected: sessions) {
            connected.sendMessage(new TextMessage(message));
        }
    }

이후 양쪽 사이드에서 모두 메시지가 잘 나오는 것을 확인할 수 있다.

이제 브로드 캐스트 기능을 테스트해 보기 위해 Controller에 매핑을 하나 만들어 준다.

@Controller
@RequestMapping("chat")
@RequiredArgsConstructor
public class ChatController {
    private final SimpleChatHandler simpleChatHandler;
    private final Gson gson;
    @GetMapping("test")
    public @ResponseBody String test() throws IOException {
        simpleChatHandler.broadcast(gson.toJson(
                new ChatMessage(
                        "test", 
                        "test")));
        return "done";
    }
}

이후 실행하면 동시에 메시지가 나가는 것을 알 수 있다.

STOMP over WebSocket

1:1로 연결해서 채팅을 진행하고 싶다면 endpoint가 기하급수적으로 늘어나서 endpoint만으로는 관리가 어렵다. 따라서 from, to, content가 있는 data를 WebSocketSession에 Map 형태로 저장해서 send하는 방법도 있다.

STOMP (Streaming Text Oriented Messaging Protocol)
WebSocket과 같은 데이터를 주고받는 통신 과정에서 데이터가 갖춰야 할 형식을 정의한 규약이다. 한 번의 데이터 전송이 어떻게 생겼는지를 정의한다.

WebSocket과 함께 활용하여 Command, Header, Payload 등 구조를 갖춘 데이터를 주고받는 데 활용된다. 먼저 사용자들이 하나의 WebSocket URL에 접속하고, 이후 보내는 데이터를 STOMP 규칙에 맞게 보낸다. 이 규칙에 따라 어디에 어떤 메타데이터를 보내는지 수신할 수 있다. 특정 세션이 받거나 받지 말아야 할 메시지를 정의하기 편해진다.

WebSocketStompConfig를 만들어 준다.

@Configuration
@EnableWebSocketMessageBroker
public class WebSocketStompConfig implements WebSocketMessageBrokerConfigurer {

    @Override
    public void registerStompEndpoints(StompEndpointRegistry registry) {
        WebSocketMessageBrokerConfigurer.super.registerStompEndpoints(registry);
    }

    @Override
    public void configureMessageBroker(MessageBrokerRegistry registry) {
        WebSocketMessageBrokerConfigurer.super.configureMessageBroker(registry);
    }
}

registerStompEndpoints는 STOMP 엔드포인트 설정용 메소드이다.

@Configuration
@EnableWebSocketMessageBroker
public class WebSocketStompConfig implements WebSocketMessageBrokerConfigurer {

    @Override
    public void registerStompEndpoints(StompEndpointRegistry registry) {
        registry.addEndpoint("/chatting");
    }

    @Override
    public void configureMessageBroker(MessageBrokerRegistry registry) {
        WebSocketMessageBrokerConfigurer.super.configureMessageBroker(registry);
    }
}

configureMessageBroker는 Message를 주고받는 미들웨어를 Message Brocker라고 한다. 따라서 Message Brocker를 사용하는 방법을 설정한다. enableSimpleBroker는 사용자가 받을 데이터를 분류하기 위한 경로이고, setApplicationDestinationPrefixes는 사용자가 보내는 데이터가 도달할 URL이다.

@Configuration
@EnableWebSocketMessageBroker
public class WebSocketStompConfig implements WebSocketMessageBrokerConfigurer {

    @Override
    public void registerStompEndpoints(StompEndpointRegistry registry) {
        registry.addEndpoint("/chatting");
    }

    @Override
    public void configureMessageBroker(MessageBrokerRegistry registry) {
        registry.enableSimpleBroker("/topic");
        registry.setApplicationDestinationPrefixes("/app");
    }
}

이후 socket 핸들러를 controller와 유사하게 만들기 위해 WebSocketMapping을 만들어 준다.

@Slf4j
@Controller
@RequiredArgsConstructor
public class WebSocketMapping {
    // STOMP over WebSocket 요청을 보낼 때 사용하는 용도
    // session에 메시지를 썼던 것처럼
    private final SimpMessagingTemplate simpMessagingTemplate;

    // RequestMapping 에 대응
    @MessageMapping("/chat")
    public void sendChat(ChatMessage chatMessage) {
        log.info(chatMessage.toString());
        String time = new SimpleDateFormat("HH:mm").format(new Date());
        chatMessage.setTime(time);
        simpMessagingTemplate.convertAndSend(
                String.format("/topic/%s", chatMessage.getRoomId()),
                chatMessage
        );
    }
}

채팅방을 여러 개 만들 수 있다.

profile
Huisu
이전 포스트

Techit 13th 3rd

다음 포스트

Techit 13th 5th

0개의 댓글