티스토리 뷰

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

 


링크

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

 

11866번: 요세푸스 문제 0

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

www.acmicpc.net

문제

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

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)

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

 

접근방법

 현재 위치에서 K 만큼 떨어진 사람을 빼면서, 모든 사람들을 자리에서 빼는 문제이다. 원형 테이블이기 때문에 현재 위치를 기준으로 k만큼 떨어졌을 때, 순환될 수 있다. 배열에 사람들을 넣었을 때, ' 요구사항에 맞게 잘 순환시켜서, 사람을 빼낼 수 있는가?'에 대한 문제라고 생각한다. 그럼 이 정도 생각을 가지고 풀이에 임하자.

 

풀이

 사실 이 문제를 처음봤을 때, 연결 리스트 하나면 되겠네!라는 생각이 먼저 들었다. (연결 리스트에 대한 내용은 나중에 포스팅하겠다.) 테일 노드를 헤드 노드와 이어 원형 리스트를 만들면, 노드 포인터 하나 만들어서 리스트가 빌 때까지 나는 밀기만 하면 된다. 그러나 하지 않은 이유는 두 가지가 있다.

 

  1. 목적성에 어긋남 - 코딩테스트에서 내가 원하는 연결 리스트를 만들어 쓰기엔, 비효율적이다.

  2. hasNext() 메소드를 k번씩 호출해서 빼야 한다. 시간 초과의 위험이 충분히 있다.

 

 위과 같은 이유로 배열인 ArrayList를 사용하여 풀기로 했다. 문제를 한번 그려보자. 문제의 예시인 N= 7 , K =3인 상황을 보자.

 

   

 기준점을 두고, 해당 기준점으로 부터 3번째인 2번 인덱스가 먼저 빠지고, 그 자리를 당겨서 채우게 된다. 여기까진 문제가 없다. 다음 상황을 보자.

 

 기준점인 4번 인덱스에서 3번쨰 앞에 있는 수는 배열상에는 존재하지 않는다. 하지만 원형이므로, 제시한 정의대로라면, 1번 인덱스가 나와야 한다. 그러므로 논리적으로 이 배열을 원형으로 연결해주는 작업이 필요하다.

 

방법은 어렵지 않다. index에서 x번째 인덱스가 배열의 길이를 초과한다면, 배열의 길이 만큼 잘라주면 된다. 

		//인덱서가 현재 원탁 사람수를 초과한다면,원형으므로 순환하게됨
		//순환이 끝날때까지 뺀다
	            while (indexor >= cur_len){
	                indexor-=cur_len;
	            }

 

코드 

두 가지 코드를 제시한다.

1. Scanner 사용

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Main test =new Main();
    }

    public Main(){
        Scanner sc =new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] answers = solution(N,K);

        System.out.print("<");
        for (int i = 0 ; i < N ; i++){
            System.out.print(answers[i]);
            if(i !=N-1) {
                System.out.print(", ");
            }

        }
        System.out.println(">");
    }

    public int[] solution (int N, int K){
        int indexor = 0;
        int k =0;
        int[] results = new int[N];
        ArrayList<Integer> datas = new ArrayList<>();

        for (int i = 0 ; i <N; i++){
            datas.add(i+1);
        }

        int cur_len = datas.size();

        while (cur_len>0){
            indexor+=(K-1);

            while (indexor >= cur_len){
                indexor-=cur_len;
            }


            results[k++]= datas.remove(indexor);

            cur_len -=1;


        }

        return results;
    }
}

2. BufferedReader, 나머지를 이용하여 index 순환

 while문의 목적은 문제 정의대로 인원수를 감소시킬 때, 배열의 크기도 줄기 때문에, 여러번 도는 경우가 생기는 것을 막기 위함이다. 다시 생각해보면, 최대 범위보다 작을 때까지 계속 빼는 과정을 진행하므로, 나머지와 같다. 그러므로 나머지 연산자를 이용하여 다시 제출하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

    public static void main(String[] args) throws IOException {
        Main test =new Main();
    }

    public Main() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();


        String[] data = br.readLine().split(" ");
        int N = Integer.parseInt(data[0]);
        int K = Integer.parseInt(data[1]);
        int[] answers = solution(N,K);



        //출력형식
        sb.append("<");
        for (int i = 0 ; i < N ; i++){
            sb.append(answers[i]);
            if(i !=N-1) {
                sb.append(", ");
            }

        }
        sb.append(">");
        System.out.println(sb);
    }

    public int[] solution (int N, int K){

        //결과 값에 저장할 위치 저장용 인덱서, 결과값 저장배열
        int k =0;
        int[] results = new int[N];


        // ArrayList의 현재위치를 기억할 인덱서, 원탁테이블 리스트
        int indexor = 0;
        ArrayList<Integer> circle_table = new ArrayList<>();
        //초기화
        for (int i = 0 ; i <N; i++){
            circle_table.add(i+1);
        }

        //현재 원탁에 앉은 사람 수
        int cur_len = circle_table.size();

        //모든 인원이 빠질때까지 요세푸스 로직 수행
        while (cur_len>0){
            //현재위치로 부터 k번째인 사람
            indexor+=(K-1);

//            //인덱서가 현재 원탁 사람수를 초과한다면,원형으므로 순환하게됨
//            //순환이 끝날때까지 뺀다
//            while (indexor >= cur_len){
//                indexor-=cur_len;
//            }
            if(indexor >= cur_len){
                indexor%=cur_len;
            }

            
            //빠진 인원을 결과 배열에 저장
            results[k++]= circle_table.remove(indexor);

            //원탁 인원수 줄임
            cur_len -=1;
            
        }

        return results;
    }
}

 

결과

 

32646087 -BufferedReader, StringBuilder

32645250 -Scanner

 

 


포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다. 

댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
글 보관함