🎃 코딩 테스트 스터디 1주차

개발/👾 PS

🎃 코딩 테스트 스터디 1주차

정소은 2024. 8. 1. 16:17

# 1920 - 수 찾기

https://www.acmicpc.net/problem/1920

# 10815 - 숫자 카드

https://www.acmicpc.net/problem/10815

📌 접근 방법
일단 보자마자 든 생각은 브루트포스인가? 여서
시간복잡도를 계산하기 위해 N과 M의 범위를 살펴보았다

파이썬의 경우 1초에 약 2천만번의 계산을 하는데
N(1 ≤ N ≤ 100,000) M(1 ≤ M ≤ 100,000) 인 상황에서 하나하나 탐색한다면
최악의 경우 100,000 x 100,000번의 연산이 필요하므로 시간 제한에 걸리게 될 것이다.

다음으로 생각한 방법은
set에 넣어서 연산하는 방법이다
python의 경우 a in set 연산의 시간복잡도가 O(1)이므로 훨씬 빠를 것이다

# 1920 / # 10815 - 코드 동일하게 적용 가능

N = int(input())
A = set(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))

for n in B:	
    if n in A:
        print(1)
    else:
        print(0)

근데 아마 이분탐색을 의도한 문제인 듯...

이분탐색을 구현해보자!

이분탐색
: 중앙값을 기준으로 탐색 범위를 절반으로 좁혀나가면서 탐색하는 기법

📍 전제 조건 : 정렬된 배열에서 수행할 것

로직

초기 설정
: 탐색 배열(arr)의 첫번째 요소를 low, 마지막 요소를 high, 중간 요소를 mid 라고 하자
: 탐색해야 할 요소를 key라고 하자
: 탐색 범위는 low ~ high

low > high가 될 때까지 반복
1 ) arr[mid] == key : 요소 발견, 탐색 중지
2 ) arr[mid] > key
: 정렬된 배열의 중앙값보다 key가 작으므로 mid ~ high에는 확실히 key가 존재하지 않는다
: 따라서 탐색 범위를 low ~ mid-1로 옮겨야 하기 때문에 high = mid-1 / 조정된 탐색 범위에서의 중앙값으로 mid 재설정
3 ) arr[mid] < key
: 정렬된 배열의 중앙값보다 key가 크므로 low ~ mid에는 확실히 key가 존재하지 않는다
: 따라서 탐색 범위를 mid+1 ~ high로 옮겨야 하기 때문에 low = mid+1 / 조정된 탐색 범위에서의 중앙값으로 mid 재설정

Python

import sys

input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))

# 이분탐색을 위해서는 배열이 정렬되어 있어야 함
a.sort()

# 이분탐색 함수 (a: 배열, key: 요소)
def binarysearch(a, key):
    # 탐색 범위를 가리키는 포인터들
    low = 0
    high = len(a) -1
    
    # 요소의 존재 여부
    flag = False
    
    while low <= high:
    	# 중간값
        mid = int((low+high)/2)
        
        # 요소와 중간값을 비교해서 탐색 범위 조정
        if a[mid] == key:
            flag = True
            break
        elif a[mid] < key:
            low = mid+1
        elif a[mid] > key:
            high = mid-1
    
    if flag :
        return 1
    else:
        return 0

# b의 요소 binarysearch 함수에 전달해서 결과값 출력
for i in range(m):
    print(binarysearch(a, b[i]))

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static int binarySearch(int[] A, int key){

        int low = 0;
        int high = A.length-1;
        Boolean flag = false;

        while (low <= high) {
            int mid = (int)((low+high)/2);
            if (A[mid] == key) {
                flag = true;
                break;
            } else if (A[mid] > key){
                high = mid - 1;
            } else if (A[mid] < key){
                low = mid + 1;
            }
        }

        if (flag) return 1;
        else return 0;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(A);

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

        st = new StringTokenizer(br.readLine(), " ");
        
        for(int i = 0; i < M; i++) {
            System.out.println((binarySearch(A, Integer.parseInt(st.nextToken()))));
        }
    }
}

사실 이 문제들은 python의 sort() 함수로 한방에 풀리는 문제들이라서...

Java에서는 보통 정렬 문제들을 어떻게 푸는지 살펴봐야겠다

💡 Java에서도 Arrays.sort() 혹은 Collections.sort() 함수를 사용하는 듯!
-> 보통 배열을 정렬할 때 Arrays.sort(), Set 혹은 List 와 같은 Collections 정렬할 때 Collections.sort() 사용
-> 둘 다 시간복잡도는 약 O(nlogn) / Arrays.sort()는 평균적으로 최악의 경우 n^2
💡 Python의 sort()는 퀵정렬을 수행하는 함수, 시간복잡도 : O(nlogn)

저작자표시 비영리 변경금지 (새창열림)

🎃 코딩 테스트 스터디 1주차

# 1920 - 수 찾기

# 10815 - 숫자 카드

# 2750 - 수 정렬하기

# 2751 - 수 정렬하기 2

# 10989 - 수 정렬하기 3