백준 11866번: 요세푸스 문제 0 with Java

요세푸스 문제 0

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

96764

55409

46404

56.813%

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입력 1 복사

7 3

예제 출력 1 복사

<3, 6, 2, 7, 5, 1, 4>

 

 

---

 

스택 하나 더 하려다가... 

그래도 공부를 해야 하니까 큐 문제를 골랐다.

큐....

이거 풀고 큐도 좀 찾아봐야겠다.

-> 이거 풀려다가 큐 문제로 선회했엇지만 지금 너무 문제 날먹한 것 같아서 다시 풀러왓쪄염 뿌우

 

근데 What is 요세푸스???????

 

1. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고 

2. 순서대로 K번째 사람을 제거한다.

3. 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다..

4. N명의 사람이 모두 제거될 때까지...

 

7과 3을 입력받았을 때

1234567 애들이 생긴다

여기서 3번째인 3 제거

124567 6 제거(4부터 세서 3번째)

12457 2 제거

이런 식으로... 해서 전부 제거하는 것

그 담에 제거한 애들 출력하기

 

linkedList인데 끝에 꺼가 null 말고 맨 첫 번째거 가리키는.. 그런 걸로 구현해야겟는데??

이걸 자바로 어케 구현함...

 

글 쓰면서 메소드 찾아보다가 다시 한 번 뜬금없이 정리해보는 add와 offer 차이.. 

https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html

Queue (Java Platform SE 8 )

 

add, remove, element->  던져버려서 exception 발생

offer, poll, peek -> true, false 반환

 

공부할 때야 이것저것 써보는 게 맞지만 구현할 때는 offer poll peek으로 쓰는 게 안전하겠다. 이건 덱도 마찬가지!!

 

 

아 이거 걍 1, 2, 3, 4, 5, 6, 7 있을 때 3을 poll 해서 그 스트링빌더에다 더해주고 4567 뒤에 12를 갖다붙이고 계속.. 하믄 되지 않을까? 길이가 1 되면 while 문 탈출하고

 

근데 지금 쓰다보니 이중 반복문이 되는데 이거 괜찮나...

일단 돌려본다..

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    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()); 
        int K = Integer.parseInt(st.nextToken()); 
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= 7; i++) {
            queue.offer(i);
        }

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

        while (queue.size() > 1) {
            for (int i = 0; i < K - 1; i++) {
                queue.offer(queue.poll());
            }

            sb.append(queue.poll());
            sb.append(", ");
        }

        sb.append(queue.poll());
        sb.append(">");

        System.out.println(sb);
    }
}

 

 

한 번에 돌아가는 법이 없네 어떻게..

왜 컴파일 에러지???

아 아주 기초적인 오류... 마이컴파일러로 코드 짜다보니까 실수로 import java.util.StringTokenizer;  이거 import 문 안 써줬다 ㅎㅎ

추가하고 돌렸더니....

 

 

이젠 틀렸다!!!!!!!!

왜!!!!!!!!!!!!!!!!

 

아 나 바보인가??

7....7 생각하다가 for문을 N 말고 7로 돌렸다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer; 

public class Main {
    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()); 
        int K = Integer.parseInt(st.nextToken()); 
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            queue.offer(i);
        }

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

        while (queue.size() > 1) {
            for (int i = 0; i < K - 1; i++) {
                queue.offer(queue.poll());
            }

            sb.append(queue.poll());
            sb.append(", ");
        }

        sb.append(queue.poll());
        sb.append(">");

        System.out.println(sb);
    }
}

 

고치고 돌리니까

 

 

키키 성공이다!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer; 

public class Main {
    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()); // 사람 수
        int K = Integer.parseInt(st.nextToken()); // 제거할 번호
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            queue.offer(i);
        } // offer로 큐 만들어주기

        StringBuilder sb = new StringBuilder(); // 덧붙여서 한 번에 출력해주려고 만듦
		sb.append("<"); // 출력 조건 맞추기

        while (queue.size() > 1) {
            for (int i = 0; i < K - 1; i++) {
                queue.offer(queue.poll());
            } // 제거할 번호 전까지 뽑아서 queue 맨 뒤로 보내기

            sb.append(queue.poll());
            sb.append(", ");
        } // 큐 길이 1 되면 탈출 while문 제거당한 애를 sb에 더해주고 조건에 맞게 반점도 찍어준다 

        sb.append(queue.poll()); // 큐에 하나 남은 애 뽑아서 sb에 더해주기
        sb.append(">"); // 출력 조건 맞추기

        System.out.println(sb); // 출력
    }
}

 

