메뉴 닫기

[BOJ] 1158 요세푸스 문제

1158번: 요세푸스 문제 (acmicpc.net)

배열 -> 다시 결국 큐

처음에 배열을 이용해서 접근 인덱스를 변경하는 방식으로 문제를 풀려다가, 조건문이 너무 복잡해지고, 메모리도 배열을 이어붙이거나 반복문을 하려면 낭비된다고 생각되어서 다시 큐를 이용해서 풀었다.

  1. 큐에 1부터 N 까지 값을 입력
  2. 큐가 빌때까지 하나씩 빼서 값을 잠시 저장
  3. 몇 번째로 꺼냈는지 확인
    1. 이번에 뺀게 k 번째이면 다시 넣지 않고 StringBuilder에 저장
    2. 이번에 뺀게 k 번째가 아니면 다시 큐에 넣기
  4. 2번으로 반복 (큐가 비어있으면 종료된다)
  5. StringBuilder로 출력
package com.algo.boj;

import java.util.LinkedList;
import java.util.Scanner;

public class BOJ1158Josephs {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder("<");
		int N = sc.nextInt();
		int k = sc.nextInt();
		LinkedList<Integer> q = new LinkedList<>();
		for (int i = 1; i <= N; i++) {
			q.offer(i);
		}
		int index=0;
		while(!q.isEmpty()) {//큐가 빌때까지
			index++;
			int save = q.poll();
			if(index%k == 0) {//다시 넣지 않고 출력에 저장
				sb.append(save).append(", ");
			}else {//차례가 아니면
			q.offer(save);
			}
		}
		sb.setLength(sb.length()-2);//마지막 공백과 컴마 제거
		sb.append(">");
		System.out.println(sb);
	}

}

새롭게 알게된점

나는 13번 줄에서 Queue객체로 선언하지 않고 그냥 LinkedList를 그대로 가져왔다.
어짜피 LinkedList객체를 생성하는거기 때문에 Queue 타입으로 LinkedList를 사용하나 LinkedList타입으로 사용하나 메모리상의 차이는 없다.
그런데 나중에 코드 유지보수관점에서 LinkedList가 아니라 다른 구현체가 오게 될 수있는데, 그렇게 되면 앞에 타입도 이에 맞게 수정해줘야 하기 때문에 Queue의 기능을 쓸 때는 Queue 타입으로 설정해 놓는 게 좋다. 또한 Queue 타입으로 선언하면 Queue의 메소드만 사용할 수 있도록 LinkedList의 메소드가 한정된다.

Related Posts

답글 남기기

이메일 주소는 공개되지 않습니다.

%d 블로거가 이것을 좋아합니다: