[구현] 11866 요세푸스 문제 0

요세푸스 순열이 대체 무슨 규칙으로 정해지는 지 감도 안잡혔음.

맨처음에는 N을 기준으로 양 끝의 수를 더해서 N이 되도록해야하나?

예를 들어서 <3, 6, 2, 7, 5, 1, 4> 이면 3+4 = 7, 6+1 = 7, 2+5 = 7 

했는데 그러면 3, 6, 2  이 순서는 어떻게 만들어질지 모름.

 

문제를 잘 보면 " 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다."이게 포인트였던 거 같다.

한 사람이 제거되면 제거된 사람을 제외한 새로운 길이를 기준으로 삭제할 사람을 찾아내야 했다.

 

풀이과정

 

1. 입력으로 주어진 k의 인덱스가 어디있는 지 찾는다.

2. 제거한 사람의 인덱스를 새로운 배열에 저장하고 기존 리스트에서는 삭제.

3. k번째 사람이 제거된 리스트의 길이로 재조정하고, (기존 배열에서의 k번째 사람의 인덱스) + (k-1) 을 해서 다음으로 제거될 사람의 인덱스를 찾아야하는데, 다음으로 제거될 사람의 인덱스가 길이가 재조정된 리스트의 길이보다 길면 나머지로 결정 -> (기존 배열에서의 k번째 사람의 인덱스) + (k-1) % (길이가 재조정된 리스트의 길이)

 

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

public class Main {
  public static void main(String[] args) throws IOException {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    List<Integer> data = new ArrayList<Integer>();
    for (int i=0; i<n; i++){
      data.add(i+1);
    }
    int idx = data.indexOf(Integer.valueOf(k));

    String[] result = new String[n];
    for (int i=0; i<n; i++) {
      result[i] = String.valueOf(data.get(idx));
      data.remove(idx);
      if(data.size() == 0) {
        break;
      }
      idx = (idx + (k-1)) % data.size();
    }
    String r = String.join(", ", result);
    System.out.print("<"+r+">");
  }
  
}

 

---

알게 된 것

자바에서 리스트를 구분자로 이어 String으로 만들기

String.join("구분자", String[]);

 

String r = String.join(", ", result);

 

큐를 이용한 풀이

• https://st-lab.tistory.com/197

import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
 
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		Queue<Integer> q = new LinkedList<>();
		
		int N = in.nextInt();
		int K = in.nextInt();
		
		
		for(int i = 1; i <= N; i++) {
			q.add(i);
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append('<');
		
		/*
		 *  마지막 부분의 출력은 > 괄호 전에 공백이 없기 때문에
		 *  일괄적으로 출력하기 위해 마지막 원소만 남겨질 때까지만
		 *  반복하고 마지막 원소는 그대로 출력한다.
		 */
		while(q.size() > 1) {
			
			for(int i = 0; i < K - 1; i++) {
				int val = q.poll();
				q.offer(val);
			}
			
			sb.append(q.poll()).append(", ");
		}
 
		// 마지막 원소 출력한 뒤 > 도 붙여준다.
		sb.append(q.poll()).append('>');
		System.out.println(sb);
	}
 
}

 

큐 사용 법

import java.util.Queue;

import java.util.LinkedList;

 

Queue<자료형> 변수명 = new LinkedList<>(); //자료형에 넣은 자료형만 삽입, 삭제 가능
Queue 변수명 = new LinkedList(); //어떤 자료형이든 삽입, 삭제 가능

Queue<자료형> q = new LinkedList<>();

 

1. 삽입

add

: 반환 값: 삽입 성공 시 true / 실패 시 Exception 발생

q.add(value);

 

offer

: 반환 값: 삽입 성공 시 true / 실패 시 false

q.offer(value);

 

2. 삭제

remove

: 반환값: 삭제된 value / 공백 큐이면 exception

 

remove(value)

: 반환값: 큐에 해당 value가 존재하면 해당 값 삭제 후 ture / 존재하지 않으면 false

 

poll

: 반환값: 삭제된 value / 공백 큐이면 null 반환.

 

StringBuilder

https://onlyfor-me-blog.tistory.com/317

public class Main
{
    public static void main(String[] args)
    {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("문자열 ").append("연결");
//        String str = stringBuilder;   // String에 StringBuilder를 그대로 넣을 순 없다. toString()을 붙여야 한다
        String str = stringBuilder.toString();
        // 두 println()은 같은 값을 출력한다
        System.out.println(stringBuilder);
        System.out.println(str);
    }

}

---

참고 자료

• https://st-lab.tistory.com/197
• https://beginnerdeveloper-lit.tistory.com/128