๐Ÿ”ฅ[99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋””] 13์ผ์ฐจ TIL - ์ˆซ์ž ์นด๋“œ

HOONSSACยท2024๋…„ 8์›” 3์ผ
1

99Club Coding Test Study

๋ชฉ๋ก ๋ณด๊ธฐ
13/41
post-thumbnail

โณ๋ฌธ์ œ

์ˆซ์ž ์นด๋“œ๋Š” ์ •์ˆ˜ ํ•˜๋‚˜๊ฐ€ ์ ํ˜€์ ธ ์žˆ๋Š” ์นด๋“œ์ด๋‹ค. ์ƒ๊ทผ์ด๋Š” ์ˆซ์ž ์นด๋“œ N๊ฐœ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค. ์ •์ˆ˜ M๊ฐœ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ด ์ˆ˜๊ฐ€ ์ ํ˜€์žˆ๋Š” ์ˆซ์ž ์นด๋“œ๋ฅผ ์ƒ๊ทผ์ด๊ฐ€ ๊ฐ€์ง€๊ณ  ์žˆ๋Š”์ง€ ์•„๋‹Œ์ง€๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— ์ƒ๊ทผ์ด๊ฐ€ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ์ˆซ์ž ์นด๋“œ์˜ ๊ฐœ์ˆ˜ N(1 โ‰ค N โ‰ค 500,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ์ˆซ์ž ์นด๋“œ์— ์ ํ˜€์žˆ๋Š” ์ •์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ˆซ์ž ์นด๋“œ์— ์ ํ˜€์žˆ๋Š” ์ˆ˜๋Š” -10,000,000๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 10,000,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™๋‹ค. ๋‘ ์ˆซ์ž ์นด๋“œ์— ๊ฐ™์€ ์ˆ˜๊ฐ€ ์ ํ˜€์žˆ๋Š” ๊ฒฝ์šฐ๋Š” ์—†๋‹ค.

์…‹์งธ ์ค„์—๋Š” M(1 โ‰ค M โ‰ค 500,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋„ท์งธ ์ค„์—๋Š” ์ƒ๊ทผ์ด๊ฐ€ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ์ˆซ์ž ์นด๋“œ์ธ์ง€ ์•„๋‹Œ์ง€๋ฅผ ๊ตฌํ•ด์•ผ ํ•  M๊ฐœ์˜ ์ •์ˆ˜๊ฐ€ ์ฃผ์–ด์ง€๋ฉฐ, ์ด ์ˆ˜๋Š” ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„๋˜์–ด์ ธ ์žˆ๋‹ค. ์ด ์ˆ˜๋„ -10,000,000๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 10,000,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™๋‹ค

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ M๊ฐœ์˜ ์ˆ˜์— ๋Œ€ํ•ด์„œ, ๊ฐ ์ˆ˜๊ฐ€ ์ ํžŒ ์ˆซ์ž ์นด๋“œ๋ฅผ ์ƒ๊ทผ์ด๊ฐ€ ๊ฐ€์ง€๊ณ  ์žˆ์œผ๋ฉด 1์„, ์•„๋‹ˆ๋ฉด 0์„ ๊ณต๋ฐฑ์œผ๋กœ ๊ตฌ๋ถ„ํ•ด ์ถœ๋ ฅํ•œ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

์˜ˆ์ œ ์ž…๋ ฅ 1

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

์˜ˆ์ œ ์ถœ๋ ฅ 1

1 0 0 1 1 0 0 1

โœ๏ธํ’€์ด

์ฒซ ๋ฒˆ์งธ ์‹œ๋„

import java.util.*;

public class Baekjoon_10815 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> N_list = new ArrayList<>();
        ArrayList<Integer> M_list = new ArrayList<>();
        
        // ์ƒ๊ทผ์ด์˜ ์นด๋“œ ์ž…๋ ฅ
        int N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            N_list.add(sc.nextInt());
        }
		
        // ๋น„๊ตํ•  ์นด๋“œ ์ž…๋ ฅ
        int M = sc.nextInt();
        for (int i = 0; i < M; i++) {
            M_list.add(sc.nextInt());
        }

		// ์ƒ๊ทผ์ด์˜ ์นด๋“œ์— ์กด์žฌํ•˜๋Š” ์ง€ ํ•˜๋‚˜์”ฉ ํ™•์ธ
        for (int i = 0; i < M; i++) {
            if (N_list.contains(M_list.get(i))) {
                System.out.print(1 + " ");
            }
            else {
                System.out.print(0 + " ");
            }
        }
        System.out.print("\b"); // ๋งˆ์ง€๋ง‰ ๊ณต๋ฐฑ ์ œ๊ฑฐ
        

        sc.close();
    }
}

