728x90
반응형
<문제 링크>
https://www.acmicpc.net/problem/1158
1158번: 요세푸스 문제
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
www.acmicpc.net
<풀이>
1부터 N까지의 수를 가진 리스트가 있는데 K 씩 증가하는 인덱스에 있는 사람들을 제거하여 그 순서대로 출력하면 되는 문제이다. K번째 자리 사람을 제거하면 리스트가 줄어들기 때문에 가변형 배열인 list를 사용했다.
현재 삭제할 인덱스 변수를 선언해 리스트에서 현재 인덱스에 있는 요소를 삭제해 제거된 사람이 모여 있는 변수에 저장하면 된다.
그래서 현재 삭제할 인덱스는 K번째 커지지만, 리스트 검색 범위를 넘어가면 안 되기 때문에 리스트로 나누었을 때 나머지가 현재 인덱스라는 걸 의미하도록 했다.
<코드>
JAVA
arr: 사람이 원을 이루면서 앉아 있는 리스트
result: 제거된 사람을 문자열로 추가하여 저장
j: K씩 변화하는 인덱스
PYTHON
people: 사람이 원을 이루면서 앉아 있는 리스트
result: 제거된 사람을 저장하는 리스트
index: K씩 변화하는 인덱스
JAVA
import java.util.ArrayList;
import java.util.Scanner;
public class B1158 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
ArrayList<Integer> arr = new ArrayList<>();
String result = "";
// arr init
for(int i = 1; i <= N; i++){
arr.add(i);
}
int j = -1;
for(int i = 0; i < N; i++){
j = (j + K) % arr.size(); // K만큼 jumping
result += arr.get(j); // 제거한 순서대로 출력
if(i != N-1){ // format print
result += ", ";
}
arr.remove(j); // 값 제거
j -= 1; // 길이도 줄었으니 인덱스도 -1
}
System.out.println("<" + result + ">");
sc.close();
}
}
PYTHON
n, k = map(int, input().split())
people = [i for i in range(1, n+1)] # init
results = []
index = 0
while len(people) > 0:
index = (index + (k-1)) % len(people) # jumping
results.append(str(people.pop(index))) # remove
print("<%s>" %", ".join(results)) # format
728x90
반응형
'~2023' 카테고리의 다른 글
| [Python] 백준 2178번 문제, 미로 탐색 (0) | 2021.07.04 |
|---|---|
| [JAVA] 백준 17478번 문제, 재귀함수가 뭔가요? (0) | 2021.07.04 |
| [JAVA] 백준 2822번 문제, 점수 계산 (0) | 2021.06.25 |
| [JAVA/PYTHON3] 백준 7568번 문제 - 덩치 비교하기 (0) | 2021.06.25 |
| [MySQL] MySQL 8.0에서 스키마, 테이블 구조 보기 (0) | 2021.06.22 |