728x90
1부터 N 까지의 카드 -> List로 생성
0번째를 버림
버리고 나서 제일 위에 있는 거를 제일 끝으로 옮김
size()가 1일 때까지 반복 -> while문으로
그때 남아있는 카드 번호 출력
package algorithm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
List <Integer> list = new ArrayList<>();
for(int i =1;i<=N;i++) { //저장되는 카드번호는 1부터 N까지
list.add(i);
}
while(list.size() != 1) {
list.remove(0); //제일 위에 요소 없애고
list.add(list.size(),list.get(0)); //그다음 젤 위에있는거 젤 뒤로 추가
list.remove(0); //뒤로 추가한 거 제일 앞에서 없앰.
}
System.out.println(list.get(0));
}
}
엄청쉽다 했더니 시간초과가 나왔당 ..ㅋ
add메소드는 해당 index~끝까지의 배열을 arraycopy로 옮겨 자리를 확보하고 , 그 자리에 요소를 삽입하는 식으로 동작한다. 문제에서 input이 최대 50만이라 했으므로, 1개를 제거 - 49만~개를 복사 - 1개를 삽입 같은 작업이 반복해서 일어나게 되고, 시간초과가 발생.
큐를 써보았다 !
그래서 해결 !!
package algorithm;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
LinkedList <Integer> q = new LinkedList<>();
for(int i =1;i<=N;i++) { //저장되는 카드번호는 1부터 N까지
q.add(i);
}
while(q.size() != 1) {
q.poll(); //제일 위에 요소 없애고
q.offer(q.poll()); //그다음 젤 위에있는거 없애고 바로 반환 받아서 젤 뒤로 추가
}
bw.write(Integer.toString(q.peek()));
bw.flush();
bw.close();
}
}
poll() 삭제(맨 앞에서) offer()추가(맨 뒤에)
728x90
'알고리즘 > 백준' 카테고리의 다른 글
2751번 문제 : 수 정렬하기 2 (0) | 2023.03.31 |
---|---|
2609번 문제 : 최대공약수와 최소공배수 (0) | 2023.03.30 |
2108번 문제 : 통계학 (0) | 2023.03.29 |
1966번 문제 : 프린터 큐 (0) | 2023.03.24 |
1929번 문제 : 소수구하기 (0) | 2023.03.22 |