2.1 자료구조 소개
Def) 자료 구조(Data Structure): 자료를 효율적으로 관리하기 위한 구조
- 목적에 맞게 사용한 자료구조는 실행시간 단축이나 메모리 용량 절감 효과가 있다.
- 선형 자료구조 / 비선형 자료구조
Note) 자료구조의 구현
- 추상 자료형(absract Data type, ADT)
-> 자료 형태와 자료에 대한 연산을 정의한 것
-> 구체적인 구현 방법은 명시하지 않는다. (추상 클래스, 인터페이스)
2.2 배열
Note) 배열
- 데이터가 메모리 상에 연속적으로 저장된다 .
- 데이터와 인덱스가 1:1 대응으로 구성된다.
- 단점
-> 데이터 추가/ 삭제가 번거롭다.
-> 미리 최대 길이를 정해서 생성한다.
-> 가변 길이 배열은 배열의 크기를 변경할 때마다 새로운 배열을 생성한다.
-> 데이터 삭제 시, 인덱스를 유지하기 위해 빈 공간을 유지한다.
Ex)
<hide/>
// Practice
// 기본 배열 자료형을 이용한 배열의 생성, 삽입, 삭제 기능 구현
import java.util.Arrays;
class MyArray {
int[] arr;
// 배열의 초기 사이즈 설정
MyArray(int size){
this.arr = new int[size];
}
// 배열에 데이터 삽입
public void insertData(int index, int data){
if(index < 0 || index > this.arr.length){ // 연속적이지 않은 경우 예외처리
System.out.println("Index Error!");
return;
}
int[] arrDup = this.arr.clone();
this.arr = new int[arr.length + 1];
for(int i = 0;i < index; ++i){
this.arr[i] = arrDup[i];
}
for(int i = index + 1; i < this.arr.length; ++i){
this.arr[i] = arrDup[i - 1];
}
this.arr[index] = data;
}
// 배열에서 특정 데이터 삭제
public void removeData(int data){
int targetIndex = -1;
for(int i = 0; i < this.arr.length; ++i){
if(this.arr[i] == data){
targetIndex = i;
break;
}
}
if(targetIndex == -1){
System.out.println("해당 데이터가 없습니다.");
}else{
int[] arrDup = this.arr.clone();
this.arr = new int[this.arr.length - 1];
for(int i = 0 ; i < targetIndex; ++i){
this.arr[i] = arrDup[i];
}
for(int i = targetIndex; i < this.arr.length; ++i){
this.arr[i] = arrDup[i + 1];
}
}
}
}
public class Practice {
public static void main(String[] args) {
// Test code
int size = 5;
MyArray myArray = new MyArray(size);
for (int i = 0; i < size; i++) {
myArray.arr[i] = i + 1;
}
System.out.println(Arrays.toString(myArray.arr)); // [1, 2, 3, 4, 5]
myArray.arr[0] = 10;
System.out.println(Arrays.toString(myArray.arr)); // [10, 2, 3, 4, 5]
myArray.insertData(2, 20);
System.out.println(Arrays.toString(myArray.arr)); // [10, 2, 20, 3, 4, 5]
myArray.insertData(6, 60);
System.out.println(Arrays.toString(myArray.arr)); // [10, 2, 20, 3, 4, 5, 60]
myArray.insertData(-1, 0); // Index Error
myArray.removeData(4);
System.out.println(Arrays.toString(myArray.arr)); // [10, 2, 20, 3, 5, 60]
myArray.removeData(5);
System.out.println(Arrays.toString(myArray.arr)); // [10, 2, 20, 3, 60]
myArray.removeData(99); // 해당 데이터가 없습니다.
}
}Note) 실행 결과
2.3 배열 practice
Ex 1) 주어진 배열에 대해 홀수 데이터의 평균과 짝수 데이터의 평균을 구하라
<hide/>
// Practice1
// 배열 arr 의 모든 데이터에 대해서,
// 짝수 데이터들의 평균과 홀수 데이터들의 평균을 출력하세요.
// 입출력 예시)
// 배열 arr: 1, 2, 3, 4, 5, 6, 7, 8, 9
// 결과:
// 짝수 평균: 5.0
// 홀수 평균: 5.0
import java.lang.reflect.Array;
import java.util.Arrays;
public class Practice1 {
public static void main(String[] args) {
int[] arr= {1, 2, 3, 4, 5, 6, 7, 8, 9};
float sumEven = 0;
float sumOdd = 0;
int evenCnt = 0;
int oddCnt = 0;
for(int item : arr){
if(item % 2 == 0){
sumEven += item;
++evenCnt;
}else{
sumOdd += item;
++oddCnt;
}
}
System.out.println("짝수 평균: "+ sumEven / evenCnt);
System.out.println("홀수 평균: "+ sumOdd / oddCnt);
}
}Note) 실행 결과
Ex 2) 주어진 배열에서 target에 해당하는 값의 인덱스를 출력하라
<hide/>
// Practice2
// 배열 arr 에서 target 에 해당하는 값의 인덱스를 출력
// 해당 값이 여러 개인 경우 가장 큰 인덱스 출력
// 입출력 예시)
// 배열 arr: 1, 1, 100, 1, 1, 1, 100
// target : 100
// 결과: 6
public class Practice2 {
public static void main(String[] args) {
int[] arr= {1, 1, 100, 1, 1, 1, 100};
int target = 100;
int result = -1;
for(int i = arr.length - 1;i >= 0 ; --i){
if(arr[i] == target){
result = i;
break;
}
}
System.out.println(result);
}
}Note) 실행 결과: 6
Ex 3) 주어진 배열에 대해 데이터 순서를 거꾸로 변경하여 출력하라
<hide/>
// Practice3
// 배열 arr 의 데이터 순서를 거꾸로 변경하세요.
// 추가 배열을 사용하지 않고 구현
// 입출력 예시)
// arr: 1, 3, 5, 7, 9
// 결과: 9, 7, 5, 3, 1
import java.util.Arrays;
public class Practice3 {
public static void main(String[] args) {
int [] arr = { 1, 3, 5, 7, 9};
for(int i = 0; i < arr.length / 2; ++i){
int tmp = arr[i];
arr[i] = arr[arr.length - 1 - i];
arr[arr.length - 1 - i] = tmp;
}
System.out.println(Arrays.toString(arr));
}
}Note) 실행 결과
Ex 4) 배열에서 peek값을 출력하라
- peek값이란? 좌우보다 큰 값을 말한다.
<hide/>// Practice4
// 배열 arr 에서 peek 값 모두 출력
// 입출력 예시)
// arr: 3, 1, 2, 6, 2, 2, 5, 1, 9, 10, 1, 11
// 결과: 3, 6, 5, 10, 11
import java.util.Arrays;
public class Practice4 {
public static void main(String[] args) {
int[] arr = {3, 1, 2, 6, 2, 2, 5, 1, 9, 10, 1, 11};
for(int i = 0; i < arr.length; ++i){
if(i == 0 && arr[i] > arr[i + 1]){
System.out.print(arr[i]+ " ") ;
}else if(i == arr.length - 1 && arr[i] > arr[i -1]){
System.out.print(arr[i]+ " ") ;
}else if(arr[i - 1] < arr[i] && arr[i] > arr[i + 1]){
System.out.print(arr[i]+ " ") ;
}
}
System.out.println();
}
}Note) 실행 결과
Ex 5) 배열의 데이터를 오름차순으로 출력한다.
<hide/>
// Practice5
// 배열 arr 의 값을 오름차순으로 출력
import java.util.*;
// 입출력 예시)
// arr: 5, 3, 1, 4, 6, 1
// 결과: 1, 1, 3, 4, 5, 6
public class Practice5 {
public static void main(String[] args) {
int [] arr = {5, 3, 1, 4, 6, 1};
int [] visited = new int[arr.length];
int visitCnt = 0;
int minVal = Integer.MAX_VALUE;
int minIdx = -1;
while(visitCnt < arr.length){
for(int i = 0; i < arr.length; ++i){
if(arr[i] < minVal && visited[i] == 0){
minVal = arr[i];
minIdx = i;
}
}
if(minIdx != - 1){
System.out.print(minVal + " ");
visited[minIdx] = 1;
++visitCnt;
}
minVal = Integer.MAX_VALUE;
minIdx = - 1;
}
System.out.println();
}
}Note) 실행 결과
Ex 6) 배열에서 중복된 데이터를 없애고 새 배열을 만들어라
<hide/>
// Practice6
// 배열 arr 에서 중복 값을 제거한 새 배열을 만드시오.
// 입출력 예시)
// arr: 1, 5, 3, 2, 2, 3, 1, 4, 1, 2, 3, 5
// 결과: 1, 5, 3, 2, 4
import java.util.Arrays;
public class Practice6 {
public static void main(String[] args) {
int[] arr = {1, 5, 3, 2, 2, 3, 1, 4, 1, 2, 3, 5};
int[] arrResult= new int[arr.length];
int cnt = 0;
for(int i = 0; i < arr.length; ++i){
boolean dupFlag = false;
for(int j = 0; j < cnt; ++j){
if(arr[i] == arrResult[j]){ // 중복된 값이므로
dupFlag = true;
}
}
if(dupFlag == false){
arrResult[cnt++] = arr[i];
}
}
for(int i = 0;i < cnt; ++i){
System.out.print(arrResult[i] + " ");
}
System.out.println();
}
}Note) 실행 결과
Ex 7) 2차원 배열을 시계방향으로 90도 회전시킨 결과를 출력하라
Sol)
<hide/>
// Practice7
// 2차원 배열 arr 을 시계방향 90도 회전시킨 결과를 출력하세요.
// 입출력 예시:
// arr:
// 1 2 3 4 5
// 6 7 8 9 10
// 11 12 13 14 15
// 결과:
// 11 6 1
// 12 7 2
// 13 8 3
// 14 9 4
// 15 10 5
public class Practice7 {
static void printArr(int [][] arr){
for(int [] item1D : arr){
for(int item : item1D){
System.out.print(item + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] arr = {{ 1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15}};
int [][] arr90 = new int[arr[0].length][arr.length];
for(int i = 0; i < arr.length; ++i) { // j = 0 ~ 4
for (int j = 0; j < arr[i].length; ++j) { // i = 2 ~ 0
int r = arr.length - 1 - i;
arr90[j][r] = arr[i][j];
}
}
printArr(arr90);
}
}MySol)
<hide/>
// Practice7
// 2차원 배열 arr 을 시계방향 90도 회전시킨 결과를 출력하세요.
// 입출력 예시:
// arr:
// 1 2 3 4 5
// 6 7 8 9 10
// 11 12 13 14 15
// 결과:
// 11 6 1
// 12 7 2
// 13 8 3
// 14 9 4
// 15 10 5
public class Practice7 {
public static void main(String[] args) {
int[][] arr = {{ 1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15}};
for(int j = 0;j < arr[0].length; ++j){ // j = 0 ~ 4
for(int i = arr.length - 1; i >= 0 ; --i){ // i = 2 ~ 0
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}Note) 실행 결과
2.4 연결리스트(LinkedList)
Def) 연결 리스트: 데이터를 링크로 연결해서 관리하는 자료구조
- 자료의 순서는 정해져있지만 메모리상 연속성이 보장되지는 않는다.
Note) 장단점
- 장점: 데이터 공간을 미리 할당할 필요가 없다. (리스트 길이가 가변적 - 데이터 추가, 삭제 용이)
- 단점: 연결 구조를 위한 별도 데이터 공간 필요
-> 연결 정보를 찾는 시간이 필요 (상대적으로 속도가 느리다.)
-> 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업이 필요하다. (head/ 중간/ tail)
Note) Java에서는 Garbage Collection이 해당 메모리를 더이상 참조하지 않으면 자동으로 delete_Node를 지워준다.
Note) 연결 리스트의 기본 구조
Def) 노드(Node): 데이터 저장 단위로 값과 포인터로 구성된다.
- 포인터(pointer): 다음 노드나 이전 노드의 연결 정보
- 가장 앞에 있는 노드를 head, 가장 뒤에 있는 노드를 tail이라고 한다.
Ex)
<hide/>
// 선형 자료구조 - 연결 리스트
// 단순 연결 리스트 (simple ver.) 기본 구조 구현
// 노드
class Node {
int data;
Node next;
Node(){}
Node(int data, Node next){
this.data = data;
this.next = next;
}
}
class LinkedList {
Node head;
LinkedList(){}
LinkedList(Node node){
this.head = node;
}
// 연결 리스트 비어있는지 확인
public boolean isEmpty(){
if(this.head == null){
return true;
}
return false;
}
// 연결 리스트의 맨 뒤에 데이터 추가
public void addData(int data){
if(this.head == null){
this.head = new Node(data, null);
}else{
Node cur = this.head;
while(cur.next != null){
cur = cur.next;
}
cur.next = new Node(data, null);
}
}
// 연결 리스트의 맨 뒤의 데이터 삭제
public void removeData(){
if(this.isEmpty()){
System.out.println("List is Empty!");
return;
}
Node cur = this.head;
Node prev = cur;
while(cur.next != null){
prev = cur;
cur = cur.next;
}
if(cur == this.head){
this.head = null;
}else{
prev.next = null;
}
}
// 연결 리스트에서 데이터 찾기
public void findData(int data){
if(this.isEmpty()){
System.out.println("List is empty!");
return;
}
Node cur = this.head;
while(cur != null){
if(cur.data == data){
System.out.println("Data exists!");
return;
}
cur = cur.next;
}
System.out.println("Data not found!");
}
// 연결 리스트의 모든 데이터 출력
public void showData(){
if(this.isEmpty()){
System.out.println("List is empty!");
return;
}
Node cur = this.head;
while(cur != null){
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
// Test Code
LinkedList myList = new LinkedList(new Node(1, null));
myList.showData(); // 1
myList.addData(2);
myList.addData(3);
myList.addData(4);
myList.addData(5);
myList.showData(); // 1 2 3 4 5
myList.findData(3); // Data exist!
myList.findData(100); // Data not found!
myList.removeData();
myList.removeData();
myList.removeData();
myList.showData(); // 1 2
myList.removeData();
myList.removeData();
myList.removeData(); // List is empty
}
}Note) 실행 결과
Ex) 단방향 연결 리스트
<hide/>
// Practice1
// 단순 연결 리스트 구현 완성
class LinkedList2 extends LinkedList{
LinkedList2(Node node){
this.head = node;
}
// 연결 리스트에 데이터 추가
// before_data가 null인 경우, 가장 뒤에 추가
// before_data에 값이 없는 경우 해당 갑을 가진 노드 앞에 추가
public void addData(int data, Integer beforeData){
if(this.head == null){
this.head = new Node(data, null);
}else if(beforeData == null){
Node cur = this.head;
while(cur.next != null){
cur = cur.next;
}
cur.next = new Node(data, null);
}else{ // 리스트 내에서
Node cur = this.head;
Node pre = cur;
while(cur != null){
if(cur.data == beforeData){
if(cur == this.head){
this.head = new Node(data, this.head);
}else{ // 중간에 들어갈 때
pre.next = new Node(data, cur);
}
break;
}
pre = cur;
cur = cur.next;
}
}
}
public void removeData(int data){
if(this.isEmpty()){
System.out.println("List is empty!");
return;
}
Node cur = this.head;
Node pre = cur;
while(cur != null){
if(cur.data == data){
if(cur == this.head){
this.head = cur.next;
}else{
pre.next = cur.next;
}
break;
}
pre = cur;
cur = cur.next;
}
}
}
public class Practice1 {
public static void main(String[] args) {
// Test code
LinkedList2 myList = new LinkedList2(new Node(1, null));
myList.showData(); // 1
myList.addData(2);
myList.addData(3);
myList.addData(4);
myList.addData(5);
myList.showData(); // 1 2 3 4 5
myList.addData(100, 1);
myList.addData(200, 2);
myList.addData(300, 3);
myList.addData(400, 4);
myList.addData(500, 5);
myList.showData(); // 100 1 200 2 300 3 400 4 500 5
myList.removeData(300);
myList.removeData(100);
myList.removeData(500);
myList.removeData(200);
myList.removeData(400);
myList.showData(); // 1 2 3 4 5
myList.removeData(3);
myList.removeData(1);
myList.removeData(5);
myList.removeData(2);
myList.removeData(4);
myList.showData(); // List is empty!
}
}Note) 실행 결과
Ex) 양방향 연결 리스트
<hide/>
// Practice2
// 양방향 연결 리스트 (Doubly Linked List) 구현
class NodeBi {
int data;
NodeBi next;
NodeBi prev;
NodeBi(int data, NodeBi next, NodeBi prev){
this.data = data;
this.next = next;
this.prev = prev;
}
}
class DoublyLinkedList extends LinkedList{
NodeBi head;
NodeBi tail;
DoublyLinkedList(NodeBi node){
this.head = node;
this.tail = node;
}
public boolean isEmpty(){
if(this.head == null){
return true;
}
return false;
}
public void addData(int data, Integer beforeData){
if(this.head == null){
this.head = new NodeBi(data,null, null);
this.tail = this.head;
}else if(beforeData == null){
this.tail.next = new NodeBi(data, null, this.tail);
this.tail = this.tail.next;
}else{// before데이터가 있는 경우
NodeBi cur = this.head;
NodeBi pre = cur;
while(cur != null){
if(cur.data == beforeData){
if(cur == this.head){
this.head = new NodeBi(data, this.head, null);
this.head.next.prev = this.head;
}else{// 헤드가 아닐 때
pre.next = new NodeBi(data, cur, pre);
cur.prev = pre.next;
}
break;
}
pre = cur;
cur = cur.next;
}
}
}
public void removeData(int data){
if(this.isEmpty()){
System.out.println("List is empty!");
return;
}
NodeBi cur = this.head;
NodeBi pre = cur;
while(cur != null){
if(cur.data == data){
if(cur == this.head && cur == this.tail){ // 노드가 하나인 경우
this.head = null;
this.tail = null;
}else if(cur == this.head){
this.head = cur.next;
this.head.prev = null; // 기존의 헤드는 없어진다.
}else if(cur == this.tail){
this.tail = this.tail.prev; // 가장 끝의 태일을 기존 태일의 이전이 되도록 만든다.
this.tail.next = null; // 기존의 끝 부분
}else{ // 중간 노드 삭제
pre.next = cur.next;
cur.next.prev = pre; // 중간 노드는 자동으로 없어진다
}
break;
}
pre = cur;
cur = cur.next;
}
}
public void showData(){
if(this.isEmpty()){
System.out.println("List is empty!");
return;
}
NodeBi cur = this.head;
while(cur != null){
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
public void showDataFromTail(){
if(this.isEmpty()){
System.out.println("List is empty!");
return;
}
NodeBi cur = this.tail;
while(cur != null){
System.out.print(cur.data + " ");
cur = cur.prev;
}
System.out.println();
}
}
public class Practice2 {
public static void main(String[] args) {
// Test code
DoublyLinkedList myList = new DoublyLinkedList(new NodeBi(1, null, null));
myList.showData(); // 1
myList.addData(2, null);
myList.addData(3, null);
myList.addData(4, null);
myList.addData(5, null);
myList.showData(); // 1 2 3 4 5
myList.showDataFromTail(); // 5 4 3 2 1
myList.addData(100, 1);
myList.addData(200, 2);
myList.addData(300, 3);
myList.addData(400, 4);
myList.addData(500, 5);
myList.showData(); // 100 1 200 2 300 3 400 4 500 5
myList.showDataFromTail(); // 5 500 4 400 3 300 2 200 1 100
myList.removeData(300);
myList.removeData(100);
myList.removeData(500);
myList.removeData(200);
myList.removeData(400);
myList.showData(); // 1 2 3 4 5
myList.showDataFromTail(); // 5 4 3 2 1
myList.removeData(3);
myList.removeData(1);
myList.removeData(5);
myList.removeData(2);
myList.removeData(4);
myList.showData(); // List is empty!
myList.showDataFromTail(); // List is empty!
}
}Note) 실행 결과
Ex) practice3 원형 연결 리스트
<hide/>
// Practice3
// 원형 연결 리스트 (Circular Linked List) 구현
class CircularLinkedList {
NodeBi head;
NodeBi tail;
CircularLinkedList(NodeBi node){
this.head = node;
this.tail = node;
node.next = this.head;
node.prev = this.head;
}
public boolean isEmpty(){
if(this.head == null){
System.out.println("List is empty!");
return true;
}
return false;
}
// 연결 리스트에 데이터 추가
// before_data 가 null 인 경우, 가장 뒤에 추가
// before_data 에 값이 있는 경우, 해당 값을 가진 노드 앞에 추가
public void addData(int data, Integer beforeData){
if(this.head == null){ // 처음에 노드 하나일 때
NodeBi newNodeBi = new NodeBi(data, null, null);
this.head = newNodeBi;
this.tail = newNodeBi;
newNodeBi.next = newNodeBi;
}else if(beforeData == null){
NodeBi newNodeBi = new NodeBi(data, this.head, this.tail);
this.tail.next = newNodeBi;
this.head.prev = newNodeBi;
this.tail = newNodeBi;
}else {
NodeBi cur = this.head;
NodeBi pre = cur;
do{
if(cur.data == beforeData) {
if (cur == this.head) {
NodeBi newNodeBi = new NodeBi(data, this.head, this.tail);
this.tail.next = newNodeBi;
this.head.prev = newNodeBi;
this.head = newNodeBi;
}else{// 노드가 중간에 추가되는 경우
NodeBi newNodeBi = new NodeBi(data,cur, pre);
pre.next = newNodeBi;
cur.prev = newNodeBi;
}
break;
}
pre = cur;
cur = cur.next;
}while(cur != this.head);
}
}
// 연결 리스트에서 특정 값을 가진 노드 삭제
public void removeData(int data){
if(this.isEmpty()){
System.out.println("List is empty!");
return;
}
NodeBi cur = this.head;
NodeBi pre = cur;
while(cur != null){
if(cur.data == data){
if(cur == this.head && cur == this.tail){ // 노드가 하나뿐일 때,
this.head = null;
this.tail = null;
}else if(cur == this.head){
cur.next.prev = this.head.prev;
this.head = cur.next;
this.tail.next = this.head;
}else if(cur == this.tail){
pre.next = this.tail.next;
this.tail = pre;
this.head.prev = this.tail;
}else{ // 노드가 중간일 때
pre.next = cur.next;
cur.next.prev = pre;
}
break;
}
pre = cur;
cur = cur.next;
}
}
public void showData(){
if(this.isEmpty()){
System.out.println("List is empty!");
return;
}
NodeBi cur = this.head;
while(cur.next != this.head){ // next가 자신이 되지 않을 때까지
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println(cur.data);
}
}
public class Practice3 {
public static void main(String[] args) {
// Test code
CircularLinkedList myList = new CircularLinkedList(new NodeBi(1, null, null));
myList.addData(2, null);
myList.addData(3, null);
myList.addData(4, null);
myList.addData(5, null);
myList.showData(); // 1 2 3 4 5
myList.addData(100, 1);
myList.addData(200, 2);
myList.addData(300, 3);
myList.addData(400, 4);
myList.addData(500, 5);
myList.showData(); // 100 1 200 2 300 3 400 4 500 5
myList.removeData(300);
myList.removeData(100);
myList.removeData(500);
myList.removeData(200);
myList.removeData(400);
myList.showData(); // 1 2 3 4 5
myList.removeData(3);
myList.removeData(1);
myList.removeData(5);
myList.removeData(2);
myList.removeData(4);
myList.showData(); // List is empty!
}
}Note) 실행 결과
2.5 단방향 연결 리스트 practice
Ex) practice1. 단방향 연결 리스트에서 중복 데이터를 찾아 삭제하라.
- findData메서드의 반환형을 boolean으로 바꿔서 false인 경우에만 addData를 한다.
<hide/>
// Practice1
// 단방향 연결 리스트에서 중복 데이터를 찾아 삭제하세요.
// 입출력 예시)
// 입력 연결 리스트: 1, 3, 3, 1, 4, 2, 4, 2
// 결과 연결 리스트: 1, 3, 4, 2
class Node {
int data;
Node next;
Node() {}
Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
class LinkedList {
Node head;
LinkedList() {}
LinkedList(Node node) {
this.head = node;
}
public boolean isEmpty() {
return this.head == null;
}
public void addData(int data) {
if (this.head == null) {
this.head = new Node(data, null);
} else {
Node cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = new Node(data, null);
}
}
public void removeData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
Node cur = this.head;
Node pre = cur;
while (cur != null) {
if (cur.data == data) {
if (cur == this.head) {
this.head = cur.next;
} else {
pre.next = cur.next;
}
break;
}
pre = cur;
cur = cur.next;
}
}
public boolean findData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
}
Node cur = this.head;
while (cur != null) {
if (cur.data == data) {
// System.out.println("Data exist!");
return true;
}
cur = cur.next;
}
return false;
// System.out.println("Data not found!");
}
public void showData() {
if (this.isEmpty()) {
System.out.println("List is empty!");
return;
}
Node cur = this.head;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
}
public class Practice1 {
public static LinkedList removeDup(LinkedList listBefore) {
// 노드 하나마다 처음에서 부터 자기 인덱스의 값 까지 하나씩 비교해서
LinkedList listAfter = new LinkedList();
Node cur = listBefore.head;
while(cur != null) {
if (listAfter.findData(cur.data) == false) {
listAfter.addData(cur.data);
}
cur = cur.next;
}
return listAfter;
}
public static void main(String[] args) {
// Test code
LinkedList linkedList = new LinkedList();
linkedList.addData(1);
linkedList.addData(3);
linkedList.addData(3);
linkedList.addData(1);
linkedList.addData(4);
linkedList.addData(2);
linkedList.addData(4);
linkedList.addData(2);
linkedList.showData(); // 1 3 3 1 4 2 4 2
linkedList = removeDup(linkedList);
linkedList.showData(); // 1 3 4 2
}
}Note) 실행 결과
Ex) practice2. 팰린드롬 연결 리스트: pallindrome 문자열이 맞는지 아닌지 확인하라
- 단방향 연결 리스트로 팰린드롬 문자열 확인하기
<hide/>
// Practice2
// Palindrome 연결 리스트
// 추가 자료구조 없이 연결 리스트만으로 풀어보기
// Palindrome: 앞으로 읽어도 뒤로 읽어도 같은 문자열
// 입력 예시)
// 입력 연결 리스트: 1, 3, 5, 3, 1
// 결과: true
// 입력 연결 리스트: 3, 5, 5, 3
// 결과: true
// 입력 연결 리스트: 1, 3, 5, 1
// 결과: false
public class Practice2 {
public static boolean checkPalindrome(LinkedList list) {
Node cur = list. head;
Node left = list. head;
Node right = null;
int cnt = 0;
while(cur != null){
++cnt;
right = cur;
cur = cur.next;
}
Node prevRight = right;
for(int i = 0; i < cnt / 2; ++i){
if(left.data != right.data){
return false;
}
//양끝데이터가 같은 경우
left = left.next;
right = left; // 일단은 left로 잡은 후,
// prevRight를 만날 때까지 right를 이동시킨다.
while(right.next != prevRight){
right = right.next;
}
}
return true;
}
public static void main(String[] args) {
// Test code
LinkedList linkedList = new LinkedList();
linkedList.addData(1);
linkedList.addData(3);
linkedList.addData(5);
linkedList.addData(3);
linkedList.addData(1);
System.out.println(checkPalindrome(linkedList));
LinkedList linkedList2 = new LinkedList();
linkedList2.addData(3);
linkedList2.addData(5);
linkedList2.addData(5);
linkedList2.addData(3);
System.out.println(checkPalindrome(linkedList2));
LinkedList linkedList3 = new LinkedList();
linkedList3.addData(1);
linkedList3.addData(3);
linkedList3.addData(5);
linkedList3.addData(1);
System.out.println(checkPalindrome(linkedList3));
}
}Note) 실행 결과
Ex) practice3 연결리스트 부분 뒤집기 - 주어진 연결 리스트에서 시작 위치부터 끝 위치 사이의 노드들을 뒤집으ㄹ시오
<hide/>
// Practice3
// 연결 리스트 부분 뒤집기
// 주어진 연결 리스트에서 시작 위치부터 끝 위치 사이의 노드들을 뒤집으시오.
// 입력 예시)
// 입력 연결 리스트: 1, 2, 3, 4, 5
// 시작 위치: 2
// 끝 위치: 4
// (처음 위치는 1부터라고 가정)
// 결과 연결 리스트: 1, 4, 3, 2, 5
public class Practice3 {
public static LinkedList reverseList(LinkedList list, int left, int right) {
Node cur1 = null;
Node pre1 = null;
cur1 = list.head;
for(int i = 0; i < left - 1; ++i){
pre1 = cur1;
cur1 = cur1.next;
}
Node cur2 = cur1;
Node pre2 = pre1;
Node after = null;
for(int i = left; i <= right; ++i){
after = cur2.next;
cur2.next = pre2;
pre2 = cur2;
cur2 = after;
}
pre1.next = pre2;
cur1.next = cur2;
return list;
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.addData(1);
linkedList.addData(2);
linkedList.addData(3);
linkedList.addData(4);
linkedList.addData(5);
linkedList.showData();
linkedList = reverseList(linkedList, 2, 4);
linkedList.showData();
LinkedList linkedList2 = new LinkedList();
linkedList2.addData(1);
linkedList2.addData(2);
linkedList2.addData(3);
linkedList2.addData(4);
linkedList2.addData(5);
linkedList2.addData(6);
linkedList2.addData(7);
linkedList2.showData();
linkedList2 = reverseList(linkedList2, 3, 5);
linkedList2.showData();
}
}Note) 실행 결과
Ex) practic4 주어진 문자열 배열을 연결 리스트 배열로 관리하는 코드를 작성한다.
- 각각의 리스트에는 접근이 불가능하므로 해당 위치에 하나씩 객체를 만들어줘야한다.
<hide/>
package P4;
// Practice4
// 연결 리스트 배열 사용 연습
// 주어진 문자열 배열을 연결 리스트 배열로 관리하는 코드를 작성하시오.
// 관리 규칙은 다음과 같다.
// 각 문자열의 첫 글자가 같은 것끼리 같은 연결 리스트로 관리하기
import java.util.ArrayList;
import java.util.HashSet;
class Node {
String data;
Node next;
Node() {}
Node(String data, Node next) {
this.data = data;
this.next = next;
}
}
class LinkedList {
Node head;
char alphabet;
LinkedList() {}
LinkedList(Node node, char alphabet) {
this.head = node;
this.alphabet = alphabet;
}
public boolean isEmpty() {
return this.head == null;
}
public void addData(String data) {
if (this.head == null) {
this.head = new Node(data, null);
} else {
Node cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = new Node(data, null);
}
}
public void removeData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
return;
}
Node cur = this.head;
Node pre = cur;
while (cur != null) {
if (cur.data.equals(data)) {
if (cur == this.head) {
this.head = cur.next;
} else {
pre.next = cur.next;
}
break;
}
pre = cur;
cur = cur.next;
}
}
public boolean findData(int data) {
if (this.isEmpty()) {
System.out.println("List is empty");
return false;
}
Node cur = this.head;
while (cur != null) {
if (cur.data.equals(data)) {
System.out.println("Data exist!");
return true;
}
cur = cur.next;
}
System.out.println("Data not found!");
return false;
}
public void showData() {
if (this.isEmpty()) {
System.out.println("List is empty!");
return;
}
Node cur = this.head;
while (cur != null) {
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
}
public class Practice4 {
public static void dataCollect(String[] data) {
HashSet<Character> set = new HashSet<>();
for(String item : data){
set.add(item.toCharArray()[0]); // 첫글자를 set에 넣는다.
}
System.out.println(set);
Character[] arr = set.toArray(new Character[0]); // set을 배열로 바꾼다.
LinkedList[] linkedList = new LinkedList[set.size()]; // 아직 각각의 위치에는 접근이 불가능하다.
for(int i = 0; i < linkedList.length; ++i){
linkedList[i] = new LinkedList(null, arr[i]); // 해당 위치에 객체를 만들어줘야한다.
}
for(String item : data){
for(LinkedList list : linkedList){
if(list.alphabet == item.toCharArray()[0]){
list.addData(item);
}
}
}
for(LinkedList list: linkedList){
System.out.print(list.alphabet + ": ");
list.showData();
}
}
public static void main(String[] args) {
// Test code
String[] input = {"apple", "watermelon", "banana", "apricot", "kiwi", "blueberry", "cherry", "orange"};
dataCollect(input);
System.out.println();
String[] input2 = {"ant", "kangaroo", "dog", "cat", "alligator", "duck", "crab", "kitten", "anaconda", "chicken"};
dataCollect(input2);
}
}Note) 실행 결과
2.6 스택(Stack)
- 후입 선출구조(LIFO, last in first out / FILO, first in last out)
ex) 함수 콜 스택, 수식 계산, 인터럽트(갑자기 발생한 일)처리
2.7 스택(Stack) 문제 풀이
Ex 1) ArrayList를 이용한 Stack 구현하기
<hide/>
// Practice1
// ArrayList 를 이용한 스택 구현
import java.util.ArrayList;
class MyStack1 {
ArrayList list;
MyStack1() {
this.list = new ArrayList();
}
public boolean isEmpty() {
if(this.list.size() == 0){
return true;
}else{
return false;
}
}
public void push(int data) {
this.list.add(data);
}
public Integer pop() {
if(this.isEmpty()){
System.out.println("Stack is empty!");
return null;
}
// arraylist가 제네릭으로 되어 있지 않아서 형변환을 해줘야 오류가 나지 않는다.
int data = (int) this.list.get(this.list.size() - 1); // 가장 마지막 값을 가져온다.
this.list.remove(this.list.size() - 1);
return data;
}
public Integer peek() {
if(this.isEmpty()){
System.out.println("Stack is empty!");
return null;
}
int data = (int) this.list.get(this.list.size() - 1); // 가장 마지막 값을 가져온다.
return data;
}
public void printStack() {
System.out.println(this.list);
}
}
public class Practice1 {
public static void main(String[] args) {
// Test code
MyStack1 myStack = new MyStack1();
System.out.println(myStack.isEmpty());
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
myStack.push(5);
myStack.printStack(); // 1, 2, 3, 4, 5
System.out.println(myStack.peek()); // 5
myStack.printStack(); // 1, 2, 3, 4, 5
System.out.println(myStack.pop()); // 5
System.out.println(myStack.pop()); // 4
myStack.printStack(); // 1, 2, 3
System.out.println(myStack.pop()); // 3
System.out.println(myStack.pop()); // 2
System.out.println(myStack.pop()); // 1
myStack.printStack();
}
}Note) 실행 결과
Ex 2) 배열을 이용한 Stack 구현하기
<hide/>
// Practice2
// 배열을 이용한 기본 스택 직접 구현
class MyStack2 {
int[] arr;
int top = -1;
MyStack2(int size) {
arr = new int[size];
}
public boolean isEmpty() {
if(top == -1){
return true;
}
return false;
}
public boolean isFull() {
if(this.top == arr.length - 1){
return true;
}
return false;
}
public void push(int data) {
if(isFull()){
System.out.println("Stack is full!");
return;
}
arr[++top] = data;
}
public Integer pop() {
if(isEmpty()){
System.out.println("Stack is empty!");
return null;
}
return arr[top--];
}
public Integer peek() {
if(isEmpty()){
System.out.println("Stack is empty!");
return null;
}
return arr[top];
}
public void printStack() {
for(int i = 0; i < top + 1; ++i){
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
public class Practice2 {
public static void main(String[] args) {
// Test code
MyStack2 myStack = new MyStack2(5);
System.out.println(myStack.isEmpty());
myStack.push(1);
myStack.push(2);
myStack.push(3);
myStack.push(4);
myStack.push(5);
myStack.push(6);
myStack.printStack(); // 1, 2, 3, 4, 5
System.out.println(myStack.peek()); // 5
myStack.printStack(); // 1, 2, 3, 4, 5
System.out.println(myStack.pop()); // 5
System.out.println(myStack.pop()); // 4
myStack.printStack(); // 1, 2, 3
System.out.println(myStack.pop()); // 3
System.out.println(myStack.pop()); // 2
System.out.println(myStack.pop()); // 1
myStack.printStack();
}
}Note) 실행 결과
2.7 Stack 문제 풀이
Ex 1) 문자열 뒤집기
MySol)
- for문(char c : .. ) 대신에 for(String s : str.split("")) 을 쓸 수도 있다.
<hide/>
// Practice1
// 문자열 뒤집기
// 입출력 예시)
// 입력: "Hello"
// 출력: "OlleH"
// 입력: 1 3 5 7 9
// 출력: 9 7 5 3 1
import java.util.Stack;
public class Practice1 {
public static String reverseString(String str) {
Stack<Character> stack = new Stack<>();
String answer = "";
for(char c : str.toCharArray()){
stack.push(c);
}
while(!stack.isEmpty()){
answer += stack.pop();
}
return answer;
}
public static void main(String[] args) {
// Test code
String result = reverseString("Hello");
System.out.println("result = " + result);
result = reverseString("1 3 5 7 9");
System.out.println("result = " + result);
}
}Note) 실행 결과
Ex 2) 괄호 짝 검사
<hide/>
// Practice2
// 괄호 짝 검사
// 입출력 예시)
// 입력: "("
// 출력: Fail
// 입력: ")"
// 출력: Fail
// 입력: "()"
// 출력: Pass
import java.util.Stack;
public class Practice2 {
public static void checkParenthesis(String str) {
Stack stack = new Stack();
for(char x : str.toCharArray()){
if(x == '('){
stack.push(x);
}else{
if(stack.isEmpty()){
System.out.println("FAIL!");
return;
}
stack.pop();
}
}
if(stack.isEmpty()){
System.out.println("PASS!");
return;
}
System.out.println("FAIL!");
}
public static void main(String[] args) {
// Test code
checkParenthesis("("); // FAIL!
checkParenthesis(")"); // FAIL!
checkParenthesis("()"); // PASS!
checkParenthesis("()()()"); // PASS!
checkParenthesis("(())()"); // PASS!
checkParenthesis("(((()))"); // FAIL!
}
}Note) 실행 결과
Ex 3) 후위 표기법 연산
<hide/>
// Practice3
// 후위표기법 연산
// 참고 설명) 전위/중위/후위 표기법
// 입출력 예시)
// 입력: "2 2 +"
// 출력: 4
// 입력: "2 2 -"
// 출력: 0
import java.util.Stack;
public class Practice3 {
public static double calculate(String string) {
Stack<Double> stack = new Stack();
for(String x : string.split(" ")){
if(x.equals("+")){
Double a = stack.pop();
Double b = stack.pop();
stack.push(b + a);
// System.out.print(a + "+" + b + "=" + answer);
}else if(x.equals("-")){
Double a = stack.pop();
Double b = stack.pop();
stack.push(- a + b);
// System.out.print(b + "-" + a + "=" + answer);
}else if(x.equals("*")){
Double a = stack.pop();
Double b = stack.pop();
stack.push(a * b);
}else if(x.equals("/")){
Double a = stack.pop();
Double b = stack.pop();
stack.push(1 / a * b);
}else{
stack.push(Double.parseDouble(x));
}
}
return stack.pop();
}
public static void main(String[] args) {
// Test code
System.out.println(calculate("2 2 +")); // 4
System.out.println(calculate("2 2 -")); // 0
System.out.println(calculate("2 2 *")); // 4
System.out.println(calculate("2 2 /")); // 1
System.out.println(calculate("1 1 + 2 * 3 * 2 / 5 -")); // 1
System.out.println(calculate("5 2 * 3 - 8 * 4 /")); // 14
}
}Note) 실행 결과
Ex 4) 두 문자열 비교, '#'은 backspace로 바로 이전의 문자를 삭제하는 기능이라고 가정한다.
<hide/>
// Practice4
// 두 문자열 비교
// 단, #은 backspace 로 바로 이전의 문자를 삭제하는 기능이라고 가정
// 입출력 예시
// 입력: s1 = "tree", s2 = "th#ree"
// 출력: true
// 입력: s1 = "ab#a", s2 = "aab#"
// 출력: true
// 입력: s1 = "wo#w", s2 = "ww#o"
// 출력: false
import java.util.Stack;
public class Practice4 {
public static boolean stringCompare(String s1, String s2) {
Stack stack1 = new Stack();
Stack stack2 = new Stack();
for(char c : s1.toCharArray()){
if(c == '#'){
stack1.pop();
continue;
}
stack1.push(c);
}
for(char c : s2.toCharArray()){
if(c == '#'){
stack2.pop();
continue;
}
stack2.push(c);
}
return String.valueOf(stack1).equals(String.valueOf(stack2));
}
public static void main(String[] args) {
// Test code
String s1 = "tree";
String s2 = "th#ree";
System.out.println(stringCompare(s1, s2));
s1 = "ab#a";
s2 = "aab#";
System.out.println(stringCompare(s1, s2));
s1 = "wo#w";
s2 = "ww#o";
System.out.println(stringCompare(s1, s2));
}
}Note) 실행 결과
2.8 Queue
- 선입선출(FIFO, first in first out)
ex) 프린터 출력 대기열, BFS
- 데이터 추가(Enqueue), 꺼내기(Dequeue), 큐 공간 확인 동작으로 이뤄진다.
- Queue는 Stack과 다르게 인터페이스로 구현되어 있기 때문에 객체를 만들 수 없다.
-> <다형성>
-> Queue queuue = new LinkedList();를 이용한다.
Ex 1) ArrayList를 이용해서 Queue 구현하기
- list.remove(0); 지우려는 데이터의 index를 매개변수로 넣는다.
<hide/>
// Practice1
// ArrayList 를 이용한 큐 구현
import java.util.ArrayList;
class MyQueue1 {
ArrayList list;
MyQueue1() {
this.list = new ArrayList();
}
public boolean isEmpty() {
return list.size() == 0;
}
public void push(int data) {
list.add(data);
}
public Integer pop() {
if(list.isEmpty()){
System.out.println("List is empty!");
return null;
}
int data = (int) list.get(0);
list.remove(0);
return data;
}
public Integer peek() {
if(list.isEmpty()){
System.out.println("List is empty!");
return null;
}
return (int) list.get(0);
}
public void printQueue() {
System.out.println(list);
}
}
public class Practice1 {
public static void main(String[] args) {
// Test code
MyQueue1 myQueue = new MyQueue1();
myQueue.push(1);
myQueue.push(2);
myQueue.push(3);
myQueue.push(4);
myQueue.push(5);
myQueue.printQueue(); // 1, 2, 3, 4, 5
System.out.println(myQueue.peek()); // 1
myQueue.printQueue(); // 1, 2, 3, 4, 5
System.out.println(myQueue.pop()); // 1
myQueue.printQueue(); // 2, 3, 4, 5
System.out.println(myQueue.pop()); // 2
myQueue.printQueue(); // 3, 4, 5
System.out.println(myQueue.pop());
System.out.println(myQueue.pop());
System.out.println(myQueue.pop());
myQueue.printQueue();
}
}Note) 실행 결과
Ex 2) 배열을 이용해서 Circle Queue 구현하기 - 원형 큐
- 인덱스 0에는 값을 비워둔다.
- 원형 큐 관리를 위해 배열의 사이즈는 매개변수로 들어온 값에 1을 더한 값으로 정한다.(5 + 1)
- enqueue를 할 때는 rear값만 변하고 front값은 변하지 않는다.
<hide/>
// Practice2
// 배열을 이용한 기본 큐 직접 구현 (원형 큐)
class MyQueue2 {
int[] arr;
int front = 0;
int rear = 0;
MyQueue2(int size) {
arr = new int[size + 1];
// 원형 큐 관리를 위해서 front자리를 비워둔다.
}
public boolean isEmpty() {
return rear == front;
}
public boolean isFull() {
return (rear + 1) % arr.length == front;
}
public void enqueue(int data) {
if(isFull()){
System.out.println("Queue is full!");
return;
}
rear = (rear + 1) % arr.length;
arr[rear] = data;
}
public Integer dequeue() {
if(isEmpty()){
System.out.println("Queue is empty!");
return null;
}
front = (front + 1) % arr.length;
return arr[front];
}
public void printQueue() {
int start = (front + 1) % arr.length;
int end = (rear + 1) % arr.length;
for(int i = start; i != end; i = (i + 1) % arr.length){
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
public class Practice2 {
public static void main(String[] args) {
// Test code
MyQueue2 myQueue = new MyQueue2(5);
myQueue.enqueue(1);
myQueue.enqueue(2);
myQueue.enqueue(3);
myQueue.enqueue(4);
myQueue.enqueue(5);
myQueue.enqueue(6); // Queue is full!
myQueue.printQueue(); // 1, 2, 3, 4, 5
System.out.println(myQueue.dequeue()); // 1
myQueue.printQueue(); // 2, 3, 4, 5
System.out.println(myQueue.dequeue()); // 2
myQueue.printQueue(); // 3, 4, 5
myQueue.enqueue(6);
myQueue.enqueue(7);
myQueue.printQueue(); // 3, 4, 5, 6, 7
System.out.println(myQueue.dequeue()); // 3
System.out.println(myQueue.dequeue()); // 4
System.out.println(myQueue.dequeue()); // 5
myQueue.printQueue(); // 6, 7
System.out.println(myQueue.dequeue()); // 6
System.out.println(myQueue.dequeue()); // 7
myQueue.dequeue(); // Queue is empty!
}
}Note) 실행 결과
2.9 Queue 문제 풀이
Ex 1) 카드 섞기 - 1 ~ N 까지 번호로 구성된 N개의 카드가 있다. (1번: 위, N번: 가장 아래)
(1) 가장 위의 카드는 버린다.
(2) 그 다음 위의 카드는 가장아래에 다시 넣는다. 카드가 한 장 남을 때까지 반복했을 때, 마지막 카드 구하기
- intstream을 이용해서 하나씩 큐에 넣을 수 있다.
- 반환할 때, poll()이 아닌 remove()를 쓸 수도 있따.
IntStream.range(1, N + 1).forEach(x -> queue.add(x));<hide/>
// Practice1
// 카드 섞기
// 1부터 N 까지의 번호로 구성된 N장의 카드가 있다.
// 1번 카드가 가장 위에 그리고 N번 카드는 가장 아래의 상태로 카드가 순서대로 쌓여있다.
// 아래의 동작을 카드 한 장만 남을 때까지 반복했을 때, 가장 마지막 남는 카드 번호를 출력하시오.
// 1. 가장 위의 카드는 버린다.
// 2. 그 다음 위의 카드는 쌓여 있는 카드의 가장 아래에 다시 넣는다.
// 예시 입력)
// N = 4
// 결과: 4
// N = 7
// 결과: 6
import javax.swing.plaf.LabelUI;
import java.util.LinkedList;
import java.util.Queue;
import java.util.stream.IntStream;
public class Practice1 {
public static int findLastCard(int N) {
Queue queue = new LinkedList();
IntStream.range(1, N + 1).forEach(x -> queue.add(x));
while(queue.size() != 1){
queue.poll();
queue.add(queue.poll());
}
return (int) queue.poll();
}
public static void main(String[] args) {
// Test code
System.out.println(findLastCard(4)); // 4
System.out.println(findLastCard(7)); // 6
System.out.println(findLastCard(9)); // 2
}
}Note) 실행 결과
Ex 2) 요세푸스 순열 - Josephus Permutation
MySol)
<hide/>
// Practice2
// 요세푸스 문제
// N과 K가 주어졌을 때 (N, K) 요세푸스 순열을 구하시오.
// N과 K는 N >= K 를 만족하는 양의 정수이다.
// 1부터 N 번까지 N명이 순서대로 원을 이루어 모여 있다.
// 이 모임에서 원을 따라 순서대로 K번째 사람을 제외한다.
// 모든 사람이 제외될 때까지 반복하며 이 때, 제외되는 순서가 요세푸스 순열이다.
// 예시 입력
// 입력: N = 5, K = 2
// 결과: 2, 4, 1, 5, 3
// 입력: N = 7, K = 3
// 결과: 3, 6, 2, 7, 5, 1, 4
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.stream.IntStream;
public class Practice2 {
public static ArrayList getJosephusPermutation(int N, int K) {
Queue queue = new LinkedList();
ArrayList<Integer> result = new ArrayList<>();
IntStream.range(1, N + 1).forEach(x -> queue.add(x));
while(!queue.isEmpty()){
for(int i = 1; i < K; ++i){
queue.add(queue.poll());
}
result.add((int) queue.poll());
}
return result;
}
public static void main(String[] args) {
// Test code
System.out.println(getJosephusPermutation(5, 2));
System.out.println(getJosephusPermutation(7, 3));
}
}Note) 실행 결과
2.10 Deque(Doubly ended Queue, 데크, 디큐)
Def) Deque: 양쪽에서 삽입과 삭제가 모두 가능한 자료 구조 (Stack + Queue)
- 일부 기능을 제한하여 용도에 맞게 변형 가능
- add / remove -> 공간이 부족하거나 제거할 데이터가 없을 때, 예외를 발생시킨다.
- offer / poll -> 공간이 부족하거나 제거할 데이터가 없을 때, null이나 false를 반환시킨다.
1) Scroll(입력 제한 데트): 한 쪽(rear 또는 front)의 입력을 제한한 데크
2) Shelf(출력 제한 데크): 한 쪽의 출력을 제한한 데크
Ex) Java Deque
<hide/>
// 선형 자료구조 - 데크
import java.util.ArrayDeque;
import java.util.Collection;
import java.util.Deque;
import java.util.Iterator;
public class Main {
public static void main(String[] args) {
Deque deque = new ArrayDeque();
// Front 부분 입력
deque.addFirst(1);
deque.addFirst(2);
deque.addFirst(3);
System.out.println(deque);
// Rear 부분 입력
deque.addLast(10);
deque.addLast(20);
deque.addLast(30);
System.out.println(deque);
// Front 부분 출력
System.out.println(deque.removeFirst());
System.out.println(deque);
// Rear 부분 출력
System.out.println(deque.removeLast());
System.out.println(deque);
System.out.println(deque.removeLast());
System.out.println(deque.removeLast());
System.out.println(deque.removeLast());
System.out.println(deque.removeLast());
System.out.println(deque);
System.out.println(deque.pollLast());
System.out.println(deque.pollLast());
}
}Note) 실행 결과
Ex 1) ArrayList를 이용한 Deque
<hide/>
// Practice1
// ArrayList 를 이용한 데크 구현
import java.util.ArrayList;
class MyDeque1 {
ArrayList list;
MyDeque1() {
list = new ArrayList();
}
public boolean isEmpty() {
if(list.size() == 0){
System.out.println("Deque is empty!");
return true;
}
return false;
}
public void addFirst(int data) {
list.add(0, data);
}
public void addLast(int data) {
list.add(list.size(), data);
}
public Integer removeFirst() {
if(list.isEmpty()){
System.out.println("Deque is empty!");
return null;
}
int data = (int) list.get(0);
list.remove(0);
return data;
}
public Integer removeLast() {
if(this.isEmpty()){
System.out.println("Deque is empty!");
return null;
}
int data = (int) list.get(list.size() - 1);
list.remove(list.size() - 1);
return data;
}
public void printDeque() {
System.out.println(list);
}
}
public class Practice1 {
public static void main(String[] args) {
// Test code
MyDeque1 myDeque = new MyDeque1();
// Front 부분 입력
myDeque.addFirst(1);
myDeque.addFirst(2);
myDeque.addFirst(3);
myDeque.printDeque(); // 3 2 1
// Rear 부분 입력
myDeque.addLast(10);
myDeque.addLast(20);
myDeque.addLast(30);
myDeque.printDeque(); // 3 2 1 10 20 30
// Front 부분 출력
System.out.println(myDeque.removeFirst()); // 3
myDeque.printDeque(); // 2 1 10 20 30
// Rear 부분 출력
System.out.println(myDeque.removeLast()); // 30
myDeque.printDeque(); // 2 1 10 20
System.out.println(myDeque.removeLast()); // 20
System.out.println(myDeque.removeLast()); // 10
System.out.println(myDeque.removeLast()); // 1
System.out.println(myDeque.removeLast()); // 2
myDeque.printDeque();
}
}Note) 실행 결과
Ex 2) 배열을 이용한 Deque
<hide/>
// Practice2
// 배열을 이용한 기본 데크 직접 구현
class MyDeque2 {
int [] arr;
int front = 0;
int rear = 0;
MyDeque2(int size) {
arr = new int[size + 1]; // 원형으로 만들것이기 때문에 + 1
}
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
return (rear + 1) % arr.length == front;
}
public void addFirst(int data) {
if(this.isFull() == true) {
System.out.println("Deque is full!");
return;
}
arr[front] = data;
front = (front - 1 + arr.length) % arr.length; // 나머지가 음수가 되는 것을 막는다.
return;
}
public void addLast(int data) {
if(this.isFull()){
System.out.println("Deque is full!");
return;
}
rear = (rear + 1) % arr.length;
arr[rear] = data;
}
public Integer removeFirst() {
if(this.isEmpty()){
System.out.println("Deque is empty!");
return null;
}
front = (front + 1) % arr.length;
return arr[front];
}
public Integer removeLast() {
if(this.isEmpty()){
System.out.println("Deque is empty!");
return null;
}
int data = arr[this.rear];
rear = (rear - 1 + arr.length) % arr.length; // 조정해준다.
return data;
}
public void printDeque() {
int start = (front + 1) % arr.length;
int end = (rear + 1) % arr.length;
for(int i = start; i != end; i = (i + 1) % arr.length ){
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
public class Practice2 {
public static void main(String[] args) {
// Test code
MyDeque2 myDeque = new MyDeque2(5);
// Front 부분 입력
myDeque.addFirst(1);
myDeque.addFirst(2);
myDeque.addFirst(3);
myDeque.printDeque(); // 3 2 1
// Rear 부분 입력
myDeque.addLast(10);
myDeque.addLast(20);
myDeque.addLast(30); // Deque is full!
myDeque.printDeque(); // 3 2 1 10 20
// Front 부분 출력
System.out.println(myDeque.removeFirst()); // 3
myDeque.printDeque(); // 2 1 10 20
// Rear 부분 출력
System.out.println(myDeque.removeLast()); // 20
myDeque.printDeque(); // 2 1 10
System.out.println(myDeque.removeLast()); // 10
System.out.println(myDeque.removeLast()); // 1
System.out.println(myDeque.removeLast()); // 2
System.out.println(myDeque.removeLast()); // Deque is empty!
}
}
Note) 실행 결과
2.11 Deque 문제 풀이
Ex 1) 데이터 재정렬
<hide/>
// Practice1
// 데이터 재정렬
// D_0 -> D_1 -> ... -> D_n-1 -> D_n 순으로 되어 있는 데이터를
// D_0 -> D_n -> D_1 -> D_n-1 -> ... 순이 되도록 재정렬 하시오.
// 입력 예시)
// 입력 데이터: 1 -> 2 -> 3 -> 4 -> 5
// 출력 데이터: 1 -> 5 -> 2 -> 4 -> 3
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.stream.IntStream;
public class Practice1 {
public static void reorderData(int[] arr) {
Deque deque = new ArrayDeque();
ArrayList result = new ArrayList();
IntStream.of(arr).forEach(x -> deque.addLast(x));
System.out.println(deque);
while(!deque.isEmpty()){
result.add(deque.removeFirst());
if(!deque.isEmpty()){
result.add(deque.removeLast());
}
}
System.out.println("== 정렬 전 ==");
printData(arr);
System.out.println("== 정렬 후 ==");
printData(result.stream().mapToInt(x -> (int) x).toArray());
}
public static void printData(int[] arr){
for(int i = 0; i < arr.length - 1; ++i){
System.out.print(arr[i] + " -> ");
}
System.out.println(" " + arr[arr.length - 1]);
}
public static void main(String[] args) {
// Test code
int[] arr = {1, 2, 3, 4, 5};
reorderData(arr); // 1 -> 5 -> 2 -> 4 -> 3
int[] arr2 = {1, 2, 3, 4, 5, 6, 7};
reorderData(arr2); // 1 -> 7 -> 2 -> 6 -> 3 -> 5 -> 4
}
}Note) 실행 결과
Ex 2) 팰린드롬
- deque를 이용한 팰린드롬
- remove가 아닌 pollFirst()와 pollLast()를 이용해야 데이터가 비어 있을 때, null을 반환한다.
<hide/>
// Practice2
// Palindrome 찾기
// Palindrome 이면 true, 아니면 false 를 반환하세요.
// Palindrome: 앞으로 읽어도 거꾸로 읽어도 같은 문자열
// 입출력 예시)
// 입력: a
// 결과: true
// 입력: madam
// 결과: true
// 입력: abab
// 결과: false
import java.util.ArrayDeque;
import java.util.Deque;
public class Practice2 {
public static boolean checkPalindrome(String str) {
Deque deque = new ArrayDeque();
boolean isFront = true;
boolean isPalindrome = true;
for(String s : str.split("")){
deque.addFirst(s);
}
while(!deque.isEmpty()){
String s1 = (String) deque.pollFirst(); // 데이터가 없으면 null을 반환한다.
String s2 = (String) deque.pollLast();
if(!s1.equals(s2) && s1 != null && s2 != null){
isPalindrome = false;
break;
}
}
return isPalindrome;
}
public static void main(String[] args) {
// Test code
System.out.println(checkPalindrome("a")); // true
System.out.println(checkPalindrome("aba")); // true
System.out.println(checkPalindrome("abba")); // true
System.out.println(checkPalindrome("abab")); // false
System.out.println(checkPalindrome("abcba")); // true
System.out.println(checkPalindrome("abccba")); // true
System.out.println(checkPalindrome("madam")); // true
}
}Note) 실행 결과
Ex 3) 중간에 데이터 추가하기
<hide/>
// Practice3
// 데크 변형
// 기본 데크 구조에서 중간에 데이터를 추가하는 기능을 구현하세요.
// 단, 추가적인 자료구조 생성하지 말고 구현
// 입력 예시)
// 초기 데크 상태 (size: 5)
// -> 1, 2, 3, 4
// 중간 입력: 10
// 결과 데크
// -> 1, 2, 10, 3, 4
class MyDeque {
int[] arr;
int front = 0;
int rear = 0;
MyDeque(int size) {
this.arr = new int[size + 1];
}
public boolean isEmpty() {
return this.rear == this.front;
}
public boolean isFull() {
return (this.rear + 1) % this.arr.length == this.front;
}
public void addFirst(int data) {
if (this.isFull()) {
System.out.println("Deque is full!");
return;
}
this.arr[front] = data;
this.front = (this.front - 1 + this.arr.length) % this.arr.length;
}
public void addLast(int data) {
if (this.isFull()) {
System.out.println("Deque is full!");
return;
}
this.rear = (this.rear + 1) % this.arr.length;
this.arr[this.rear] = data;
}
public void addMiddle(int data) {
if (this.isFull()) {
System.out.println("Deque is full!");
return;
}
int elements = rear - front; //데이터가 있는 부분
if (elements < 0) {
elements = elements + arr.length;
}
int mid = (rear - elements / 2 + arr.length) % arr.length + 1;
int start = (rear + 1) % arr.length;
int end = (rear - elements / 2 + arr.length) % arr.length;
for (int i = start; i != end; i = (i - 1 + arr.length) % arr.length) {
arr[i] = arr[(i - 1 + arr.length) % arr.length];
}
arr[mid] = data;
rear = (rear + 1) % arr.length;
}
public Integer removeFirst() {
if (this.isEmpty()) {
System.out.println("Deque is empty!");
return null;
}
this.front = (this.front + 1) % this.arr.length;
return this.arr[this.front];
}
public Integer removeLast() {
if (this.isEmpty()) {
System.out.println("Deque is empty!");
return null;
}
int data = this.arr[this.rear];
this.rear = (this.rear - 1 + this.arr.length) % this.arr.length;
return data;
}
public void printDeque() {
int start = (this.front + 1) % this.arr.length;
int end = (this.rear + 1) % this.arr.length;
for (int i = start; i != end; i = (i + 1) % this.arr.length) {
System.out.print(this.arr[i] + " ");
}
System.out.println();
}
}
public class Practice3 {
public static void main(String[] args) {
// Test code
MyDeque myDeque1 = new MyDeque(5);
myDeque1.addLast(1);
myDeque1.addLast(2);
myDeque1.addLast(3);
myDeque1.addLast(4);
myDeque1.printDeque();
myDeque1.addMiddle(10);
myDeque1.printDeque();
MyDeque myDeque2 = new MyDeque(5);
myDeque2.addLast(10);
myDeque2.addLast(10);
myDeque2.addLast(10);
myDeque2.addLast(10);
myDeque2.addLast(10);
myDeque2.removeFirst();
myDeque2.removeFirst();
myDeque2.removeFirst();
myDeque2.removeFirst();
myDeque2.addLast(11);
myDeque2.addLast(12);
myDeque2.addLast(13);
myDeque2.printDeque();
myDeque2.addMiddle(100);
myDeque2.printDeque();
}
}
Note) 실행 결과
Ex 4) 데크 리사이즈
<hide/>
// Practice4
// 데크 리사이즈
// 기본 데크 구조에서 데크 공간이 full 일 때 데이터를 추가하는 경우,
// 데크 공간을 2배 씩 늘려주는 코드를 작성하세요.
class MyDeque2 {
int[] arr;
int front = 0; // 첫 데이터 앞에 빈 공간
int rear = 0; // 데이터 중 가장 마지막 데이터
MyDeque2(int size) {
this.arr = new int[size + 1];
}
public boolean isEmpty() {
return this.rear == this.front;
}
public boolean isFull() {
return (this.rear + 1) % this.arr.length == this.front;
}
public void increaseSize() {
System.out.println("MyDeque2.increaseSize");
int[] arrtmp = this.arr.clone();
arr = new int[arr.length * 2];
int start = (this.front + 1) % arrtmp.length;
int end = (this.rear + 1) % arrtmp.length;
int idx = 1;
for(int i = start; i != end; i = (i + 1) % arrtmp.length){
this.arr[idx++] = arrtmp[i];
}
front = 0;
rear = idx - 1;
}
public void addFirst(int data) {
if (this.isFull()) {
increaseSize();
}
this.arr[front] = data;
this.front = (this.front - 1 + this.arr.length) % this.arr.length;
}
public void addLast(int data) {
if (this.isFull()) {
increaseSize();
}
this.rear = (this.rear + 1) % this.arr.length;
this.arr[this.rear] = data;
}
public Integer removeFirst() {
if (this.isEmpty()) {
System.out.println("Deque is empty!");
return null;
}
this.front = (this.front + 1) % this.arr.length;
return this.arr[this.front];
}
public Integer removeLast() {
if (this.isEmpty()) {
System.out.println("Deque is empty!");
return null;
}
int data = this.arr[this.rear];
this.rear = (this.rear - 1 + this.arr.length) % this.arr.length;
return data;
}
public void printDeque() {
int start = (this.front + 1) % this.arr.length;
int end = (this.rear + 1) % this.arr.length;
for (int i = start; i != end; i = (i + 1) % this.arr.length) {
System.out.print(this.arr[i] + " ");
}
System.out.println();
}
}
public class Practice4 {
public static void main(String[] args) {
// Test code
MyDeque2 myDeque = new MyDeque2(5);
myDeque.addLast(1);
myDeque.addLast(2);
myDeque.addLast(3);
myDeque.addLast(4);
myDeque.addLast(5);
myDeque.printDeque();
myDeque.addLast(6);
myDeque.addLast(7);
myDeque.addLast(8);
myDeque.addLast(9);
myDeque.addLast(10);
myDeque.printDeque();
myDeque.removeLast();
myDeque.removeLast();
myDeque.addFirst(100);
myDeque.addFirst(200);
myDeque.printDeque();
myDeque.addFirst(300);
myDeque.addFirst(400);
myDeque.addFirst(500);
myDeque.printDeque();
}
}
Note) 실행 결과
2.12 해시 테이블(Hash Table)
Def) Hash Table(해시 맵, 해시 표): 키와 값을 대응시켜 저장하는 데이터 구조, 키를 통해 데이터에 빠르게 접근 가능하다
- 해싱: 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정
- 키(key): 해시 테이블 접근을 위한 입력 값
- 해시 함수: 키를 해시 값으로 매핑하는 연산
- 해시 값: 해시 테이블의 인덱스
- 해시 테이블: 키와 값을 연관시켜 저장하는 데이터 구조
Note) 해시 충돌: 해시테이블의 같으 ㄴ공간에 서로 다른 값을 저자하려는 경우
- 서로 다은 키의 해시 함수를 통해 해시 값이 동일한 경우
- 해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있다.
1) 개방 주소법(Open Address): 충돌 시 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장한다.
-> hash와 value가 1:1 관계를 유지한다.
-> 비어 있는 공간 탐색 방법에 따른 분류(선형 탐사법, 제곱 탐사법, 이중 해싱)
(1) 선형 탐사법(Linear Probing): 빈 공간을 순차적으로 탐사하는 방법
- 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사
- 일차 군집화 문제 발생 (반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생한다.)
(2) 제곱 탐사법(Quarratic Probing): 빈 공간을 n제곱만큼의 간견을 두고 탐사하는 방법
- 충돌 발생 지점 부터 이후의 빈 공간을 n제곱 간격으로 탐사한다.
- 일차 군집화 문제 일부 보완
- 이차 군집화 문제 발생 가능성
(3) 이중 해싱(Double Hashing): 해시 함수를 이중으로 사용
- 해시 함수1(최초 해시를 구할 때, 사용) / 해시함수2(충돌 발생 시, 탐사 이동 간격을 구할 때 사용한다.)
- 선형탐사, 제곱탐사에 비해 데이터가 골고루 분포된다.
2) 분리 연결법(Seperate Chaining): 해시 테이블을 연결 리스트로 구성한다.
- 충돌 발생 시, 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결 리스트를 이용해서 해당 테이블에 데이터를 연결한다.
Ex) hash table
<hide/>
// 선형 자료구조 - 해시 테이블
import java.util.Hashtable;
import java.util.Map;
public class Main {
// 해시 함수
public static int getHash(int key){
return key % 5;
}
public static void main(String[] args) {
// 기본 해시 테이블 사용 방법
Hashtable<String, Integer> ht = new Hashtable();
ht.put("key1", 10);
ht.put("key2", 20);
ht.put("key3", 30);
ht.put("key3", 50);
for(Map.Entry<String, Integer> item: ht.entrySet()){
System.out.println(item.getKey() + " - " + item.getValue());
}
// 해시 충돌 케이스 (해시 함수 사용)
Hashtable<Integer, Integer> ht2 = new Hashtable();
ht2.put(getHash(1), 10);
ht2.put(getHash(2), 20);
ht2.put(getHash(3), 30);
ht2.put(getHash(4), 40);
ht2.put(getHash(5), 50);
System.out.println("== 충돌 전 ==");
for(Map.Entry<Integer, Integer> item: ht2.entrySet()){
System.out.println(item.getKey() + " - " + item.getValue());
}
System.out.println("== 충돌 후 ==");
ht2.put(getHash(6), 60);
for(Map.Entry<Integer, Integer> item: ht2.entrySet()){
System.out.println(item.getKey() + " - " + item.getValue());
}
}
}Note) 실행 결과
Ex 1) 해시테이블을 배열로 구현하기
<hide/>
// Practice1
// 해시 테이블 배열로 직접 구현
class MyHashTable{
Integer[] table;
int elemCnt;
MyHashTable(){}
MyHashTable(int size){
table = new Integer[size];
elemCnt = 0;
}
public int getHash(int key){
return key % table.length;
}
public void setValue(int key, int data){
int idx = this.getHash(key);
this.table[idx] = data;
++this.elemCnt;
}
public int getValue(int key){
int idx = getHash(key);
return table[idx];
}
public void removeValue(int key) {
int idx = getHash(key);
table[idx] = null;
--elemCnt;
}
public void printHashTable(){
System.out.println("== Hash Table ==");
for(int i = 0;i < table.length; ++i){
System.out.println(i + " : " + table[i]);
}
}
}
public class Practice1 {
public static void main(String[] args) {
// Test code
MyHashTable ht = new MyHashTable(7);
ht.setValue(1, 1);
ht.setValue(2, 2);
ht.setValue(3, 3);
ht.setValue(4, 4);
ht.setValue(5, 5);
ht.printHashTable();
ht.setValue(8, 6);
ht.printHashTable();
}
}Note) 실행 결과
- 8을 7로 나눈 나머지는 1이기 때문에
- setvalue(8, 6)은 hash 1에 6을 넣는 것과 같은 충돌이 일어난다. 데이터가 바뀐다.
Ex 2) 선형 탐사법
<hide/>
// Practice2
// 해시 충돌 해결 - 개방 주소법 (선형 탐사법)
class MyHashTable2 extends MyHashTable {
MyHashTable2(int size) {
super(size);
}
public void setValue(int key, int data) {
int idx = this.getHash(key);
if(this.elemCnt == this.table.length){
System.out.println("Hash table is full!");
return;
}else if(this.table[idx] == null){
this.table[idx] = data;
}else{
int newIdx = idx;
while(true) {
newIdx = (newIdx + 1) % this.table.length;
if (this.table[newIdx] == null) {
break;
}
}
this.table[newIdx] = data;
}
++elemCnt;
}
}
public class Practice2 {
public static void main(String[] args) {
// Test code
MyHashTable2 ht = new MyHashTable2(5);
ht.setValue(1, 1);
ht.setValue(3, 3);
ht.printHashTable();
ht.setValue(1, 10);
ht.printHashTable();
ht.setValue(1, 20);
ht.setValue(1, 30);
ht.setValue(1, 40);
ht.printHashTable();
}
}Note) 실행 결과
Ex 3) 해시 충돌 해결 - 개방 주소법(제곱 탐사법)
<hide/>
// Practice3
// 해시 충돌 해결 - 개방 주소법 (제곱 탐사법)
class MyHashTable3 extends MyHashTable {
MyHashTable3(int size) {
super(size);
}
public void setValue(int key, int data) {
int idx = this.getHash(key);
if(this.elemCnt == this.table.length){
System.out.println("Hash table is full!");
return;
}else if(this.table[idx] == null){
this.table[idx] = data;
}else{
int newIdx = idx;
int cnt = 0;
while(true){
newIdx = (newIdx + (int) Math.pow(2, cnt)) % this.table.length;
if(this.table[newIdx] == null){
break;
}
++cnt; // 충돌할 때마다 증가
}
this.table[newIdx] = data;
}
++this.elemCnt;
}
}
public class Practice3 {
public static void main(String[] args) {
// Test code
MyHashTable3 ht = new MyHashTable3(11);
ht.setValue(1, 10);
ht.setValue(2, 20);
ht.setValue(4, 40);
ht.printHashTable();
ht.setValue(1, 100);
ht.printHashTable();
ht.setValue(1, 200);
ht.setValue(1, 300);
ht.setValue(1, 400);
ht.printHashTable();
}
}Note) 실행 결과
Ex 4) 해시 충돌 해결 - 개방 주소법 (이중 해싱)
<hide/>
// Practice4
// 해시 충돌 해결 - 개방 주소법 (이중 해싱)
class MyHashTable4 extends MyHashTable {
int c ; // 즉, getHashC의 결과값
MyHashTable4(int size){
super(size); // table = new Integer[size]
this.c = this.getHashC(size); // 11보다 작은 최대의 소수 7 = c
}
public int getHashC(int size){ //getHaahC(11) = 7
int c = 0;
if(size <= 2){
return size;
}
for(int i = size - 1; i > 2; --i){
boolean isPrime = true;
for(int j = 2; j < i; ++j){
if(i % j == 0){ // i가 합성수일 때 안쪽 for문 빠져나가고 아래 if문 건너뛰고 다음 i에 대해 바깥 for문을 실행한다.
isPrime = false;
break;
}
}
if(isPrime == true){ // i가 소수일 때, 안쪽 for문을 돌고 여기 if문까지 들어온다.
c = i;
break; // 바깥 for문을 빠져나온다.
}
}
return c; // 즉, c는 i보다 작은 수 중에서 가장 큰 소수이다.
}
public int getHash2(int key){ // size가 11일 때, getHash2(key)는 key를 7로 나눈 나머지에 1을 더한 값이다.
int hash = 1 + key % this.c;
return hash;
}
public void setValue(int key, int data) {
int idx = getHash(key);
if(elemCnt == table.length){
System.out.println("Table is full!");
return;
}else if(table[idx] == null) {
table[idx] = data;
}else{
int newIdx = idx; // 초기값 idx = 1;
int cnt = 1;
while(true){
System.out.printf("%nkey = %d, data = %d %n", key, data);
System.out.printf("newIdx = (%d + %d * %d) %% %d %n", newIdx, getHash2(newIdx), cnt, table.length);
newIdx = (newIdx + getHash2(newIdx) * cnt) % table.length;
System.out.printf("newIdx = %d %n", newIdx );
if(table[newIdx] == null){
System.out.printf(" result: table[%d] = %d %n", newIdx, data);
break;
}
++cnt;
}
table[newIdx] = data;
}
++elemCnt;
}
}
public class Practice4 {
public static void main(String[] args) {
// Test code
MyHashTable4 ht = new MyHashTable4(11); // 11보다 작은 가장 큰 소수 getHashC(11) = 7
ht.setValue(1, 10);
ht.setValue(2, 20);
ht.setValue(3, 30);
ht.printHashTable();
ht.setValue(1, 100);
ht.setValue(1, 200);
ht.setValue(1, 300);
ht.printHashTable();
}
}Note) 실행 결과
Ex 5) 해시 충돌 해결 - 분리 연결법
<hide/>
// Practice5
// 해시 충돌 해결 - 분리 연결법
import java.util.List;
class Node {
int data;
int key;
Node next;
Node() {}
Node(int key, int data, Node next) {
this.key = key;
this.data = data;
this.next = next;
}
}
class LinkedList {
Node head;
LinkedList() {}
LinkedList(Node node) {
this.head = node;
}
public boolean isEmpty() {
return this.head == null;
}
public void addData(int key, int data) {
if(isEmpty()){
this.head = new Node(key, data, null);
return;
}
Node cur = this.head;
while(cur.next != null){
cur = cur.next;
}
cur.next = new Node(key, data, null);
}
public void removeData(int data) { // 키를 가지고 찾아서 데이터를 지운다.
if(isEmpty()){
System.out.println("List is empty!");
return;
}
Node cur = this.head;
Node pre = cur;
while(cur != null){
if(cur.key == data){ // 삭제하려는 값을 찾은 경우
if(cur == this.head){ // 찾으려는 데이터가 리스트 가장 첫 원소
this.head = cur.next;
} else {
pre.next = cur.next;
}
break;
}
pre = cur;
cur = cur.next;
}
}
public Integer findData(int key) { // key를 넣으면 data를 반환한다.
// removeData랑 findData는 isEmpty()
// key 값이 있는지 확인해보고 있으면 노드의 data를 반환한다.
if(isEmpty()){
System.out.println("List is empty!");
return null;
}
Node cur = this.head;
while(cur != null){
if(cur.key == key){
return cur.data;
}
cur = cur.next;
}
System.out.println("Data not found!");
return null;
}
public void showData() {
if(isEmpty()){
System.out.println("List is empty!");
return;
}
Node cur = this.head;
while(cur != null){
System.out.print(cur.data + " " );
cur = cur.next;
}
System.out.println();
}
}
class MyHashTable5 {
LinkedList[] table;
MyHashTable5(int size){
table = new LinkedList[size];
for(int i = 0; i < table.length; ++i){
table[i] = new LinkedList(null);
}
}
public int getHash(int key){
return key % table.length; // 11로 나눠서 나머지 구하기
}
public void setValue(int key, int data) {
int idx = getHash(key);
table[idx].addData(key, data);
}
public int getValue(int key){
int idx = getHash(key);
return table[idx].findData(key);
}
public void removeValue(int key){ // 헷갈리는 부분..
int idx = getHash(key);
table[idx].removeData(key);
}
public void printHashTable(){
System.out.println("== Hash Table ==");
for(int i = 0;i < table.length; ++i){
System.out.print(i + " : ");
table[i].showData();
}
}
}
public class Practice5 {
public static void main(String[] args) {
// Test code
MyHashTable5 ht = new MyHashTable5(11); // ht = new LinkedList[11]
ht.setValue(1, 10);
ht.setValue(2, 20);
ht.setValue(3, 30);
ht.printHashTable();
ht.setValue(12, 11); // getHash(key)값이 1인 데이터를 리스트에 넣는다.
ht.setValue(23, 12);
ht.setValue(34, 13);
ht.setValue(13, 21); // getHash(key)값이 2인 데이터를 리스트에 넣는다.
ht.setValue(24, 22);
ht.setValue(35, 23);
ht.setValue(5, 1); // getHash(key)값이 5인 데이터를 리스트에 넣는다.
ht.setValue(16, 2);
ht.setValue(27, 3);
ht.printHashTable();
System.out.println("== key 값으로 해당 데이터 가져오기 ==");
System.out.println(ht.getValue(1)); // 데이터 반환
System.out.println(ht.getValue(12));
System.out.println("== 데이터 삭제 ==");
ht.removeValue(1);
ht.removeValue(5);
ht.removeValue(16);
ht.printHashTable();
}
}Note) 실행 결과
2.13 hash table 문제 풀이
Ex 1) Hash Table
<hide/>
// Practice1
// 해시 테이블을 이용한 수 찾기
// 주어진 첫 번째 배열을 이용하여 해시 테이블을 초기화 한 후
// 두 번째 배열이 주어졌을 때 해당 배열 내 데이터가 해시 테이블에 있는지 확인하는 코드를 작성하세요.
// 입출력 예시)
// 배열1: 1, 3, 5, 7, 9
// 배열2: 1, 2, 3, 4, 5
// 출력: True, False, True, False, True
import java.util.Hashtable;
public class Practice1 {
public static void solution(int[] arr1, int[] arr2) {
Hashtable<Integer, Integer> ht = new Hashtable<>();
for(int i = 0; i < arr1.length; ++i){
ht.put(arr1[i], arr1[i]);
}
for(int i = 0; i < arr2.length; ++i){
if(ht.containsKey(arr2[i])){
System.out.println("True");
}else{
System.out.println("False");
}
}
}
public static void main(String[] args) {
// Test code
int[] arr1 = {1, 3, 5, 7, 9};
int[] arr2 = {1, 2, 3, 4, 5};
solution(arr1, arr2);
}
}Note) 실행 결과
Ex 2) Hash Table
- 정수형 배열 numbers가 주어졌을 때, target을 구할 수 있는지 확인하는 프로그램 작성하라
- target에서 뺀 값을 key로 넣는다. (나중에 if문에서 containsKey로 비교하기 위해)
<hide/>
// Practice2
// 정수형 배열 nums 와 target 이 주어졌을 때,
// nums 에서 임의의 두 수를 더해 target 을 구할 수 있는지 확인하는 프로그램을 작성하세요.
// 두 수 의 합으로 target 을 구할 수 있으면 해당 값의 index 를 반환하고,
// 없는 경우 null 을 반환하세요.
// 입출력 예시
// nums: 7, 11, 5, 3
// target: 10
// 출력: 0, 3
// nums: 8, 3, -2
// target: 6
// 출력: 0, 2
import java.util.Arrays;
import java.util.Hashtable;
public class Practice2 {
public static int[] solution(int[] numbers, int target) {
int[] result = new int[2];
int idx = 0;
Hashtable<Integer, Integer> ht = new Hashtable<>();
for(int i = 0; i < numbers.length; ++i) {
if (ht.containsKey(numbers[i])) {
result[0] = ht.get(numbers[i]);
result[1] = i;
return result;
}
ht.put(target - numbers[i], i);
}
return null;
}
public static void main(String[] args) {
// Test code
int[] nums = {7, 11, 5, 3};
System.out.println(Arrays.toString(solution(nums, 10)));
nums = new int[]{8, 3, -2};
System.out.println(Arrays.toString(solution(nums, 6)));
nums = new int[]{1, 2, 3};
System.out.println(Arrays.toString(solution(nums, 12)));
}
}Note) 실행 결과
Ex 3) HashTable과 HashMap 비교하기
- 공통점: 둘 다 map인터페이스를 구현한 것이다.
- 차이점: key에 null 사용 여부(hashmap: 가능, hashtable: 불가능)
-> Thread safe(스레드 세이프): hashtable(o) - 멀티 스레드 환경에서 우수하다, hashmap(x) - 싱글스레드 환경에서 우수하다 .
Def) Thread safe(스레드 세이프): 멀티 스레드 프로그래밍에서 일반적으로 어떤 함수나 변수 혹은 객체가 여러 스레드로부터 동시에 접근이 이뤄져도 프로그램의 실행에 문제가 없다.
ex) SyncronizedMap, ConcurrentHashMap -> 스레드 세이프한 HashMap으로 두 가지의 장점을 모두 가진다.
<hide/>
// Practice3
// 참고 - Hashtable? HashMap?
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Map;
public class Practice3 {
public static void main(String[] args) {
//hashtable
Hashtable<Integer, Integer> ht = new Hashtable();
ht.put(0, 10);
System.out.println(ht.get(0));
// hashmap
HashMap<Integer, Integer> hm = new HashMap();
hm.put(0, 10);
System.out.println(hm.get(0));
Map<Integer, Integer> map1 = ht;
Map<Integer, Integer> map2 = hm;
System.out.println(map1.get(0));
System.out.println(map2.get(0));
// ht.put(null, -999);
// System.out.println(ht.get(null)); // hashtable에는 null을 넣을 수 없다.
hm.put(null, -999);
System.out.println(hm.get(null));
}
}Note) 실행 결과
2.14 선형 자료구조 연습문제 풀이
Ex 1) modification함수를 이용해서 배열 내 데이터 순서를 변경한다. modification 함수를 되돌리는 코드를 작성하라.
<hide/>
import java.util.Arrays;
public class Practice1 {
public static int[] solution(int[] arr) {
int[] arrNew = new int[arr.length];
int index = 0;
for (int i = 0; i < arr.length; ++i) {
for (int j = 0; j < arr.length; ++j) {
if (arrNew[index] == 0) {
break;
}
index = (index + 1) % arr.length; // 인덱스를 오른쪽으로 하나씩 이동
}
arrNew[index] = arr[i];
index = (index + arr[i]) % arr.length;
}
return arrNew;
}
public static int[] modification(int[] arr) {
int[] arrNew = new int[arr.length];
int idx = 0;
int cnt = 0;
int val = arr[idx];
while (cnt < arr.length) {
while (val == 0) {
idx = (idx + 1) % arr.length;
val = arr[idx];
}
arrNew[cnt++] = val;
arr[idx] = 0;
idx = (val + idx) % arr.length;
val = arr[idx];
}
return arrNew;
}
public static void main(String[] args) {
// Test code
// Modification test
int[] arr = {1, 3, 7, 9, 5};
int[] arrNew = modification(arr);
System.out.println(Arrays.toString(arrNew));
// Revert data
arr = new int[]{1, 3, 5, 7, 9};
int[] arrOrigin = solution(arr);
System.out.println(Arrays.toString(arrOrigin));
arr = new int[]{3, 2, 6, 8};
arrOrigin = solution(arr);
System.out.println(Arrays.toString(arrOrigin));
}
}Note) 실행 결과
Ex 2) 정수로 주어진 M * N 행렬에 대해 행렬의 원소 중에서 0이 있을 경우, 해당 원소가 위치하는 행과 열 전체 데이터를 0으로 작성하라.
Sol)
- 행렬 값이 0인 데이터에 대해 각 열과 행에 대해 boolean 값(fczero, frzero)를 true로 저장한다.
- 1행 ~ 마지막 행 , 1열~ 마지막 열을 먼저 for문으로 0으로 바꾸는 작업을 한다.
- 그 다음 0행, 0열은 firstRowZero/ firstColumnZero 를 이용해서 작업하면 된다.
<hide/>
import java.util.Arrays;
public class Practice2 {
public static void solution(int[][] matrix) {
// fisrtColumnZero의 약자
boolean fcZero = false;
boolean frZero = false;
for(int i = 0; i < matrix.length; ++i){
for(int j = 0; j < matrix[i].length; ++j){
if(matrix[i][j] == 0){
if(i == 0){ // 0행에 하나라도 0이 있으면
frZero = true; // 2번 케이스의 경우 둘 다 트루
}
if(j == 0){ // 0열에 하나라도 0이 있으면
fcZero = true; // 1번 케이스는 둘 다 거짓
}
matrix[i][0] = 0; // 인덱스 위치에 0으로 표시를 해준다.
matrix[0][j] = 0;
}
}
}
// 0행이나 0열에 (주변 애들을 바꿀 수 있는) 0이 있는 경우, 해당 줄을 모두 0으로 바꾼다.
for(int i = 1; i < matrix.length;++i){
for(int j = 1; j< matrix[i].length; ++j){
if(matrix[i][0] == 0 || matrix[0][j] == 0){
matrix[i][j] = 0;
}
}
}
// 0번째 행과 0번째 열은 앞으로 데이터를 놔둘건지, 0으로 모두 바꿀 것인지 정보가 있다.
// 0열의 행렬값을 모두 0으로 만든다.
if(fcZero){
for(int i = 0; i < matrix.length; ++i){
matrix[i][0] = 0;
}
}
// 0행의 행렬값을 모두 0으로 만든다.
if(frZero){
for(int j = 0; j < matrix[0].length; ++j){
matrix[0][j] = 0;
}
}
// 출력
for (int i = 0; i < matrix.length; ++i) {
for (int j = 0; j < matrix[0].length; ++j) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
// Test code
int[][] matrix = {{1, 1, 1},
{1, 0, 1},
{1, 1, 1}};
solution(matrix);
System.out.println();
matrix = new int[][]{{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
solution(matrix);
}
}
MySol) 만약 0이 같은 행에 두 개 있거나 같은 열에 두 개 넘게 있는 경우에는 오류가 생길지도 모르겠다.. 확인할 부분
<hide/>
import java.util.Arrays;
public class Practice2 {
public static void solution(int[][] matrix) {
boolean[][] visited = new boolean[matrix.length][matrix.length];
for(int i = 0; i < matrix.length; ++i) {
for (int j = 0; j < matrix[0].length; ++j) {
if (matrix[i][j] == 0 && visited[i][j] == false) {
visited[i][j] = true;
for (int x = i; x < i + 1; ++x) {
for (int y = 0; y < matrix[0].length; ++y) {
visited[x][y] = true;
matrix[x][y] = 0;
}
}
for (int x = 0; x < matrix.length; ++x) {
for (int y = j; y < j + 1; ++y) {
visited[x][y] = true;
matrix[x][y] = 0;
}
}
}
}
}
for (int i = 0; i < matrix.length; ++i) {
for (int j = 0; j < matrix[0].length; ++j) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
// Test code
int[][] matrix = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
solution(matrix);
System.out.println();
matrix = new int[][]{{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
solution(matrix);
}
}
Note) 실행 결과
Ex 3) 1~N번 까지 N개의 풍선이 원형으로 놓여 있고 i번 풍선의 오른쪽에는 i + 1번 풍선이 있고 왼쪽에는i -1번 풍선이 있다.
- 처음에는 1번 풍선을 터뜨리고 풍선안에 있는 종이를 꺼내서 그 종이에 적힌 값만큼 이동하여 다음 풍선을 터뜨린다.
- 이미 터뜨린 풍선은 제외하고 이동한다.
- 풍선이 터지는 순서대로 인덱스 출력
<hide/>
class Node{
int data;
int cmd; // 어디로 이동할 지
boolean visited;
Node next;
Node prev;
public Node(int data, int cmd, boolean visited, Node next, Node prev) {
this.data = data;
this.cmd = cmd;
this.visited = visited;
this.next = next;
this.prev = prev;
}
}
// 원형 연결 리스트
class LinkedListC{
Node head;
public void add(int data, int cmd){
if(this.head == null){
this.head = new Node(data, cmd, false, null, null );
this.head.next = this.head;
this.head.prev = this.head;
}else{
Node cur = this.head;
while(cur.next != this.head){
cur = cur.next;
}
cur.next = new Node(data, cmd, false, cur.next, cur);
this.head.prev = cur.next;
}
}
}
public class Practice3 {
public static void solution(int[] data) {
LinkedListC linkedList = new LinkedListC();
for(int i = 0; i < data.length ; ++i ){
linkedList.add(i + 1, data[i]);
}
Node cur = linkedList.head;
int visitCnt = 0; // 몇개가 터졌는지
int cmd = 0;
while(visitCnt != data.length){ // (첫 번째, 두 번째, .. , 다섯 번째 연산)
int cnt = 0;
while( cnt != Math.abs(cmd)){ // cmd의 절댓값 만큼 이동한다.
if(cmd > 0){
cur = cur.next; // 이동 명령(배열의 원소)이 양수일 때, 우측 이동
}else{
cur = cur.prev;
}
if(cur.visited == false) { // 방문하지 않은 곳만
++cnt; // n번째 연산에서 몇 칸 이동했는지 센다.
}
}
// cnt == |cmd|가 됐을 때
System.out.println(cur.data + " "); // 방문한 곳의 data
cur.visited = true;
++visitCnt;
cmd = cur.next.cmd;
}
}
public static void main(String[] args) {
int[] balloon = {3, 2, 1, -3, -1};
solution(balloon);
System.out.println();
balloon = new int[]{3, 2, -1, -2};
solution(balloon);
}
}Note) 실행 결과
Ex 4) 괄호 짝 검사, 세 종류의 괄호가 있다.
- 여는 괄호의 순서에 맞춰 닫는 괄호의 순서도 맞아야한다.
- 스택 하나만 가지고 풀 수 있다.
- stack과 map의 성질을 함께 이동한다.
<hide/>
import java.util.HashMap;
import java.util.Stack;
public class Practice4 {
public static void solution(String str) {
Stack<String> stack = new Stack<>();
boolean checkFlag = true;
HashMap<String, String> map = new HashMap<>();
map.put("(", ")");
map.put("{", "}");
map.put("[", "]");
for(String s : str.split("")){
if(map.containsKey(s)){ // 앞 괄호가 있으면
stack.push(s);
}else if(map.containsValue(s)){ // 뒷 괄호가 있으면
if (stack.isEmpty()) {
checkFlag = false;
break;
}else{
String cur = stack.pop();
if(!s.equals(map.get(cur))){
checkFlag = false;
break;
}
}
}
}
if( checkFlag && stack.isEmpty()){
System.out.println("PASS");
return;
}
System.out.println("FAIL");
}
public static void main(String[] args) {
// Test code
solution("[yyyy]-[mm]-[dd]"); // Pass
solution("System.out.println(arr[0][1))"); // FAIL
solution("Support [Java or Python(3.x)]"); // PASS
solution("([[{}])"); // FAIL
}
}Note) 실행 결과
Ex 5) Dummy - 도스게임
<hide/>
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Practice5 {
public static Integer solution(int n, int k, int l, ArrayList<ArrayList> apples, Queue<ArrayList> moves) {
int[][] board = new int[n + 1][n + 1];
// 사과 정보를 업데이트
for(ArrayList item: apples){
board[(int)item.get(0)][(int)item.get(1)] = 1;
}
// 스네이크의 초기 위치값
Queue<ArrayList> snake = new LinkedList<>();
snake.add(new ArrayList(Arrays.asList(1, 1))); // 객체 생성을 먼저 하지않고 일단 add에 넣는다.
// list로 된 list direcion에 네 가지 방향을 넣는다.
// 일단 처음에는 +0행, +1열 만큼씩, 즉 오른쪽으로 이동한다.
// 나중에 나오는 didx를 연산하기위해서 아래 방향리스트 네개의 순서를 고정시킨다.
ArrayList<ArrayList> direction = new ArrayList<>();
direction.add(new ArrayList(Arrays.asList(0, 1)));
direction.add(new ArrayList(Arrays.asList(1, 0)));
direction.add(new ArrayList(Arrays.asList(0, -1)));
direction.add(new ArrayList(Arrays.asList(-1, 0)));
int dIdx = 0;
int score = 0;
int x = 1; // 출발하는 위치
int y = 1;
// score 회 만큼 while문을 실행하는 건가???
while(true){ // 스네이크 정보 업데이트
score += 1; // 시간 체크 //????????
// direction 리스트 중에서 didx 번째 리스트의 행과 열 => x, y
x += (int) direction.get(dIdx).get(0); // 행
y += (int) direction.get(dIdx).get(1); // 열
if(1 <= x && x <= n && 1 <= y && y <= n){ // 벽에 부딪히지 않는 범위 내
ArrayList cur = new ArrayList(Arrays.asList(x, y)); // 현재 위치 정보
if(snake.contains(cur)){ // 현재 이동한 좌표가 Queue에도 있다는 건 이미 몸체라는 뜻 => 게임 종료
return score;
}
snake.add(cur); // 새로운 위치를 queue에 더하기
if(board[x][y] == 0){ // 사과 없을 때
snake.poll(); // 위에서 add한 cur을 poll()한다.
}else { // 사과 있을 때
board[x][y] = 0; // 사과 없어진다.
}
}else{ // 벽에 부딪혔을 때
return score;
}
// moves 큐에 원소가 있으면 계속 실행
if(moves.size() > 0 && score == (int)moves.peek().get(0)) {
// while문에서 score를 1씩 더하다가 moves의 0열 값이랑 같은 경우에만 실행한다.
if((char) moves.peek().get(1) == 'D') { //방향 바꿔준다.
dIdx = (dIdx + 1) % 4; //오른쪽 90도로 움직인다.
moves.poll();
}else if((char) moves.peek().get(1) == 'L'){ // 왼쪽인 경우
dIdx = (dIdx - 1) % 4; //
moves.poll();
}
}
}// while문 종료
}
public static void main(String[] args) {
// Test code
int n = 6;
int k = 3;
int l = 3;
ArrayList<ArrayList> apples = new ArrayList();
apples.add(new ArrayList<>(Arrays.asList(3, 4)));
apples.add(new ArrayList<>(Arrays.asList(2, 5)));
apples.add(new ArrayList<>(Arrays.asList(5, 3)));
Queue<ArrayList> moves = new LinkedList();
moves.add(new ArrayList(Arrays.asList(3, 'D')));
moves.add(new ArrayList(Arrays.asList(15, 'L')));
moves.add(new ArrayList(Arrays.asList(7, 'D')));
System.out.println((solution(n, k, l, apples, moves)));
n = 10;
k = 4;
l = 4;
apples.clear();
apples.add(new ArrayList<>(Arrays.asList(1, 2)));
apples.add(new ArrayList<>(Arrays.asList(1, 3)));
apples.add(new ArrayList<>(Arrays.asList(1, 4)));
apples.add(new ArrayList<>(Arrays.asList(1, 5)));
moves.clear();
moves.add(new ArrayList(Arrays.asList(8, 'D')));
moves.add(new ArrayList(Arrays.asList(10, 'D')));
moves.add(new ArrayList(Arrays.asList(11, 'D')));
moves.add(new ArrayList(Arrays.asList(13, 'L')));
System.out.println((solution(n, k, l, apples, moves)));
n = 10;
k = 5;
l = 4;
apples.clear();
apples.add(new ArrayList<>(Arrays.asList(1, 5)));
apples.add(new ArrayList<>(Arrays.asList(1, 3)));
apples.add(new ArrayList<>(Arrays.asList(1, 2)));
apples.add(new ArrayList<>(Arrays.asList(1, 6)));
apples.add(new ArrayList<>(Arrays.asList(1, 7)));
moves.clear();
moves.add(new ArrayList(Arrays.asList(8, 'D')));
moves.add(new ArrayList(Arrays.asList(10, 'D')));
moves.add(new ArrayList(Arrays.asList(11, 'D')));
moves.add(new ArrayList(Arrays.asList(13, 'L')));
System.out.println((solution(n, k, l, apples, moves)));
}
}Note) 실행 결과
Ex 6) 프린터 중요도 인쇄
<hide/>
import java.util.LinkedList;
import java.util.Queue;
class Doc{
int no;
int priority;
public Doc(int no, int priority){
this.no = no;
this.priority = priority;
}
}
public class Practice1 {
public static void solution(int docs, int target, int[] priority) {
Queue<Doc> queue = new LinkedList<>();
// 자바에 내장된 게 아닌 직접 만든 클래스이므로 Doc객체를 하나씩 만들어서 Queue에 넣어야한다.
for(int i = 0;i < docs ; ++i){
queue.add(new Doc(i, priority[i])); // 1 1 9 1 1 1
// Doc(인덱스, 우선순위)
}
int cnt = 1;
while(true){
Doc cur = queue.poll();
Doc[] highP = queue.stream().filter(x -> x.priority > cur.priority).toArray(Doc[]::new);
System.out.printf("cur.no : %d cur.priority: %d %n", cur.no, cur.priority);
if(highP.length > 0){ // 현재 문서 보다 우선순위 높은 게 뒤에 있으니 poll해서 뒤로 보낸다.
queue.add(cur);
}else{ // cur이 최고 우선순위일 때
System.out.printf("target: %d cur.no: %d cur.priority: %d %n", target, cur.no, cur.priority);
if(target == cur.no){ // 출력대상 번호가 현재 문서의 번호일 때
System.out.println("result cnt : " + cnt);
break;
}
++cnt;
// cur이 최고 우선순위이지만 출력하려는 target이 아닐 때
// cur을 인쇄하므로 cnt증가시키고 다음 순서로 넘어간다.
System.out.println("cnt: " + cnt );
}
}
}
public static void main(String[] args) {
// Test code
int docs = 1;
int target = 0;
int[] priority = {5};
solution(docs, target, priority);
docs = 4;
target = 2;
priority = new int[]{1, 2, 3, 4};
solution(docs, target, priority);
docs = 6;
target = 0;
priority = new int[]{1, 1, 9, 1, 1, 1};
solution(docs, target, priority);
}
}Note) 실행 결과
Ex 7) 스택 수열 만들기
- 1~n까지의 숫자를 (오름차순으로) 스택에 넣었다가 뽑아 늘어놓음으로써 하나의 수열을 만든다.
- 임의의 수열이 주어졌을 때, 스택을 이용해 그 수열을 만들 수 있는지 없는지
- 원하는 수가 나왔을 때, push를 한 다음에 뺀다.
<hide/>
import java.util.ArrayList;
import java.util.Stack;
public class Practice2 {
public static void solution(int[] nums) {
Stack<Integer> stack = new Stack<>();
ArrayList<String> result = new ArrayList<>();
int idx = 0;
for(int i = 0; i < nums.length; ++i){
int num = nums[i];
if(num > idx){
for(int j = idx + 1; j < num + 1; ++j){
stack.push(j);
result.add("+");
}
idx = num;
}else if(stack.peek() != num){
System.out.println("NO");
return;
}
stack.pop();
result.add("-");
}
for(String item: result){
System.out.println(item);
}
}
public static void main(String[] args) {
int[] nums = {4, 3, 6, 8, 7, 5, 2, 1};
solution(nums);
System.out.println("=====");
nums = new int[]{1, 2, 5, 3, 4};
solution(nums);
}
}Note) 실행 결과
Ex 8) 베스트 앨범 출시
<hide/>
import java.sql.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Hashtable;
import java.util.Map;
class Song{
int no;
int play;
public Song(int no, int play){
this.no = no;
this.play = play;
}
}
public class Practice3 {
public static void solution(String[] genres, int[] plays) {
Hashtable<String, ArrayList<Song>> ht = new Hashtable<>();
for(int i = 0; i < genres.length;++i){
if(ht.containsKey(genres[i])){
ArrayList<Song> cur = ht.get(genres[i]);
int idx = -1;
for(int j = 0; j < cur.size(); ++j){
if(plays[i] > cur.get(j).play ||
plays[i] == cur.get(j).play && i < cur.get(j).no){
idx = j; // 초기화
break;
}
}
if(idx == -1){// 재생횟수가 작을 때
cur.add(new Song(i, plays[i])); // 리스트의 가장 뒤에 붙인다.
}else{
cur.add(idx, new Song(i, plays[i])); // 리스트의 idx 위치에 붙인다.
}
ht.put(genres[i], cur);
}else{ // 해당 키가 해시테이블에 없는 경우
Song s = new Song(i, plays[i]);
ht.put(genres[i], new ArrayList<>(Arrays.asList(s)));
}
}
Hashtable<String, Integer> htPlay = new Hashtable<>();
for(String item : ht.keySet()){
int sum = 0;
ArrayList<Song> cur = ht.get(item);
for(int i = 0; i < cur.size(); ++i){
sum += cur.get(i).play;
}
htPlay.put(item, sum);
}
ArrayList<Map.Entry<String, Integer>> htPlaySort = new ArrayList<>(htPlay.entrySet());
// 우변의 value들이 좌변에 저장..
htPlaySort.sort((x1, x2) -> (x2.getValue() - x1.getValue()));
for(Map.Entry<String, Integer> item: htPlaySort){
ArrayList<Song> songs = ht.get(item.getKey()); //
for(int i = 0; i < songs.size(); ++i){
System.out.print(songs.get(i).no + " ");
if(i == 1){
break;
}
}
}
System.out.println();
}
public static void main(String[] args) {
// Test code
String[] genres = {"classic", "pop", "classic", "classic", "pop"};
int[] plays = {500, 600, 150, 800, 2500};
solution(genres, plays);
}
}Note) 실행 결과: 4 1 3 0
Ex 9) 완주하지 못한 선수
- 동명이인 있는 경우가 있다.
<hide/>
import java.util.Arrays;
import java.util.Hashtable;
public class Practice4 {
public static String solution(String[] participant, String[] completion) {
String answer = "";
Hashtable<String, Integer> ht = new Hashtable<>();
for(String item: participant){
if(ht.containsKey(item)){
ht.put(item, ht.get(item) + 1);
}else{
ht.put(item, 1);
}
}
for(String item : completion){
ht.put(item, ht.get(item) - 1);
}
for(String item : participant){
if(ht.get(item) > 0){
answer = item;
break;
}
}
return answer;
}
public static void main(String[] args) {
// Test code
String[] participant = {"leo", "kiki", "eden"};
String[] completion = {"eden", "kiki"};
System.out.println(solution(participant, completion));
participant = new String[]{"marina", "josipa", "nikola", "vinko", "filipa"};
completion = new String[]{"josipa", "filipa", "marina", "nikola"};
System.out.println(solution(participant, completion));
participant = new String[]{"mislav", "stanko", "mislav", "ana"};
completion = new String[]{"stanko", "ana", "mislav"};
System.out.println(solution(participant, completion));
}
}Note) 실행 결과
Ex 10) 어피치 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매
<hide/>
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.stream.Stream;
public class Practice5 {
public static ArrayList<Integer> solution(String[] gems) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
HashSet<String> set = new HashSet<>();
Stream.of(gems).forEach(x -> set.add(x));
int n = set.size();
if(n == 1){
result.add(new ArrayList(Arrays.asList(1, 1)));
return result.get(0);
}
Hashtable<String, Integer> ht = new Hashtable();
boolean isCandidatee = false;
int left = 0;
int right = 0;
ht.put(gems[0], 1);
while(true){
if(isCandidatee == false){
right += 1;
if(right >= gems.length){
break;
}
if(ht.containsKey(gems[right]) == false){
ht.put(gems[right], 1);
}else{
ht.put(gems[right], ht.get(gems[right]) + 1);
}
if(ht.size() == n){
isCandidatee = true;
result.add(new ArrayList<>(Arrays.asList(left + 1, right + 1)));
}
}else{ //
left += 1;
int cnt = ht.get(gems[left - 1]) - 1;
if(cnt == 0){
ht.remove(gems[left - 1]); // 해당 위치에 보석을 뺀다.
isCandidatee = false; // 다시 while문으로 들어가서
}else{
ht.put(gems[left - 1], cnt);
result.add(new ArrayList<>(Arrays.asList(left + 1, right + 1)));
}
}
}
int minIdx = 0;
int minNum = Integer.MAX_VALUE;
for(int i = 0; i < result.size(); ++i){
ArrayList<Integer> cur = result.get(i);
left = cur.get(0);
right = cur.get(1);
if(right - left < minNum){
minNum = right - left;
minIdx = i;
}
}
return result.get(minIdx);
}
public static void main(String[] args) {
// Test code
String[] gems = {"DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"};
System.out.println(solution(gems));
gems = new String[]{"AA", "AB", "AC", "AA", "AC"};
System.out.println(solution(gems));
gems = new String[]{"XYZ", "XYZ", "XYZ"};
System.out.println(solution(gems));
gems = new String[]{"ZZZ", "YYY", "NNNN", "YYY", "BBB"};
System.out.println(solution(gems));
}
}Note) 실행 결과
'자료구조와 알고리듬 With Java > [zerobase] Algorithm' 카테고리의 다른 글
| Chapter 03. 비선형 자료구조 (0) | 2022.06.08 |
|---|---|
| Chapter 01. 기초 수학 [zerobase] (0) | 2022.05.22 |
| [Java 핵심 복습] (0) | 2022.05.13 |
| Part 01. 연습문제 풀이 3 [zerobase] (0) | 2022.05.12 |
| Part 01. 연습문제 풀이 2 [zerobase] (0) | 2022.05.11 |