알고리즘 스터디 3주차 문제풀이

 

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

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

 

문제설명

HashMap을 사용해 포켓몬 번호와 이름을 매핑

접근방식

O(n + m) 선형 시간복잡도

 

포켓몬 개수 N개에 대해 N번의 입력을 받고, 문제의 개수 M에 대해 M번의 처리를 수행하기 때문에

시간복잡도는 O(N + M)이다.

문제 조건 분석 과정

• 포켓몬의 개수 N과 문제의 개수 M을 입력받은 후 N개 만큼 포켓몬의 이름을 입력받는다.
• HashMap을 두개 지정해 하나는 포켓몬 번호 순으로 정렬, 하나는 이름 순으로 정렬한다.
•  
• M개의 줄 만큼 문제가 주어진다.
• 문제가 숫자로 시작할시 숫자(번호)에 대응하는 포켓몬 이름을 출력한다.
• 문자열로 주어지면 이름에 대응하는 포켓몬 번호를 출력한다.
•  
• 각 문제에 대한 정답을 StringBuilder에 저장하고 출력한다.

사용된 자료구조

• HashMap: 두 개의 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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); //포켓몬의 개수
        int M = Integer.parseInt(st.nextToken()); //문제의 개수

        StringBuilder sb = new StringBuilder();
        //조건에 따라 다르게 쓰일 두개의 HashMap
        HashMap<Integer, String> hash1 = new HashMap<Integer, String>(); //포켓몬 번호순 이름저장
        HashMap<String, Integer> hash2 = new HashMap<String, Integer>(); //포켓몬 이름순 번호저장


        for(int i = 1; i <= N; i++) {
            String S = br.readLine(); //N만큼의 포켓몬 이름
            hash1.put(i, S); //포켓몬 번호에 대응하는 이름
            hash2.put(S, i); //포켓몬 이름에 대앙하는 번호
        }

        for(int i = 0; i < M; i++) { //M개의 문제
            String S = br.readLine();
            if(49 <= S.charAt(0) && S.charAt(0) <= 57) {
                sb.append(hash1.get(Integer.parseInt(S))).append("\n"); //번호에 해당하는 포켓몬
            }else {
                sb.append(hash2.get(S)).append("\n"); //이름에 해당하는 포켓몬 번호
            }
        }
        System.out.println(sb);
    }
}

 

10816 숫자 카드 2

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

 

문제설명

이진 탐색을 이용하여 숫자가 몇 개씩 있는지 계산

접근방식

O(M log N) 시간 복잡도

 

1. Arrays.sort()를 이용한 배열 정렬하는데 O(N log N)의 시간 소요

2. 이진 탐색하는데 O(log N)의 시간이 소요된다.

3. 각 숫자별로 M번만큼 이진 탐색을 하기 때문에 O(M log N)의 시간이 소요된다.

문제 조건 분석 과정

 

1. 배열에 숫자 개수 만큼의 정수를 담고, 정렬한다.

2. 배열 안에서 key 이상인 정수를 찾는다.

3. 각 숫자별로 상근이가 가지고 있는 숫자 카드 개수를 계산한다.

 

사용된 자료구조

• Arrays.sort(): 정수들을 배열에 담고 정렬하기 위해서 사용
• lowerBound, upperBound: 이진 탐색을 위한 반복문

전체코드

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

public class Main {

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

        // 숫자 카드의 개수 N 입력
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        // 숫자 카드에 적힌 정수들 입력 및 정렬
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        // 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 숫자의 개수 M 입력
        int M = Integer.parseInt(br.readLine());

        // 구해야 할 숫자들 입력
        st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();

        // 각 숫자에 대해 상근이가 가지고 있는 숫자 카드 개수 계산
        for (int i = 0; i < M; i++) {
            int key = Integer.parseInt(st.nextToken());

            // 이진 탐색을 이용해 lowerBound와 upperBound의 차이를 구함
            sb.append(upperBound(arr, key) - lowerBound(arr, key)).append(' ');
        }

        // 결과 출력
        System.out.println(sb);
    }

    // lowerBound 구하는 메서드
    private static int lowerBound(int[] arr, int key) {
        int n = 0;
        int m = arr.length;

        while (n < m) {
            int mid = (n + m) / 2;

            if (key <= arr[mid]) {
                m = mid;
            } else {
                n = mid + 1;
            }
        }

        return n;
    }

    // upperBound 구하는 메서드
    private static int upperBound(int[] arr, int key) {
        int n = 0;
        int m = arr.length;

        while (n < m) {
            int mid = (n + m) / 2;

            if (key < arr[mid]) {
                m = mid;
            } else {
                n = mid + 1;
            }
        }

        return n;
    }
}

 

