백준 자바 1158 알고리즘 '요세푸스 문제' 문제풀이





코드를 보다보니 어느새 새벽이 되었네요.

새벽에 우는 귀뚜라미? 소리를 들으며 가을의 바람을 느껴봅니다

선선한 바람을 맞으며 푸는 코드

링크드리스트(Linked List) 문제를 배열없이 Linked List를 이용해 풀었습니다.

원형 링크드리스트(Circular Linked List) 문제입니다.




코드 설명

코드만 봐도 쉽게 이해 할수 있게 객체 지향적으로 작성되었으며

코드 사용시 출처 링크를 남겨주시면 감사하겠습니다.





백준 1158번 문제 링크

More info: 요세푸스 문제





자바는 여기서 배웠습니다

More info: 유데미 강좌(영어)/자바강의





링크드리스트 및 자료구조의 경우 아래에서 배웠습니다

More info: 유데미 강좌(영어)/자바자료구조 알고리즘




간단한 노트




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176

/*
Made by SONG KIM
2020-10-03
*/

import java.util.Scanner;

public class Main {

public static class Node {

int data;
Node next;
Node previous;

public void displayNode(){
System.out.println(data);
}

}

public static class CustomLinkedList {
Node first;
Node last;

public CustomLinkedList() {
this.first = null;
this.last = null;
}

public void InsertFirst(int data){
Node newNode = new Node();
newNode.data = data;

if(IsEmpty())
{
last = newNode;
}else {
first.previous = newNode;
}
newNode.next = first;
this.first = newNode;

last.next = newNode;
newNode.previous = last;
}

public boolean IsEmpty(){
return first == null;
}

public void DisplayAll(){
System.out.print("<");
Node temp = new Node();
temp = last;
Node newNode = new Node();
newNode = first;
if(IsEmpty()!=true)
{
while (temp.data != newNode.data)
{
System.out.print(temp.data);
System.out.print(", ");
temp = temp.previous;
}
System.out.print(temp.data);
System.out.print(">");
}
}

public int Josephus(int sn, int d){

int counter = 1;

// start from where data = sn
Node newNode = new Node();
newNode = last;

if(IsEmpty())
{
return 0;
}

// System.out.println();
// System.out.println("first + last");
// System.out.println(first.data);
// System.out.println(last.data);
// System.out.println();

while (newNode.data != sn){
newNode = newNode.previous;
}


// find data with d distance away
while (counter != d){
newNode = newNode.previous;
++counter;
}





// print number being deleted
System.out.print(newNode.data);


// allocate next number
sn = newNode.previous.data;

// delete corresponding Node
// when newNode is last
if(newNode == last){
newNode.next.previous = newNode.previous;
newNode.previous.next = newNode.next;
last = newNode.previous;
}else {
newNode.next.previous = newNode.previous;
}

// when newNode is first
if(newNode == first){
newNode.next.previous = newNode.previous;
newNode.previous.next = newNode.next;
first = newNode.next;
}else {
newNode.previous.next = newNode.next;
}


return sn;


}
}

public static void main(String[] args) throws Exception {
CustomLinkedList cll = new CustomLinkedList();

Scanner sc = new Scanner(System.in);

// Number of Elements in the list
int N = sc.nextInt();

// Number of Elements to be jumped
int K = sc.nextInt();

// Initialize List with consecutive order
for (int i = 1; i <= N; i++) {
cll.InsertFirst(i);
}

// show all elements
//cll.DisplayAll();

// Starting number
int sn = 1;

//Josephus Problem

System.out.print("<");
for (int i = 0; i<N; i++){
//cll.DisplayAll();
//System.out.println();
sn = cll.Josephus(sn, K);
if (i == N-1)break;
System.out.print(", ");
}
System.out.print(">");


}
}




글을 마치며

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

인간은 뛰어넘은 역경의 숫자만큼 강해진다.

그 숫자가 많으면 많을수록,

어떠한 상황에서도 지지 않는 강한 사람이 된다.

그러니까 인생에서 성공하는 사람이 된다는 것은

역경을 많이 극복한다는 것과 같은 뜻이기도 하다.

<기타가와 야스시, ‘편지가게’>

모두들 화이팅 하셔서 훌륭한 프로그래머가 되시길 바라겠습니다.






Author

Song Kim

Posted on

2020-10-03

Updated on

2020-10-03

Licensed under

You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments