본문 바로가기
코딩테스트

[JAVA] 집합과 맵

you__me 2024. 2. 1. 17:10

10815 숫자 카드

이진 정렬문제.

  1. left=0, right=n(숫자 카드 arr 의 length)
  2. mid = (left+right)/2
  3. arr[mid]와 num을 비교
    1. arr[mid]>num 인 경우, left=mid +1
    2. arr[mid]<num 인 경우, right=mid -1
    3. 위 경우를 반복하고, 반복문이 끝날 때까지 num을 찾지 못하면 false 
import java.io.*;
import java.util.StringTokenizer;
//import java.util.HashMap;
import java.util.Arrays;

public class Main {

  

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int n = Integer.parseInt(br.readLine());
    int[] num = new int[n];
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");

    for (int i=0; i<n; i++){
      num[i]=Integer.parseInt(st.nextToken());
    }

    Arrays.sort(num);

    int m = Integer.parseInt(br.readLine());
    int[] num2 = new int[m];
    st = new StringTokenizer(br.readLine(), " ");

    for(int i = 0 ; i < m; i++) {
        int a = Integer.parseInt(st.nextToken());
      
        if(binarySearch(a, num)) bw.write("1 ");
        else bw.write("0 ");
    }

    bw.flush();

  }

  private static boolean binarySearch(int num, int[] arr) {
    int n = arr.length;
    int leftIndex = 0;
    int rightIndex = n - 1;

    while (leftIndex <= rightIndex) {
      int midIndex = (leftIndex + rightIndex) / 2;
      int mid = arr[midIndex];

      if (num < mid)
        rightIndex = midIndex - 1;
      else if (num > mid)
        leftIndex = midIndex + 1;
      else
        return true;
    }
    return false;
  }

}

이진분류는 간단하다.

다만 배열이나 변수를 다른 함수에서 사용하려면 위와 같이 인자로 전달하거나, 

main함수 밖에 static으로 선언해서 사용하자.

 

14425 문자열 집합

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

public class Main {

  

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    
    HashMap<String, Integer> map = new HashMap<>();
    for (int i = 0; i < n; i++) {
        map.put(br.readLine(), 0);
    }
    
    int count = 0;
    for (int i = 0; i < m; i++) {
        if (map.containsKey(br.readLine())) count++;
    }
    System.out.print(count);

  }

}

HashMap을 이용하면 쉽게 풀 수 있다.

나는 문자열 일부만 일치하면 되는 줄 알고 집합을 하나의 문자열로 만들어서 contains() 메소드를 사용했는데 아니였음ㅎ

 

7785 회사에 있는 사람

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

public class Main {

  

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st;
    int n = Integer.parseInt(br.readLine());
    
    HashMap<String, String> map = new HashMap<>();
    for (int i = 0; i < n; i++) {
      st = new StringTokenizer(br.readLine(), " ");
      String name = st.nextToken();
      String state = st.nextToken();

      if (map.containsKey(name)) {
        map.remove(name);
      } else {
        map.put(name, state);
      }
    }

    ArrayList<String> list = new ArrayList<String>(map.keySet());
    Collections.sort(list, Collections.reverseOrder());

    for(var li : list) {
      System.out.println(li);
    }

  }

}

HashMap을 이용.

단어순 정렬은 ArrayList에 key값을 넣어서 이용했다.

 

1620 나는야 포켓몬 마스터 이다솜

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

public class Main {


  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st;
    st = new StringTokenizer(br.readLine(), " ");
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    
    HashMap<String, Integer> map1 = new HashMap<>();
    HashMap<Integer, String> map2 = new HashMap<>();
    for (int i = 0; i < n; i++) {
      String name = br.readLine();

      map1.put(name, i+1);
      map2.put(i+1, name);
    }

