글 읽기 - 요세푸스 문제 2 시간초과

rlaskdus4713 3년 전 0

이클립스에서 컴파일 했을땐 정답이 잘 나오는데 시간초과가 떠요. 왜 그러는걸까요?ㅜㅜ

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class 요세푸스문제2 {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		List<Integer> list = new ArrayList<>();
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		int count = k;
		int m = 0;
		int[] ans = new int[n];
		for(int i=1;i<=n;i++) {
			list.add(i-1,i);
		}
		
		while(!list.isEmpty()) {
			if(count == 1) {
				ans[m++] = list.remove(0);
				count = k;
			}else {
				count--;
				int last = list.remove(0);
				list.add(list.size(), last);
			}
		}
		
		int len = n;
		
		System.out.print("<");
		for(int an : ans) {
			if(len == 1) {
				System.out.print(an);
			}else
				System.out.print(an + ", ");
			len--;
		}
		System.out.print(">");
	}
}

gi5005 3년 전 1

list.remove 함수가 시간복잡도가 n이기때문에 코드의 시간복잡도가 N^2 가 되어서 시간초과가 나는걸로 보입니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

요세푸스 문제 2 시간초과

rlaskdus4713 3년 전 0

gi5005 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말