ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [BOJ-JAVA] 1158번: 요세푸스 문제
    Algorithm/Baekjoon Online Judge 2023. 4. 12. 20:48
    728x90

    문제 해결

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

     

    1158번: 요세푸스 문제

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

    www.acmicpc.net

    큐를 이용해 쉽게 구현할 수 있는 문제지만, 초기에는 연결리스트만을 사용하여 구현하였고, 이후에 다시 큐를 사용해 구현하였다.

     

    연결리스트 사용

    • iterator를 사용하여 K번째 마다 remove
    • iterator가 끝을 가르킬 때 다시 정의해줘야 하는 번거로움이 있음
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Iterator;
    import java.util.LinkedList;
    
    public class Main {
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String[] order = br.readLine().split(" ");
            int N = Integer.valueOf(order[0]);
            int K = Integer.valueOf(order[1]);
    
            LinkedList<Integer> queue = new LinkedList<>();
            for(int i=1; i<=N; i++) {
                queue.add(i);
            }
            StringBuilder sb = new StringBuilder();
            sb.append("<");
            Iterator iterator = queue.listIterator();
            int count = 1;
            while(!queue.isEmpty()){
                int num = (int)iterator.next();
                if(count == K) {
                    sb.append(num).append(", ");
                    iterator.remove();
                    count = 1;
                }
                else {
                    count++;
                }
                if(!iterator.hasNext()){
                    iterator = queue.listIterator();
                }
            }
            sb.replace(sb.length()-2, sb.length(), ">");
            System.out.println(sb);
        }
    }

     

    큐 사용

    • 큐는 연결리스트를 사용하여 구현
    • K번째가 아니라면 꺼내서 뒤로 보내고, 맞다면 꺼내는 방식
    • 코드가 훨씬 간단해짐 
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class boj_1158 {
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String[] order = br.readLine().split(" ");
            int N = Integer.valueOf(order[0]);
            int K = Integer.valueOf(order[1]);
    
            Queue<Integer> queue = new LinkedList<>();
            for(int i=1; i<=N; i++) {
                queue.offer(i);
            }
            StringBuilder sb = new StringBuilder();
            sb.append("<");
            int count = 1;
            while(queue.size() != 1){
                if(count == K) {
                    sb.append(queue.poll()).append(", ");
                    count = 1;
                }
                else {
                    queue.offer(queue.poll());
                    count++;
                }
            }
            sb.append(queue.poll()).append(">");
            System.out.println(sb);
        }
    }

     

    메모리, 시간 차이

    연결리스트

    • 큐를 사용했을 때 코드 길이 감소
    • 큐를 사용했을 때 시간과 메모리 증가
      • 메모리의 경우 똑같이 linkedlist를 사용하지만 큐는 offer, poll의 반복이기 때문인듯
      • 시간의 경우 연결리스트의 iterator를 사용하면 시간 감소 
    728x90

    'Algorithm > Baekjoon Online Judge' 카테고리의 다른 글

    [BOJ-JAVA] 17298번: 오큰수  (0) 2023.04.17
    [BOJ-JAVA] 10799번: 쇠막대기  (0) 2023.04.17
    [BOJ-JAVA] 1406번: 에디터  (0) 2023.04.07
    [BOJ-JAVA] 10828번: 스택  (0) 2023.04.06
    [BOJ] 10986번: 나머지 합  (0) 2022.04.27

    댓글

Designed by Tistory.