문자열 검색 풀어낸 소스 평가부탁드립니다.

조회수 352회

안녕하세요. 자바 알고리즘 - 이진검색 공부 후 구글링에서 예시 문제 비슷한거 찾아서

간단한 알고리즘 문제인것같아 공부겸 풀었는데, 아래 문제내용에 제가 푼 소스를 첨부드립니다.

코드 평가 요청드립니다. 제가 알고있는 개념선에서 했는데,

혹시 다른 효율적인 소스라던가 불필요한 내용 들어갔는지 등 평가 부탁드립니다.


[ 문제 내용 ]

부품 찾기 문제 동빈이네 전자 매장에는 부품이 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 답변

  • 좋아요

    0

    싫어요
    채택 취소하기
        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표시
            }
        }
    
    
    1. 루프가 무조건 M x N 번 돌아야 하는데, 값이 일치하면 break; 하는게 더 좋습니다.
    2. 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. 이진 검색하곤 좀 거리가 멀긴 합니다.

    • 피드백주셔서 감사합니다. ^^ 코테준비를 위해 나아가는중인데, 잘못된 방향으로 코딩할뻔했네요 catDeveloper 2024.1.2 21:48

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)