๋‚˜๋Š” ๋‹จ์ˆœํžˆ ๋น„๊ตํ•  ์นด๋“œ์™€ ์ƒ๊ทผ์ด์˜ ์นด๋“œ๋ฅผ ๋น„๊ตํ•˜๊ธฐ๋งŒ ํ•˜๋ฉด ๋œ๋‹ค๊ณ  ์ƒ๊ฐํ•ด, ๋‘ ๊ฐœ์˜ ArrayList๋ฅผ ๋งŒ๋“ค์–ด์„œ containsํ•จ์ˆ˜๋ฅผ ํ†ตํ•ด ํ•ด๋‹น ์นด๋“œ๊ฐ€ ์ƒ๊ทผ์ด์˜ ์นด๋“œ๋ฅผ ๋‹ด๊ณ  ์žˆ๋Š” ArrayList์— ์กด์žฌํ•˜๋Š” ์ง€ ์—ฌ๋ถ€๋ฅผ ํŒ๋ณ„ํ•˜๋„๋ก ๊ตฌํ˜„ํ•˜์˜€๋‹ค.

์ถœ๋ ฅ ๊ฒฐ๊ณผ๋Š” ๋™์ผํ–ˆ์œผ๋‚˜, ๊ฒฐ๊ณผ๋Š” ์‹œ๊ฐ„ ์ดˆ๊ณผ๋กœ ์ธํ•ด ์‹คํŒจ์˜€๋‹ค.

๋‘ ๋ฒˆ์งธ ์‹œ๋„

๊ทธ๋ ‡๋‹ค๋ฉด ์‹œ๊ฐ„์„ ๋‹จ์ถ•์‹œํ‚ฌ ์ˆ˜ ์žˆ๋Š” ๋ฐฉ๋ฒ•์—๋Š” ๋ฌด์—‡์ด ์žˆ์„๊นŒ ๊ฐ€๋งŒํžˆ ์ƒ๊ฐํ•ด ๋ณด์•˜๋‹ค.

์›์ธ์ด ๋ญ”๊ฐ€ ArrayList์˜ contains()๋ฉ”์„œ๋“œ ์ผ ๊ฒƒ์ด๋ผ๋Š” ์ƒ๊ฐ์ด ๋“ค์—ˆ๋‹ค.

๊ทธ๋ž˜์„œ ๊ฒ€์ƒ‰์„ ํ•ด๋ณด๋‹ˆ, ArrayList์—์„œ contains()๋ฉ”์„œ๋“œ๋ฅผ ์‚ฌ์šฉํ•˜๋ฉด, ๋ฆฌ์ŠคํŠธ์˜ ๋ชจ๋“  ์š”์†Œ๋ฅผ ์ˆœํšŒํ•˜๋ฉด์„œ ํŠน์ • ์š”์†Œ๊ฐ€ ์กด์žฌํ•˜๋Š” ์ง€ ํ™•์ธํ•˜๋Š” ๊ณผ์ •์„ ๊ฑฐ์น˜๊ธฐ ๋•Œ๋ฌธ์—, ์ตœ์•…์˜ ๊ฒฝ์šฐ O(N)O(N)์˜ ์‹œ๊ฐ„์ด ์†Œ์š” ๋œ๋‹ค๋Š” ์‚ฌ์‹ค์„ ๊นจ๋‹ฌ์•˜๋‹ค.

