[BOJ 길라잡이/Java] 8일차 #10816 숫자 카드 2

2025. 3. 18. 17:25· Languages/Java
목차
  1. 알고리즘 분류
  2. HashMap 사용
  3. 이진탐색 사용

알고리즘 분류

- 자료 구조

- 정렬

- 이분 탐색

- 해시를 사용한 집합과 맵

 

일단 내가 푼 방법은 HashMap이다.

N개 주어진 숫자 카드 각각 몇 개 있는지를 알아야 하기 때문이다.

 

HashMap 사용

import java.util.*;
import java.io.*;

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            int cnt = map.getOrDefault(num, 0);
            cnt++;
            map.put(num, cnt);
        }

        StringBuilder sb = new StringBuilder();
        int M = Integer.parseInt(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int ansNum = Integer.parseInt(st2.nextToken());
            sb.append(map.getOrDefault(ansNum, 0) + " ");
        }

        System.out.println(sb.toString());
    }
}

 

근데 처음에는 귀찮아서 StringBuilder 안쓰고 그대로 print로 출력했는데

시간제한에 걸렸다. 웬만해서는 StringBuilder 쓰는게 나을듯..

 

이진탐색 사용

찾아보니 이진탐색으로 푼 사람이 많은 것 같았다.

따라서 이 방법도 공부해봤다.

 

원래 이진탐색은 값이 일치하면 true or false를 리턴하는 구조였다.

(중앙값과 찾고자 하는 값)

그러나 이번 문제는 연속으로 중복된 값이 몇 번 입력됐는지 찾아야 하기 때문에

찾고자 하는 값의 인덱스 범위를 구해야 한다.

 

이때 lower_bound와 upper_bound의 개념을 사용한다.

import java.util.*;
import java.io.*;

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

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

        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(st.nextToken());

            sb.append(upperBound(arr, num) - lowerBound(arr, num)).append(" ");
        }

        System.out.println(sb.toString());
    }
    static int lowerBound(int[] arr, int num) {
            int left = 0;
            int right = arr.length;

            while (left < right) {
                int mid = (left + right) / 2;
                if (num <= arr[mid]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }

        static int upperBound(int[] arr, int num) {
            int left = 0;
            int right = arr.length;

            while (left < right) {
                int mid = (left + right) / 2;
                if (num < arr[mid]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }
}

 

'Languages > Java' 카테고리의 다른 글

[BOJ 길라잡이/Java] 9일차 #1874 스택 수열  (0) 2025.03.21
[BOJ 길라잡이/Java] 8일차 #9012 괄호  (0) 2025.03.19
[BOJ 길라잡이/Java] 8일차 #10867 중복 빼고 정렬하기  (0) 2025.03.18
[BOJ 길라잡이/Java] 7일차 #11651 좌표 정렬하기 2  (0) 2025.03.17
[BOJ 길라잡이/Java] 7일차 #11650 좌표 정렬하기  (0) 2025.03.17
  1. 알고리즘 분류
  2. HashMap 사용
  3. 이진탐색 사용
'Languages/Java' 카테고리의 다른 글
  • [BOJ 길라잡이/Java] 9일차 #1874 스택 수열
  • [BOJ 길라잡이/Java] 8일차 #9012 괄호
  • [BOJ 길라잡이/Java] 8일차 #10867 중복 빼고 정렬하기
  • [BOJ 길라잡이/Java] 7일차 #11651 좌표 정렬하기 2
효딩
효딩
개ㄱ발은 기세다. 줄여서 객기.
hyoding개ㄱ발은 기세다. 줄여서 객기.
효딩
hyoding
효딩
전체
오늘
어제
  • 분류 전체보기 (245)
    • SKKU SW (30)
      • Computer Architecture (14)
      • Database (4)
      • Computer Network (3)
      • Operating System (7)
      • Mobile App Programming (2)
    • SuperCoding (68)
    • CS (8)
    • Web Programming (19)
    • Cloud (13)
    • Languages (45)
      • Python (8)
      • Java (37)
    • Supporters (8)
      • MoteMote (6)
      • NHN Cloud (2)
    • Certification (27)
      • Network Advisor (14)
      • ADsP (10)
      • Engineer Information Proces.. (3)
    • Finance (9)
      • 경제금융용어 (3)
    • Woori FISA (14)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 우리fis아카데미
  • 네트워크관리사 합격
  • 서버개발
  • 네트워크관리사2급
  • 네트워크관리사
  • 글로벌소프트웨어캠퍼스
  • 클라우드
  • AWS
  • 클라우드서비스개발
  • Kotlin
  • 코틀린문법
  • 네트워크관리사 준비물
  • 인프라개발
  • 우리에프아이에스
  • 코틀린
  • 봐
  • 서버생성
  • K-디지털트레이닝
  • 네트워크관리사 커트라인
  • 클라우드 서비스
  • 우리FISA
  • 네트워크관리사2급 필기
  • apppaas
  • 인프라
  • 네트워크관리사 후기
  • 서버배포
  • nhn cloud
  • rds local 접속
  • 앱개발
  • 네트워크관리사2급 공부방법

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
효딩
[BOJ 길라잡이/Java] 8일차 #10816 숫자 카드 2
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.