JAVA/문제 및 디버깅표
중복제거 알고리즘 고민중
hyun9_9
2023. 11. 23. 17:18
사용하기 위해선 값이 있는지 탐색을 해봐야했다
그래서 생각 했던것이 탐색방법중 일반 검색과 이진탐색을 통해 중복값을 찾아 있으면 무시하고
없으면 저장 하도록 하면 가능하지 않을까했다
방식 1
만들고 싶은 것
방금 뽑은 숫자와 저장된 숫자들과 모두 비교하여 중복이 있다면
i를 1줄여 다시 for문의 증감식을 만났을때 i가 1이 증가하여 다시 뽑는 효과를 누릴수있다
한글 코딩
뽑은 값 저장 배열 선언(정의)
배열의 수만큼 반복문 실행(초기값 i의 역할은 저장할 배열의 인덱스로 사용)
뽑은 랜덤값 배열에 저장
과거에 뽑은 수만큼 반복
방금 뽑은 값과 과거에 뽑아 저장했던 값와 비교
만약 참이라면
현재 저장할 배열 인덱스를 뜻하는 i를 1만큼 감소한다
디버깅 표
import java.util.Random;
public class Test07 {
public static void main(String[] args) {
//일반탐색
Random rand=new Random();
int [] datas=new int [5];
int del=0;//중복 횟수 확인
for(int i=0;i<datas.length;i++) {
datas[i]=rand.nextInt(10)+1;
for(int j=0;j<i;j++) {
//방금 뽑은 숫자와 그 전에 뽑은 숫자들 비교하여 같으면 실행
if(datas[i]==datas[j]) {
del++;//중복 횟수 증가
i--;//다시 뽑기 위해 i를 감소시켜 현재 for문이 끝나고
//밖 for문 증감식(i++)을 만났을 때 같은 i가 되어 다시 뽑기가 가능해진다
}
}
}
for(int data:datas) {//forEach문
System.out.print(data+ " ");
}
System.out.println();
System.out.println("중복 제거 횟수 : "+del);
}
}
방식 2
이진 탐색 사용은 해보기
=>정렬이 되어있어야한다
정렬 후 만들고 탐색
import java.util.Random;
public class Test08 {
public static void main(String[] args) {
// 이진탐색
Random rand = new Random();
int[] datas = new int[5];
for (int i = 0; i < datas.length; i++) {
//high와 low를 알아야 하고 정렬이 되어 있어야한다
//버블 정렬
for (int j = 0; j < i-1; j++) {//0~ 현재까지 뽑은 i 만큼 정렬을 시킨다
for (int k= 0; k < i - j-1; k++) {
if (datas[k] > datas[k + 1]) {
int tmp = datas[k];
datas[k] = datas[k+1];
datas[k+1] = tmp;
}
}
}
int mid;//중간 index 값
int low=0;//배열 첫번째 index
int high=i-1;//지금까지 뽑은 배열 index
int ranNum = rand.nextInt(10) + 1;
boolean ck=true;//중복 체크
//이진 탐색
while(low <= high) {
mid = (low + high) / 2;
if(ranNum == datas[mid]) {
ck=false;//같은게 있는지 체크
i--;//다시 뽑기위해 i 감소
break;
} else if(ranNum < datas[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
if(ck) {//true가 나오면 중복이 없으므로 datas에 추가
datas[i]=ranNum;
}
}
for (int data : datas) {
System.out.print(data + " ");
}
System.out.println();
}
}
2023.11.29 수정) 마지막에 뽑은 것이 정렬 안되는 문제를 알고리즘 순서변경으로 해결
package class07;
import java.util.Random;
public class Test01 {
public static void main(String[] args) {
// TODO Auto-generated method stub
// 이진탐색
Random rand = new Random();
int[] datas = new int[5];
for (int i = 0; i < datas.length; i++) {
int mid;//중간 index 값
int low=0;//배열 첫번째 index
int high=i-1;//지금까지 뽑은 배열 index
int ranNum = rand.nextInt(5) + 1;
boolean ck=true;//중복 체크
//이진 탐색
while(low <= high) {
mid = (low + high) / 2;
if(ranNum == datas[mid]) {
ck=false;//같은게 있는지 체크
i--;//다시 뽑기위해 i 감소
break;
} else if(ranNum < datas[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
if(ck) {//true가 나오면 중복이 없으므로 datas에 추가
datas[i]=ranNum;
//버블 정렬
for (int j = 0; j < i; j++) {//0~ 현재까지 뽑은 i 만큼 정렬을 시킨다
for (int k= 0; k < i - j; k++) {
if (datas[k] > datas[k + 1]) {
int tmp = datas[k];
datas[k] = datas[k+1];
datas[k+1] = tmp;
}
}
}
}
}
for (int data : datas) {
System.out.print(data + " ");
}
System.out.println();
}
}
2023.11.30 수정) 모듈화 진행->코드 가독성 증가 (결합도 감소,응집도 증가)
import java.util.Random;
public class Test01 {
public static boolean search(int i, int ranNum, int[] datas) {
int mid;// 중간 index 값
int low = 0;// 배열 첫번째 index
int high = i - 1;// 지금까지 뽑은 배열 index
// 이진 탐색
while (low <= high) {
mid = (low + high) / 2;
if (ranNum == datas[mid]) {
break;
} else if (ranNum < datas[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
if(low>high) {
return true;
}
return false;
}
public static void sort(int i, int[] datas) {// 버블 정렬
for (int j = 0; j < i; j++) {// 0~ 현재까지 뽑은 i 만큼 정렬을 시킨다
for (int k = 0; k < i - j; k++) {
if (datas[k] > datas[k + 1]) {
int tmp = datas[k];
datas[k] = datas[k + 1];
datas[k + 1] = tmp;
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Random rand = new Random();
int[] datas = new int[5];
for (int i = 0; i < datas.length; i++) {
int ranNum = rand.nextInt(5) + 1;
if (search(i, ranNum, datas)) {// true가 나오면 중복이 없으므로 datas에 추가
datas[i] = ranNum;
sort(i, datas);
} else {
i--;// 다시 뽑기위해 i 감소
}
}
for (int data : datas) {
System.out.print(data + " ");
}
System.out.println();
}
}
방식 3
Set의 중복을 허용하지 않는 특성을 이용
set : https://www.codelatte.io/courses/java_programming_basic/51BDPYQYSJVHNR4R
set저장방법
HashSet은 HashMap을 이용하여 만들어져있다
HashMap은 map을 사용하는데 map의 특성 중 하나인 중복 key는 존재할수 없다는 특징이 있는데
이 특징을 이용하여 key를 set값으로,value에는 더미 Object를 저장하는 방식으로 데이터를 추가한다
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
public class Test09 {
public static void main(String[] args) {
Random rand=new Random();
Set<Integer> set = new HashSet<>();
while (set.size() < 5) {
int ranNum = rand.nextInt(10) + 1;
System.out.println(ranNum);
set.add(ranNum);
}
for(int data:set) {
System.out.print(data+ " ");
}
}
}
방식 4
원하는 0~n를 boolean 배열 개수 n으로 만들어 뽑힌 숫자가 있으면 true바꾼다
그럼 뽑았을때 그 숫자의 boolean 인덱스 값을 확인해봤을때
true가 나오면 중복으로 뽑은것이기에 다시 뽑기
false가 나오면 없는 것이기 때문에 저장을 하고
그 boolean 해당 인덱스의 false를 true로 변경한다
한글 코딩
뽑고 싶은 숫자의 범위를 진위형 배열로 만든다 ex)1~10사이의 값을 뽑을꺼다 boolean[10]
뽑은 값 저장 배열 선언(정의)
배열의 수만큼 반복문 실행(초기값 i의 역할은 저장할 배열의 인덱스로 사용)
뽑은 랜덤값 변수에 저장
진위형 배열[뽑은 값] = T/F 확인
만약 T라면
뽑은 랜덤 값 저장
진위형 배열[뽑은 값]= F로 변경
아니면
현재 저장할 배열 인덱스를 뜻하는 i를 1만큼 감소한다
디버깅표
import java.util.Random;
public class Test10 {
public static void main(String[] args) {
boolean [] numCk =new boolean[10];//1~10까지 뽑기때문에 진위형 배열 0~9까지 만든다 def=false
Random rand=new Random();
int [] datas=new int [5];
for(int i=0;i<datas.length;i++) {//랜덤 숫자를 datas길이 만큼 뽑는다
int ranNum =rand.nextInt(10)+1;
System.out.println(ranNum);
//방금 뽑은 숫자를 numCk(진위형 배열)index로 넣어 false가 나오면 중복x true가 나오면 중복o이 된다
if(!numCk[ranNum-1]) {//false를 Not 연산자를 이용해 true로 바꾸어 if문 실행한다
datas[i]=ranNum;//뽑은 랜덤 값 저장
numCk[ranNum-1]=true;//numCk 해당 index로 들어가 false를 true로 변환
}
else {//중복시 i 감소하여 다시 뽑기
i--;
}
}
for(int data:datas) {
System.out.print(data+ " ");
}
}
}
방식 5
재귀함수?
import java.util.Random;
public class Test11 {
public static int ran(int [] datas,int index) {
Random rand=new Random();
int random =rand.nextInt(10)+1;
datas[index]=random;//랜덤값을 datas에 저장한다
boolean ck=false;//중복체크
for(int i=0;i<index;i++) {
if(datas[i]==datas[index]) {//방금 저장한 datas와 나머지를 비교한다
ck=true;
}
}
if(ck) {//중복일겅우
System.out.println(ck);
ran(datas,index);//재호출
return 0;
}
else if(index<datas.length-1) {//dtas길이보다 작으면
ran(datas,index+1);//index 1증가 시켜 호출
return 0;
}
else return 0;
}
public static void main(String[] args) {
int [] datas=new int [5];
ran(datas,0);//초기값음 준다
for(int data:datas) {
System.out.print(data+ " ");
}
}
}
방식 6
다 뽑고 중복있으면 1개 빼고 나머지 제거하고 다시 생성 반복
import java.util.Random;
public class Test12 {
public static void main(String[] args) {
Random rand=new Random();
int [] datas=new int [5];
for(int i=0;i<datas.length;i++) {
datas[i]=rand.nextInt(10)+1;
}
for(int data:datas) {//미리 데이터를 뽑는다
System.out.print(data+ " ");
}
System.out.println();
while(true) {
boolean ck=true;//중복체크
for(int a=0;a<datas.length;a++) {
for(int i=a+1;i<datas.length;i++) {
if(datas[i]==datas[a]) {//같은게 있으면 그 자리에 다시뽑는다
datas[i]=rand.nextInt(10)+1;
ck=false;
}
}
}
if(ck)break;//중복 없으면 종료
}
for(int data:datas) {
System.out.print(data+ " ");
}
}
}