[알고리즘] 구현 풀이

Kevin·2025년 4월 11일

백준 자바 10810 백준 자바 1158

Algorithm

목록 보기

9/10

1️⃣ 요세푸스 문제 - 1158

문제

정답

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public void solution() throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        Queue<Integer> queue = new LinkedList<>();
        Queue<Integer> ansQueue = new LinkedList<>();

        for (int i = 1; i < N + 1; i++) {
            queue.add(i);
        }

        int idx = 0;

        while (true) {
            if (queue.isEmpty()) {
                break;
            }

            idx++;

            if (idx == K) {
                ansQueue.add(queue.poll());
                idx = 0;
            } else {
                int num = queue.poll();
                queue.add(num);
            }
        }

        bw.write("<" + String.join(", ", ansQueue.stream().map(String::valueOf).toArray(String[]::new)) + ">" + "\n");

        bw.flush();
        bw.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

해당 문제는 큐 자료구조를 사용할 수 있다.

예를 들어 (6, 6)이라는 값이 주어지고 1, 2, 3, 4, 5, 6 수열이 주어진다고 가정하자.

이 때 1, 2, 3, 4, 5, 6을 담을 큐(queue)를 선언한다.

그리고 6번째인 6을 제거할 때 이를 출력용 큐(ansQueue)에 저장한다.

이 문제에서는 N명의 사람이 원을 이루면서 앉아 있다고 하였다.

6을 제거하고 나서 1, 2, 3, 4, 5가 남았을 것이다.

이 때 6번째를 만들 수 없다 하여 그대로 종료 하는게 아니라 원을 이루며 앉아 있기에 1, 2, 3, 4, 5, 1, 1이 제거 되게 된다.

다른 이들의 코드 풀이 방식

StringBuilder sb = new StringBuilder();
sb.append("<");

// Queue의 사이즈가 1일 때까지 반복한다.
while(q.size() != 1) {
    // K - 1번째까지는 처음에 있던 값을 맨 뒤로 보낸다.
    for (int i = 0; i < K - 1; i++) {
        q.offer(q.poll());
    }
    // K번째 값은 poll한 후 출력한다.
    sb.append(q.poll() + ", ");
}

// Queue의 사이즈가 1일 때는 단순히 poll하면 된다.
sb.append(q.poll() + ">");

bw.write(sb.toString() + "\n");

https://steady-coding.tistory.com/21

StringBuilder를 사용하여 문자열을 만들어내었다.
- 이 방식이 문자열을 만드는데 더 난이도가 쉬운 것 같다.

2️⃣ 공 넣기 - 10810

문제

정답

import java.io.*;
import java.util.*;

public class Main {

    public void solution() throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = 0;
        }

        for (int j = 0; j < M; j++) {
            st = new StringTokenizer(br.readLine(), " ");

            int I = Integer.parseInt(st.nextToken());
            int J = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            for (int k = I - 1; k < J; k++) {
                arr[k] = K;
            }
        }

        bw.write(String.join(" ", Arrays.stream(arr).mapToObj(String::valueOf).toArray(String[]::new)) + "\n");

        bw.flush();
        bw.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}