아래의 코드로 문제를 해결했습니다. 큐를 이용하여
이클립스로 문제를 돌려보니 답안이 맞는걸 확인할수 있었습니다.
시간초과로 답이 맞는지 확인을 못했는데 시간을 단축시킬수 있는 방법이 있을까요 ? 제 생각에 이문제를 푸는데 큐를 이용하는 것이
최적의 방법이라 생각되었습니다.
import java.util.Scanner;
public class jose {
static int array[] = new int[1000];
public static void function(int N, int K) {
for (int i = 0; i < N; i++) {
array[i] = i + 1;
}
deque();
while (!check()) {
for (int i = 0; i < K; i++) {
if (i == K - 1) {
deque();
break;
}
int num = deque();
inque(num);
}
}
sort();
System.out.print(array[0]+" "+array[1]);
}
public static int deque() {
int num = array[0];
for (int i = 1; i < array.length; i++) {
array[i - 1] = array[i];
if (array[i] == 0)
break;
}
return num;
}
public static void sort(){
for(int i=0;i<array.length-1;i++){
for(int j=1;j<array.length;j++){
if(array[i]>array[j]&&array[j]!=0){
int temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
}
}
public static void inque(int num) {
for (int i = 0; i < array.length; i++) {
if (array[i] == 0) {
array[i] = num;
break;
}
}
}
public static boolean check() {
for (int i = 0; i < array.length; i++) {
if (array[i] == 0) {
if (i == 2) {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int testcase = scan.nextInt();
for (int i = 0; i < testcase; i++) {
int N = scan.nextInt();
int K = scan.nextInt();
function(N,K);
}
}
소팅은 마지막에 어짜피 2개 남으니 상관없다고 해도
인큐랑 디큐가 너무 느리네요
앞부터 빈 곳 까지 찾아서 푸시하고
맨 앞꺼 팝하고 하나씩 땡기는 것보다
head인덱스랑 tail인덱스 저장해서 인덱스를 옮기는 방법으로 큐를 관리하면 어떨까 싶네용
O(N^2*K)->O(NK)
qkrqudwn
아래의 코드로 문제를 해결했습니다. 큐를 이용하여
이클립스로 문제를 돌려보니 답안이 맞는걸 확인할수 있었습니다.
시간초과로 답이 맞는지 확인을 못했는데 시간을 단축시킬수 있는 방법이 있을까요 ? 제 생각에 이문제를 푸는데 큐를 이용하는 것이
최적의 방법이라 생각되었습니다.
import java.util.Scanner;
public class jose {
static int array[] = new int[1000];
}
8년 전