๊ฒŒ๋‹ค๊ฐ€ ์ด๊ฑธ M๋งŒํผ ๋ฐ˜๋ณตํ•˜๋„๋ก ์ฝ”๋“œ๋ฅผ ๊ตฌ์„ฑํ•ด ๋†“์•˜์œผ๋‹ˆ, O(Nโˆ—M)O(N * M)์ด๋ผ๋Š” ๋น„ํšจ์œจ์ ์ธ ์‹คํ–‰ ์‹œ๊ฐ„์„ ์ดˆ๋ž˜ํ–ˆ๋˜ ๊ฒƒ์ด๋‹ค.

๐Ÿ’ป์ตœ์ข… ์ฝ”๋“œ

๊ทธ๋ž˜์„œ ๋‚˜๋Š” ArrayList๋Œ€์‹  Set์„ ์‚ฌ์šฉํ•ด ๋ฌธ์ œ๋ฅผ ๋‹ค์‹œ ํ’€์—ˆ๋‹ค.
Set ์ค‘์—์„œ๋„ Hash Set์€ Hash table์„ ๊ธฐ๋ฐ˜์œผ๋กœ ์ž‘๋™ํ•˜๋Š” Set์ด๊ธฐ ๋•Œ๋ฌธ์—, ๊ฒ€์ƒ‰ํ•˜๋Š” ์ž‘์—…์„ ์ˆ˜ํ–‰ํ•˜๋Š” ๋ฐ ์ƒ์ˆ˜ ์‹œ๊ฐ„๋ฐ–์— ์†Œ์š”๋˜์ง€ ์•Š๋Š”๋‹ค๋Š” ์žฅ์ ์ด ์žˆ๋‹ค!

import java.util.*;

public class Baekjoon_10815 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Set<Integer> N_set = new HashSet<>(); // Hash Set
        StringBuilder result = new StringBuilder();
        
        // ์ƒ๊ทผ์ด์˜ ์นด๋“œ ์ž…๋ ฅ
        int N = sc.nextInt();
        for (int i = 0; i < N; i++) {
            N_set.add(sc.nextInt());
        }

		// ๋น„๊ตํ•  ์นด๋“œ ์ž…๋ ฅ
        int M = sc.nextInt();
        for (int i = 0; i < M; i++) {
            if (N_set.contains(sc.nextInt())) {
                result.append(1).append(" ");
            }
            else {
                result.append(0).append(" ");
            }
        }
        result.toString().trim(); // ๋งˆ์ง€๋ง‰ ๊ณต๋ฐฑ ์ œ๊ฑฐ
        System.out.print(result);
        
        sc.close();
    }
}


์ด๋ ‡๊ฒŒ ArrayList๋Œ€์‹  Hash Set์„ ์‚ฌ์šฉํ•จ์œผ๋กœ์จ ์‹คํ–‰ ์‹œ๊ฐ„์„ ๋‹จ์ถ•์‹œํ‚ฌ ์ˆ˜ ์žˆ์—ˆ๋‹ค!


๐Ÿ”—๋ฌธ์ œ ๋งํฌ
๐Ÿ’ปRepository

profile
ํ›ˆ์‹น์˜ ๊ฐœ๋ฐœ์—ฌํ–‰

1๊ฐœ์˜ ๋Œ“๊ธ€

comment-user-thumbnail
2024๋…„ 8์›” 3์ผ

์˜ค๋Š˜๋„ ๋ฉ‹์žˆ๋‹ค๊ตฌ!๐Ÿ‘

๋‹ต๊ธ€ ๋‹ฌ๊ธฐ