[백준/BOJ] 1158번 : 요세푸스 문제 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

---

- 문제 -

 

난이도 실버 5 문제이다.

 

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

문제 자체는 복잡하진 않다. 그저 제거된 사람을 세지않고 다음으로 넘어갈지에대한 구현이 좀 까다로웠다.

주어진 값 N과 K.

두개의 정수형 list를 선언해준다.(list1, list2)

list1에 1부터 N까지의 값을 순서대로 저장해준다.

이제 list1에서 K번째 값을 list2로 이동하고, list1에서는 제거해줘야한다. 총 N개의 값이 있기때문에 N번 반복하는 반복문을 만들어주고, list1에서 K번째 값을 list2에 옮겨주고, 제거한다. 하지만 K는 3이지만 실제로 지워져야하는 인덱스 값은 2이다. 그렇기때문에 인덱스값을 지정할 땐 -1을 해준다. 다음 인덱스로 K로 표현할 수가 힘들기 때문에 변수를 하나 선언해서 K값을 저장하고, 반복될때마다 K를 더해준다.

K값을 더하다 보면 인덱스 값이 현재 list1의 최대 인덱스 값을 넘어갈 것이다. 그렇다면 그 인덱스 값에 최대 인덱스 값을 빼주면 원하는 값을 얻을 수 있을 것이다.

매번 반복될 때마다 값은 하나씩 지워질 것이다. 그렇다보면 list1의 길이가 하나씩 줄어들 것이기 때문에 N을 다른 변수에 저장하고, 반복될때마다 -1을 해준다. 그리고 현재 인덱스값의 값이 제거되면 인덱스값은 변하지 않아도 그 자리의 값이 한자리 넘어가 버린다. 그렇기 때문에 K를 더해줄때 -1을 해주고 빼주면 현재 인덱스 값이 유지되는 현상과 같아진다.

그렇게 list2에 요세푸스 수열로 저장되었을 것이다. list2를 그냥 출력하면 []형식으로 출력된다. 하지만 문제에서 원하는 방식은 <>이것이다. 그렇기때문에 <>출력하고 사이에는 0인덱스부터 list2값을 출력해준다.

 

내가 적었지만 이해가 잘 될지 의문이다.  코드로 보자.

 

---

-풀이-

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
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());
		//now = 현재 인덱스 값을 저장할 변수
		//size는 최대 인덱스 값을 저장할 변수
		int now = K;
		int size = N;
		
		List<Integer> list1 = new ArrayList<Integer>();
		List<Integer> list2 = new ArrayList<Integer>();
		
		for(int i = 1; i <= N; i++) {
			list1.add(i);
		}
		
		//해당 인덱스 값을 list1에서 list2로 이동해주고, list1에서는 제거해준다.
		for(int i = 0; i < N; i++) {
			list2.add(list1.get(now - 1));
			list1.remove(now - 1);
			now += (K - 1);
			size--;
			
			if(size != 0) {
				//최댓값보다 현재 값이 커지면, 현재값이 최댓값보다 작아질때까지 최댓값을 빼준다.
				//계속 빼주는 이유는 최댓값은 점점 작아지고, 현재값에 추가되는 값은 같기때문에
				//최댓값이 작아질수록 빼줘야하는 횟수가 늘어날 것이다.
				while(now > size) {
					now -= size;
				}
			}
		}
		//출력.
		System.out.print("<");
		for(int i = 0; i < N; i++) {
			if(i == (N - 1)) System.out.print(list2.get(i) + ">");
			else System.out.print(list2.get(i) + ", ");
		}
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.