2164 카드 2

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

문제설명

요세푸스 순열을 이용한 문제

접근방식

O(N) 선형 시간복잡도

 

큐의 연산은 O(1) 상수 시간이 주어지고

N번만큼 주어졌을 때, 한 명이 남을 때까지 위의 과정을 N-1번 반복하므로

시간 복잡도는 O(N)이다.

문제 조건 분석 과정

 

1. 1부터 N까지의 숫자를 큐에 저장한다.

2. 한 명만 남을 때까지 큐에서 반복한다

• 큐에서 맨 앞에 있는 사람을 제거한다. (q.poll())
• 그 다음 사람을 큐의 맨 뒤로 보낸다 (q.offer(q.poll())

3. 큐에 한 명만 남았을때, 해당 사람의 번호를 출력한다.

 

사용된 자료구조

• Queue(Linkedlist): 선입선출을 이용

전체코드

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

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 N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        Queue<Integer> q = new LinkedList<>();

        for (int i = 1; i <= N; i++){
            q.offer(i); //1 ~ N의 숫자를 q에 저장
        }

        StringBuilder sb = new StringBuilder();
        sb.append("<");

        //queue에 한 명이 남을때까지 반복
        while (q.size() > 1){
            //K번째의 사람을 제거하기 위해 K-1 번째까지의 사람을 q의 맨 뒤로 보낸다
            for(int i = 0; i < K - 1; i++){
                q.offer(q.poll());
            }
            sb.append(q.poll()).append(", ");
        }

        sb.append(q.poll()).append(">");

        String result = sb.toString();
        System.out.println(result);

       br.close();
    }
}

18115 카드놓기

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

문제설명

deque를 사용하여 카드를 놓는 순서 관리

접근방식

O(N) 선형 시간복잡도

 

n 개의 숫자를 입력받고, 각 숫자에 따라 덱을 조작한다.

덱은 O(1) 상수 시간을 가진다.

따라서 O(n) 의 시간복잡도를 가진다.

문제 조건 분석 과정

 

1. 하나는 그냥 받고, 하나는 StringBuilder을 사용해 역순으로 입력된 숫자열을 받는다.

 

2. num이 1일 때 현재 숫자를 덱의 맨 앞에 추가한다.

3. num이 2일 때 덱의 맨 앞에서 숫자를 제거한 후 현재 숫자를 덱의 맨 앞에 추가한다. 

그리고 제거한 숫자를 다시 맨 앞에 추가한다.

4. num이 3일 때 현재 숫자를 덱의 맨 뒤에 추가한다.

 

5. 덱이 빌 때 까지 숫자들을 stringBuilder에 추가한다

 

사용된 자료구조

• Deque: 덱을 사용하여 카드를 놓는다.
  • addFirst: 덱의 맨 앞에 요소를 추가한다.
  • removeFirst: 덱의 맨 앞에 있는 요소를 제거하고 반환한다.
  • addLast: 덱의 맨 뒤에 요소를 추가한다.

전체코드

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

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(new StringBuilder(br.readLine()).reverse().toString());

        //Deque로 정수 저장
        Deque<Integer> d = new LinkedList<>();

        //1부터 n까지 반복
        for (int i = 1; i <= n; i++) {
            //역순으로 입력된 값 중에서 다음 정수 호출
            int num = Integer.parseInt(st.nextToken());

            //num이 1일 때 현재 숫자를 덱의 맨 앞에 추가
            if (num == 1) {
                d.addFirst(i);
            //num이 2일 때, 덱의 맨 앞에서 숫자를 제거한 후 현재 숫자를 덱의 맨 앞에 추가
            } else if (num == 2) {
                int top = d.removeFirst(); //맨 앞 요소를 제거하고 저장
                d.addFirst(i); //현재 숫자를 맨 앞에 추가
                d.addFirst(top); //제거한 숫자를 맨 앞에 추가
            } else {
                d.addLast(i);
            }
        }

        StringBuilder sb = new StringBuilder();

        //덱이 빌 때까지 모두 StringBuilder에 저장
        while (d.size() != 0) {
            sb.append(d.removeFirst() + " ");
        }

        System.out.println(sb);
    }
}