    StringBuilder sb = new StringBuilder();
    for(int i = 0; i < m; i++) {
      String S = br.readLine();
      //입력값이 번호인지 포켓몬이름인지 판별
      if(49 <= S.charAt(0) && S.charAt(0) <= 57) {
        sb.append(map2.get(Integer.parseInt(S))).append("\n");
      }else {
        sb.append(map1.get(S)).append("\n");
      }
    }
    System.out.println(sb);

  }

}
  1. HaspMap을 두개 만든다.(이름, 숫자) & (숫자, 이름)
  2. 입력값이 번호인지 판별하고 적절한 HaspMap을 사용한다. 숫자(1~9)의 아스키 코드값은 49~57 이므로 이를 이용한다.

 

이 문제를 풀 때 출력을 BW을 사용했지만 정수는 아스키코드값이 출력된다.

그래서 출력이 제대로 안됨. 물어봤더니 따로 String 형변환을 해주어야 한다고 한다. 귀찮아서 sb 사용함

10816 숫자 카드 2

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

public class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int n = Integer.parseInt(br.readLine());
    HashMap<Integer, Integer> map = new HashMap<>();
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");

    for (int i=0; i<n; i++){
      int a = Integer.parseInt(st.nextToken());
      if (map.containsKey(a)) map.put(a, map.get(a) +1); 
      else map.put(a, 1);
    }

    StringBuilder sb = new StringBuilder();
    int m = Integer.parseInt(br.readLine());
    st = new StringTokenizer(br.readLine(), " ");
    for(int i = 0 ; i < m; i++) {
      int a = Integer.parseInt(st.nextToken());

      if (map.containsKey(a)) sb.append(map.get(a) + " ");
      else sb.append("0 ");
    }

    System.out.println(sb);

  }

}

 

 

1764 듣보잡

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        int n = Integer.parseInt(inputs[0]);
        int m = Integer.parseInt(inputs[1]);

        HashSet<String> set = new HashSet<>(); 
        for (int i = 0; i < n; i++) {
            set.add(br.readLine());
        }

        ArrayList<String> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            String tmp = br.readLine();
            if(set.contains(tmp)){
                result.add(tmp);
            }
        }

        Collections.sort(result);

        System.out.println(result.size());
        for (String s : result) {
            System.out.println(s);
        }
    }
}

key값만 사용하므로 HashMap이 아닌 HashSet을 사용했다.

또한 정렬을 편리하게 하고 크기가 정해지지 않은 ArrayList를 사용해서 결과를 저장함.

 

1269 대칭 차집합

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

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

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        Set<Integer> setA = new HashSet<>();
        Set<Integer> setB = new HashSet<>();

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < a; i++) {
            setA.add(Integer.parseInt(st.nextToken()));
        }
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < b; i++) {
            setB.add(Integer.parseInt(st.nextToken()));
        }

        int ans = 0;
        for(int num : setA) {
            if(!setB.contains(num)) {
                ans += 1;
            }
        }
        for(int num : setB) {
            if(!setA.contains(num)) {
                ans += 1;
            }
        }
        System.out.println(ans);
    }
}

set을 2개씩 만들어서 직접 빼주려고 했는데 검색해보니 그냥 서로의 key값이 포함안될때 +1 해주면 간단하게 풀 수 있었다.

 

11478 서로 다른 부분 문자열의 개수

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
      
        String str = br.readLine();
        Set<String> set = new HashSet<>();
        int cnt=0;

        for (int i=1;i<=str.length();i++){
          for(int j=0;j+i<=str.length();j++){
            String k = str.substring(j, j+i);
            if (set.contains(k)) continue;
            else cnt++; set.add(k);
          }
        }

        System.out.println(cnt);
    }
}

 

# 회고

 

set, map 등을 사용하면 쉽게 풀리는 문제들이라 간단하당

'코딩테스트' 카테고리의 다른 글

[JAVA] 스택, 큐, 덱  (0) 2024.02.06
[JAVA] 약수, 배수와 소수 2  (1) 2024.02.04
[JAVA] 정렬  (0) 2024.01.30
[JAVA] 브루트 포스  (1) 2024.01.25
[JAVA] 시간 복잡도 단계  (0) 2024.01.24

'코딩테스트' Related Articles

티스토리툴바