[BOJ]1920 수 찾기 (kotlin,java)

❔문제❔

1920. 수 찾기

🙌Solution🙌

〰️List.contins()함수 사용 : 시간초과

fun main(){

    val numsCount=readLine()
    val nums=readLine()!!.split(" ")

    val inputsCount=readLine()
    val inputs=readLine()!!.split(" ")

    inputs.forEach{
        println("${if(nums.contains(it))1 else 0}\n")
    }

이 코드는 시간초과가 됐다.😅

가장 간단하게 구현할 수 있는 방법이지만 시간 복잡도가 $O(n^2)$이 된다.

inputs.forEach{
      println("${if(nums.contains(it))1 else 0}\n")
}

위 함수의 경우 forEach에서 inputs을 한번 순회하며 그 안에서 contains()함수로 선형탐색을 하게 된다.

따라서 반복문 안에서 반복문이 동작하므로 시간복잡도는 \(O(n^2)\)이 된다.

코틀린은 각 함수에 대해 잘 모르면 코드의 효율성을 핸들링하기 힘든데 이런 디테일 한 부분이 좀 재미있는 것 같다.☺️

〰️Two pointer 알고리즘 : 시간초과

fun main(){

    val n=readLine()!!.toInt()
    val nums=readLine()!!.split(" ").map{it.toLong()}
    val sortedNums=nums.sorted()

    val m=readLine()!!.toInt()
    val checkNums=readLine()!!.split(" ").map{it.toLong()}
    val checkNumsIndexMap=checkNums
                            .withIndex()
                            .groupBy { it.value }
                            .mapValues { it.value.map { it.index } }
    val sortedCheckNums=checkNums.sorted()

    var compareIndex=0 // 배열 인덱스를 가리키는 변수
    var checkIndex=0 // 포함여부를 확인할 배열의 인덱스를 가리키는 변수 

    val res=BooleanArray(m){false}

    while(checkIndex<m&&compareIndex<n){
        val num=sortedNums[compareIndex]
        val check=sortedCheckNums[checkIndex]
        if(num==check){
            checkNumsIndexMap[check]?.forEach{
                res[it]=true
            }
            checkIndex++
            compareIndex++
        }
        else if(num>check){
            checkIndex++
        }
        else compareIndex++
    }

    res.forEach{
        print("${if(it)1 else 0}\n")
    }

}

두 번째로 접근한 방법은 최근에 배운 투 포인터 알고리즘을 사용하는 것이다!

위 코드는 다음과 같이 동작한다.

1. 배열을 오름차순 정렬
2. 포함 여부를 확인해야 하는 배열을 오름차순 정렬 및 원래 위치와 매핑

3. 투 포인터 알고리즘을 통해 포함 여부 확인

   인덱스 0 부터 아래 흐름에 따라 비교

   (num : 원래 배열에서 현재 가리키는 원소)

   (check : 포함 여부를 확인해야 하는 배열에서 현재 가리키는 원소)

위와 같이 동작하는 코드는 아래와 같은 고려할 점이 있다.

1. 배열 정렬 시 시간 복잡도 :
2. 포함 여부를 확인해야 하는 배열 정렬 및 매핑 시 시간 복잡도
3. 투 포인터 알고리즘에서 시간 복잡도

sorted()

• 오름차순 정렬해줌
• quick sort 기반 정렬
• 정렬은 안정적(stable)
• 기존 리스트는 변경되지 않고 새로운 정렬된 리스트를 생성해 반환

이것도 조사하다 보니 길어질 것 같아서 여기에는 간단히 sorted()함수에 대해서 설명하고 다른 포스팅에서 코틀린의 정렬에 대한 전반적인 내용을 다뤄보기로 했다!

〰️Set.contains() 함수 사용 : 1804ms

마지막으로는 첫 번째 접근에서 약간 수정해서 Set.contains()을 활용하여 탐색을 해봤다.

set은 자료구조 상 list보다 더 효율적으로 포함되는 원소를 찾을 수 있어 Set.contains()는 List.contins()보다 효율이 좋다.

사용하는 set의 종류별로 탐색 방법이 조금씩 달라서 이부분도 나중에 공부해보면 재미있을것같다!

fun main(){

    val n=readLine()!!.toInt()
    val nums=readLine()!!.split(" ").map{it.toLong()}.toSet()

    val m=readLine()!!.toInt()
    val checkNums=readLine()!!.split(" ").map{it.toLong()}

    checkNums.forEach{
        print("${if(nums.contains(it))1 else 0}\n")
    }

}

🚀Advanced🚀

다른 사람의 풀이를 보니 가장 빠른 풀이는 268ms로 내 풀이보다 7배 정도 빨랐다.

다른 풀이들도 대부분 500ms대로 내 풀이보다 3배정도 빨랐다.

백준의 알고리즘 구분을 보니 이진 탐색을 활용하여 빠르게 풀이할 수 있는 듯 했다.

〰️이진 탐색 : 864ms

지금 생각하면 첫 번째 시도 후에 이진 탐색 접근을 고려해 볼 수도 있었을텐데 하는 생각이 든다🥲

이번에는 알고리즘의 변경 뿐만 아니라 IO에 관련된 코드도 개선해보았다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main(){

    val br=BufferedReader(InputStreamReader(System.`in`))
    val bw=BufferedWriter(OutputStreamWriter(System.out))

    val n=br.readLine().toInt()
    val nums=br.readLine().split(" ").map{it.toInt()}.toMutableList()
    nums.sort()

    val m=br.readLine().toInt()
    val checkNums=br.readLine().split(" ").map{it.toInt()}

    checkNums.forEach{
        bw.write("${if(nums.binarySearch(it)<0)0 else 1}\n")
    }

    bw.flush()

}

• Buffer를 사용한 IO 효율 개선

    val br=BufferedReader(InputStreamReader(System.`in`))
  

  • System.in : 표준 입출력 스트림(키보드 등) 의미
  • InputStreamReader : 바이트 스트림(InputStream)→ 문자 스트림(Reader)
  • BufferedReader : InputStreamReader에서 변환한 문자 스트림을 버퍼링.

    val bw=BufferedWriter(OutputStreamWriter(System.out))
  

  • System.out : 표준 출력 스트림(콘솔 출력 등) 의미
  • OutputStreamWriter : 문자스트림(Writer)→ 바이트스트림(OutputStreamWriter)
  • BufferedWriter : 문자스트림을 버퍼링하다가(write()) OutputStreamWriter를 사용해 바이트 스트림으로 변환 후 한번에 내보냄(flush()).

• 이진 탐색 사용

    val nums=br.readLine().split(" ").map{it.toInt()}.toMutableList()
    nums.sort()
  

  • 이진 탐색을 하기 위해 nums를 오름차순 정렬
  • 이때 정렬 방법은 quicksort

    bw.write("${if(nums.binarySearch(it)<0)0 else 1}\n")
  

  • binarySearch()함수로 이진탐색 수행

투포인터 알고리즘 vs 이진탐색 알고리즘

내가 이 방법으로 문제를 풀 때 가장 많이 고민했던 건 투 포인터 알고리즘으로 푸는 게 더 효율적으로 보였기 때문이다.

이진 탐색의 경우 매 원소마다 탐색을 해야 하는데 비해 투 포인터 알고리즘은 한번의 반복문에서 답을 찾아낼 수 있으니 뭔가 더 효율적이여 보였다.

비교 하기 쉽게 각 코드의 절차 별로 사용된 함수를 표로 정리해보았다.

구분	투포인터	이진탐색
숫자 배열 정렬	split map sorted	sort
(시간복잡도)	$O(nlogn)$	$O(nlogn)$
확인 숫자 배열 정렬	groupBy mapValues sorted	x
(시간복잡도)	$O(mlogm)$	x
탐색 알고리즘	Two Pointer	Binary Search
(시간복잡도)	$O(n+m)$	$O(m log n)$
전체 시간 복잡도	$O(nlogn+mlogm+n+m)$	$O(nlogn+mlogn)$

그냥 생각했을 때는 투 포인터 알고리즘이 빨라 보였는데 투 포인터 알고리즘을 쓰기 위한 전처리 과정에서 이진탐색보다 오버헤드가 많이 일어남을 알 수 있었다.

따라서 이 문제에서는 이진탐색을 활용하는게 더 적합하다는 결론을 내릴 수 있다.

〰️Set.contains() + IO 개선 : 676ms

공부를 하다 보니 set.contains가 이진 탐색보다 효율이 좋지 않을까 하는 생각이 문뜩 들어 세 번째 시도한 코드에서 IO를 버퍼를 사용해 개선해 보았다.

fun main(){

    val br=BufferedReader(InputStreamReader(System.`in`))
    val bw=BufferedWriter(OutputStreamWriter(System.out))
    val n=br.readLine().toInt()
    val nums=br.readLine().split(" ").map{it.toLong()}.toSet()

    val m=br.readLine().toInt()
    val checkNums=br.readLine().split(" ").map{it.toLong()}

    checkNums.forEach{
        bw.write("${if(nums.contains(it))1 else 0}\n")
    }

    bw.flush()

}

결과는 676ms로 가장 빨랐다!

알고리즘 문제인 줄 알았는데 입출력의 비효율이 가장 큰 문제였나보다.😅

약간 허탈하기도 하지만 set의 contains()함수를 조사하다 보니 이것도 공부 거리가 꽤 있어서 오히려 좋다!😂

🔠JAVA로 풀어보기🔠

마음 같아서는 코틀린으로 코테를 준비하고 싶지만 코테에서 코틀린의 입지는 너무나 좁으므로 겸사겸사 마지막 코드를 자바로 코딩하면서 자바도 같이 연습해보기로 했다.🥲

import java.util.HashSet;
import java.util.Scanner;

public class Main {

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        sc.nextLine();

        HashSet<Integer> set= new HashSet<Integer>();
        String[] nums=sc.nextLine().split(" ");

        for(int i=0;i<n;i++){
            set.add(Integer.parseInt(nums[i]));
        }

        int m=sc.nextInt();
        sc.nextLine();

        String[] checkNums=sc.nextLine().split(" ");

        for(int i=0;i<m;i++){
            int num=Integer.parseInt(checkNums[i]);
            System.out.println(set.contains(num)?1:0);
        }
    }
}

같은 알고리즘인데 시간차이가 많이난다..ㅜ

아직 자바가 미숙해서 그런가 보다.

자바로 최적화하는 것도 하고싶지만 지금은 너무 방전이라서 다음에 다른 코드대한 포스팅에서 해보기로 한다🥲