올만에 주석도 더해보았다. 굿

 

 

발표용 큐 개념 추가

 

 

🔄 큐의 기본 개념

• 선입선출(FIFO: First In, First Out) 방식입니다.
  • 먼저 들어간 데이터가 먼저 나옵니다.
  • 마치 줄 서는 것과 같아요. 먼저 줄 선 사람이 먼저 처리되는 거죠.

🧱 큐의 주요 동작

1. enqueue: 큐의 뒤쪽(Rear)에 데이터를 추가
2. dequeue: 큐의 앞쪽(Front)에서 데이터를 제거
3. peek / front: 큐의 맨 앞에 있는 데이터를 확인만 함 (제거하지 않음)
4. isEmpty: 큐가 비어 있는지 확인

📦 큐를 사용하는 예

• 프린터 작업 순서
• 콜센터 고객 대기
• BFS(너비 우선 탐색) 알고리즘
• CPU 태스크 스케줄링

 

 

LinkedList는 자바에서 연결 리스트를 구현한 클래스예요. 연결 리스트는 각 요소가 다음 요소를 가리키는 방식으로 데이터를 저장하는 자료구조입니다. 배열과 달리, 데이터를 저장하는 위치가 연속적이지 않고 각 요소가 독립적으로 존재하면서 포인터(또는 참조)로 서로 연결돼 있어요.

자바에서는 java.util.LinkedList 클래스가 이를 구현하고 있으며, List, Queue, Deque 인터페이스를 구현하고 있어서, 다양한 방식으로 활용할 수 있어요.

---

🔸 LinkedList의 구조

연결 리스트의 기본 개념은 각각의 요소가 데이터와 포인터(다음 요소를 가리키는)를 가지고 있다는 점이에요. 연결 리스트는 크게 **단일 연결 리스트(Singly Linked List)**와 **이중 연결 리스트(Doubly Linked List)**로 나뉘는데, 자바의 LinkedList는 이중 연결 리스트입니다.

이중 연결 리스트는 각 노드가 두 개의 포인터를 가지며:

• 앞쪽(previous) 포인터는 이전 노드를 가리키고,
• 뒤쪽(next) 포인터는 다음 노드를 가리킵니다.

🔸 LinkedList의 장점

1. 동적 크기 조정: 배열은 크기가 고정되어 있지만, 연결 리스트는 크기가 동적으로 변경될 수 있어요. 요소를 추가하거나 제거할 때 크기를 조정하는 데 시간이 걸리지 않아요.
2. 삽입 및 삭제 효율적: 배열과 달리 삽입이나 삭제가 효율적이에요. 중간에 요소를 추가하거나 제거할 때, 다른 요소들을 이동시킬 필요 없이, 포인터만 수정하면 되니까요.
3. 메모리 절약: 배열처럼 미리 메모리를 할당할 필요가 없기 때문에 메모리를 절약할 수 있어요.

🔸 LinkedList의 단점

1. 임의 접근 불가: 배열처럼 인덱스로 바로 접근할 수 없어요. 데이터에 접근하려면 처음부터 끝까지 순차적으로 접근해야 해서 검색에 시간이 걸릴 수 있어요.
2. 추가적인 메모리 사용: 각 노드는 데이터 + 두 개의 포인터(이전 노드와 다음 노드)를 가지고 있어 메모리 사용이 비교적 큽니다.

 

Queue 인터페이스 메서드

• add(E e): 큐의 맨 뒤에 요소를 추가합니다. 큐가 꽉 차있다면 IllegalStateException이 발생합니다.
• offer(E e): 큐의 맨 뒤에 요소를 추가합니다. 큐가 꽉 차면 false를 반환하고 예외는 발생하지 않습니다.
• remove(): 큐의 맨 앞에서 요소를 제거하고 반환합니다. 큐가 비어있다면 NoSuchElementException이 발생합니다.
• poll(): 큐의 맨 앞에서 요소를 제거하고 반환합니다. 큐가 비어있으면 null을 반환합니다.
• element(): 큐의 맨 앞에 있는 요소를 반환합니다. 큐가 비어있으면 NoSuchElementException이 발생합니다.
• peek(): 큐의 맨 앞에 있는 요소를 반환합니다. 큐가 비어있으면 null을 반환합니다.
• size(): 큐에 저장된 요소의 개수를 반환합니다.
• isEmpty(): 큐가 비어있는지 여부를 확인합니다. 비어있으면 true, 아니면 false를 반환합니다.