04.15 오늘의 알고리즘 문제(1158: 요세푸스 문제)

안녕하세요! 거의 1주일만에 찾아 뵙는 오늘의 알고리즘 시간입니다!

 

요 최근에 계속 SQLD 공부 하랴, 새로 듣는 Java 강의가 있어서 그거 듣느랴

 

그러다보니 알고리즘 업로드를 잘 하지 못했네요 ㅜ.ㅜ 

 

죄송하다는 마음을 가득 담고 앞으로는 정해진 기간에 알고리즘 꾸준히 올리는 걸로.....

 

오늘 알고리즘 풀이로 가져온 문제는

 

백준 코드 1158번 문제인 [요세푸스 문제] 입니다!

 

 

문제

그래도 저번 문제보다는 이해가 쉽다.

입출력으로 보는것이 좋긴 하다

당장 처음에 보면은 문제가 무엇을 말하는지 모르실수도 있다는 생각이 들 수도 있습니다.

 

왜냐구요???

.....

 

.....

 

.....

 

이 문제 풀 때 제가 그랬어서..........ㅎ

저는 이해하는 머리가 안좋은가봐요....ㅎㅎ

 

설명

근데 사실 자세히 읽어보면 제가 저번에 업로드 했던 문제 보다는 이해하기 쉬운 내용입니다.

 

간단하게 설명을 해드리자면 

 

예를 들어 위의 입력 예제와 같이 N이 7이고 K가 3라고 가정을 하면은

 

총 7명이 원을 이루어 앉아 있고 1부터 시작해서 3번째 사람을 빼버린다는 뜻이 됩니다.

 

그러면 최초에 3번째 사람이 빠졌으므로 남은 사람은 1,2,4,5,6,7이 되겠죠?

 

이제 이렇게 되면 다음 순서는 3번이 빠졌기 때문에

 

빠진 3번을 처음(최초의 1번이 되겠죠?)으로 기준을 잡고

 

그 다음 3번째는 6번째 사람이기 때문에

 

남는 사람은 1,2,4,5,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 Algo1158 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer Token = new StringTokenizer(br.readLine());
		int Input = Integer.parseInt(Token.nextToken());
		int Remove = Integer.parseInt(Token.nextToken());
		Queue<Integer> List = new LinkedList<>();
		StringBuilder Sb = new StringBuilder();
		
		Sb.append("<");

		for (int i = 1; i <= Input; i++) {
			List.offer(i);
		}
		while (List.size() != 1) {
			for (int i = 0; i < Remove - 1; i++) {
				List.offer(List.poll());
			}
			Sb.append(List.poll() + ", ");
		}
		Sb.append(List.poll() + ">");
		System.out.println(Sb);
	}

}

우선적으로 이 코드를 이해하시려면 기본적으로 큐 메소드를 알고 있다는 가정 하에

 

offer와 poll에 대한 이해가 필요합니다.

 

offer는 어찌 보면은 어떤 것을 추가한다는 점에서 add랑 같은 개념인데요.

 

단지 다른 점이라고 하면 offer는 문제 발생시 null 혹은 false를 리턴 한다는 차이고

 

add는 예외를 발생 시킨다는 차이입니다. 크게 다를 것은 없어요!!

 

poll 역시 remove와 같은 개념이지만 null 혹은 false를 리턴한다는건 동일합니다.

 

 설명은 간단히 이정도로 드리고 문제에 대한 대략적인 풀이를 말씀 드리자면

 

최초에 Input으로 값을 입력 받으면 1부터 입력값을 큐에 집어넣습니다.

 

그다음 Remove로 입력 받은 값의 위치에 있는 숫자를 알아야 되기 때문에

 

입력 값의 -1번째 까지의 처음에 오는 값은 맨뒤로 보내버립니다.

 

그러다 보면 K번째 값이 잡히게 될 것이고 이 값을 큐에서 poll로 제거 하여 출력 시킵니다.

 

이 과정을 큐에 값이 1개 남을 때 까지 반복합니다.

 

그러면 큐에 남는 1개는 어떻게 빼냐는 의문이 생길 수도 있는데

 

단순히 그냥 하나 남은 값을 빼줘서 출력 시켜버리면 되기 때문에

 

그렇게 어려운 과정은 아닙니다.

 

풀이 후 느낀 점

영문을 알 수가 없었다....그런데.....

처음에 풀이를 하고 나서 틀렸을 때는 어딘가 코드가 잘못된건가 싶어서

 

다시 제대로 수정을 하고 제출을 했는데 또 틀렸다고 나오더라구요....

 

근데 이게 알고 봤더니 출력 과정에서 

 

<3, 6, 2, 7, 5, 1, 4> <-- 이렇게 출력 되야 하는게

 

띄어쓰기를 한 칸 더 해버려서

 

<3 , 6 , 2 , 7 , 5 , 1 , 4> <-- 이렇게 출력이 되서 틀렸던 것이더라구요....

 

 

에헤헤헤헤헤.....바보다 바보야

네 이로써 다시한번 바보 같은 짓을 했다는 것이 밝혀져 세간의 충격을........

 

다행히도 코드가 틀린건 아니었다는건 다행이라는 생각을 하면서....

 

오늘의 알고리즘을 마칩니다......