[백준] 1920번: 수 찾기 - Java, Python

 

코딩테스트 백준 1920번: 수 찾기 문제를 풀다가 sys를 사용했음에도 시간초과가 떠서 통과한 다른 사람들의 코드를 참조하였다. 파이썬의 경우 대부분의 사람들이 이진 탐색(이분 탐색)을 사용하여 코드를 작성하였다. 이를 참조하여 코드를 작성하고 테스트를 통과했다. 이전까지 알고리즘을 배울 때는 잘 쓰이지도 않는데 왜 배워야하는지 의문점이 많았는데 코딩테스트에 직접 활용해보니 유용하다는 생각이 들었다. 

 

---

처음에 작성했던 코드 (시간 초과)

import sys

# 각각 int와 list로 입력받아 저장하기
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

M = int(sys.stdin.readline())
B = list(map(int, sys.stdin.readline().split()))

# 초기 값을 0으로 설정
x = 0

for i in range(M):
    x = 0
    # 이중 for문을 돌며 값이 일치하면 1, 다르면 0
    for j in range(N):
        if(B[i] == A[j]):
            x = 1
            break
    print(x)

 

input()으로 입력받는 대신 sys를 사용하였지만, 시간 초과가 떴었다. 검색해보니 이중 for문의 경우 O(n**2) 의 시간복잡도를 갖는다. 해당 문제는 시간제한이 1초라서, input과 이중 for문을 사용하면 풀 수 없다. 그래서 문제를 통과한 다른 사람들의 블로그를 참조하여 이진 탐색으로 문제를 해결하였다. 코드는 다음과 같다.

---

이진 탐색 알고리즘을 활용해 수정한 코드

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

M = int(sys.stdin.readline())
B = list(map(int, sys.stdin.readline().split()))

# 이진 탐색 알고리즘 사용하기

# 우선 비교 대상인 A 배열을 정렬한다.
A.sort()

for i in range(M):
	# start, end, mid를 설정하여 해당 값보다 크거나 작은 경우 값을 변경한다.
    start = 0
    end = len(A) - 1
    x = 0

	# while문으로 값이 하나가 남을 때까지 비교해준다.
    while(start <= end):
    
    	# while문을 한 번 돌때마다 mid값을 변경해준다.
        mid = (start + end) // 2
		
        # 값이 같으면 break
        if(B[i] == A[mid]):
            x = 1
            break
            
        # 비교 대상이 더 큰 경우 end 값을 변경
        elif(B[i] < A[mid]):
            end = mid - 1
        
        # 비교 대상이 더 작은 경우 start값을 변경
        else:
            start = mid + 1
            
    print(x)

이진 탐색을 활용한 코드로 변경하니 바로 통과할 수 있었다! Python으로 해결한 후 Java로도 풀어 보았다. 코드는 다음과 같다.

---

 

import java.io.*;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
    	// BufferedReader, StringTokenizer를 위해 throw exception은 필수이다.
        
        // 각각 수와 배열을 입력받는다. (N, A, M, B)
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String x = br.readLine();
        int N = Integer.parseInt(x);

        String y = br.readLine();
        StringTokenizer st = new StringTokenizer(y);
		
        // 입력받은 수를 배열로 변경해준다.
        int[] A = new int[N];
        int i = 0;
        while(st.hasMoreTokens()){
            A[i] = Integer.parseInt(st.nextToken());
            i++;
        }

        String a = br.readLine();
        int M = Integer.parseInt(a);

        String q = br.readLine();
        StringTokenizer st1 = new StringTokenizer(q);
		
        // 입력받은 수를 배열로 변경해준다.
        int[] B = new int[M];
        i = 0;
        while(st1.hasMoreTokens()){
            B[i] = Integer.parseInt(st1.nextToken());
            i++;
        }
		
        // 비교 대상인 A 배열을 정렬한다.
        Arrays.sort(A);

        for(i = 0; i < M; i++){
        
        // start, end, mid 변수를 조건에 맞게 변경한다.
            int start = 0;
            int end = A.length - 1;
            int idx = 0;
            
            // while문으로 비교대상보다 작은 경우, 큰 경우를 비교하며 end와 start 변수의 값을 변경한다.
            while(start <= end){
                int mid = (start + end) / 2;
                if(A[mid] == B[i]){
                    idx = 1;
                    break;
                }else if(B[i] < A[mid]){
                    end = mid - 1;
                }else{
                    start = mid + 1;
                }
            }
            System.out.println(idx);
        }
    }
}

이진 탐색 알고리즘을 사용해도 계속 오류가 났다. 계속 디버깅 했지만 오류가 계속 되어서 하나씩 값을 생각해보고 있었는데 순서만 다르게 출력될 뿐 각 값에 대한 0과 1값은 정확하게 출력되었다. 알고보니 이진탐색의 대상인 리스트 A만 정렬해야하는데 B값도 같이 정렬해서 순서가 이상한 값이 출력된 것이었다. 오류 찾는데만 혼자 1시간 정도 걸린 것 같다. 하하