문자열 검색 풀어낸 소스 평가부탁드립니다.
조회수 860회
안녕하세요. 자바 알고리즘 - 이진검색 공부 후 구글링에서 예시 문제 비슷한거 찾아서
간단한 알고리즘 문제인것같아 공부겸 풀었는데, 아래 문제내용에 제가 푼 소스를 첨부드립니다.
코드 평가 요청드립니다. 제가 알고있는 개념선에서 했는데,
혹시 다른 효율적인 소스라던가 불필요한 내용 들어갔는지 등 평가 부탁드립니다.
[ 문제 내용 ]
부품 찾기 문제 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자.
N=5 [8, 3, 7, 9, 2]
손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다.
M=3 [5, 7, 9]
이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다.
입력
첫째 줄에 정수 N이 주어진다. (1<=N<=1,000,000) 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다. 셋째 줄에는 정수 M이 주어진다. (1<=M<=100,000) 넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. 이때 정수는 1보다 크고 10억 이하이다. 출력
첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes를, 없으면 no를 출력한다. 입력 예시
5 8 3 7 9 2 3 5 7 9 출력 예시
no yes yes
[ 제가 짠 소스 ]
import java.util.Scanner;
public class SearchTest { public static void main(String[] args) { Scanner sc = new Scanner(System.in);
int num = sc.nextInt(); //전체 부품갯수
int[] arr1 = new int[num]; //갯수만큼 배열
for(int i = 0; i < arr1.length; i++) {
arr1[i] = sc.nextInt(); //배열 값 셋팅
}
int num2 = sc.nextInt(); //손님 요구 갯수
int[] arr2 = new int[num2]; //배열 생성
for(int j = 0; j < arr2.length; j++) {
arr2[j] = sc.nextInt(); //배열 값 셋팅
}
for(int i = 0; i < arr1.length; i++) {
for(int j = 0; j < arr2.length; j++) {
if(arr2[j] == arr1[i]) //손님 요구한 값들이 있는경우
arr2[j] = 1; // 1표시
}
}
for(int rs : arr2) { //손님 요구한 갯수 만큼
System.out.print(((rs == 1) ? "yes" : "no") + " "); // 일치하여 1인것이면 "yes" 아님 "no"
}
sc.close();
}
}
1 답변
-
for(int i = 0; i < arr1.length; i++) { for(int j = 0; j < arr2.length; j++) { if(arr2[j] == arr1[i]) //손님 요구한 값들이 있는경우 arr2[j] = 1; // 1표시 } }
- 루프가 무조건 M x N 번 돌아야 하는데, 값이 일치하면
break;
하는게 더 좋습니다. arr[j]
를 재활용하시고 값이 일치하면 1을 할당하셨는데, 만약에arr[j]
값이 원래부터 1이었다면 찾지 못해도 찾은 것 처럼 결과가 나오지 않을까요?
배열을 사용하시면 값을 서치하기 위해서 최악의 경우 배열의 길이 전부를 스캔해야 합니다. (정렬된 경우는 좀 더 빠르긴 합니다.)
제 생각엔
Set
을 사용하면 더 빠른 풀이가 나올 것 같습니다.의사코드로 써보면 대충 이럴 것 같아요
Set<Integer> 재고 = new Set<>(); for (int i : arr1){ 재고.add(i); } String[] buffer = new String[arr2.length]; for (int j : arr2){ if( 재고.contain(j) ){ buffer[j] = "yes"; } else{ buffer[j] = "no"; } } : : :
Set
이나HashMap
은 매칭되는 요소를 찾는데에 매우 효율적이라서 더 빠를겁니다ps. 이진 검색하곤 좀 거리가 멀긴 합니다.
- 루프가 무조건 M x N 번 돌아야 하는데, 값이 일치하면
댓글 입력