알고리즘 재활 1일차 - 백준 1620, 10828, 1764번

오랜만에 알고리즘이라 재활치료 시작합니다..

Solved 클래스 높히기 아자아자 아장응애 ㅋㅋ

 

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

 

포켓몬 도감이 들어온다.

1번 피카츄~

2번 파이리~

...

 

이후 숫자가 주어지면 해당 번호의 포켓몬이 무엇인지

포켓몬 이름이 주어진다면 도감 번호가 무엇인지 출력해야한다.

빠르게 Map<> 구조를 떠올려주고, 중복이 없으니 hash를 생각했다

 

다만 key로 value 조회는 수월하지만, value로 key를 찾는건 다소 비효율적이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
 
public class Main { // S4 1620 나는야 포켓몬 마스터 다솜이
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
 
        HashMap<String, String> poketmon = new HashMap<>();
 
        for (int i = 1; i <= N; i++) {
            poketmon.put(br.readLine(), String.valueOf(i));
        }
 
        for (int i = 0; i < M; i++) {
            String cmd = br.readLine();
            if (poketmon.containsKey(cmd)) {
                sb.append(poketmon.get(cmd));
                sb.append("\n");
            } else {
                sb.append(getkey(poketmon, cmd));
                sb.append("\n");
            }
        }
        System.out.println(sb);
    }
 
    public static <K, V> K getkey(HashMap<K, V> map, V value) {
        for (K key : map.keySet()) {
            if (value.equals(map.get(key))) {
                return key;
            }
        }
        return null;
    }
}

 

처음에 보자마자 풀었던 방식은

Map에 모든 벨류를 뒤져가며 찾아주었는데 이러니 시간 초과가 발생했다.

도감이 무려 100,000이었자네

따라서 key-value 형태로 하나 만들어주고, 반대로 value-key 형태로 만들어줬다.

 

import java.io.*;
import java.util.*;
 
public class Main { // S4 1620 나는야 포켓몬 마스터 다솜이
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
 
        HashMap<String, String> nameToNumber = new HashMap<>();
        HashMap<String, String> numberToName = new HashMap<>();
 
        for (int i = 1; i <= N; i++) {
            String name = br.readLine();
            String number = String.valueOf(i);
            nameToNumber.put(name, number);
            numberToName.put(number, name);
        }
 
        for (int i = 0; i < M; i++) {
            String cmd = br.readLine();
            if (nameToNumber.containsKey(cmd)) {
                sb.append(nameToNumber.get(cmd));
            } else {
                sb.append(numberToName.get(cmd));
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}
 

 

보다 빠르게 조회할 수 있게 됐다.하나의 Map에 같이 담아도 좋은 방법인것 같다

---

 

Boj 10828 스택

 

 

기본적인 스택구조 이해 문제이다.

스택에 대한 기본적인 이해와 메서드 이해만 있다면 단순 구현문제이다.

 

import java.io.*;
import java.util.*;
 
public class Main { // S4 10828 스택
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        int N = Integer.parseInt(st.nextToken());
        Stack<Integer> stack = new Stack<>();
 
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            String cmd = st.nextToken();
            switch (cmd) {
                case "push":
                    stack.push(Integer.parseInt(st.nextToken()));
                    break;
                case "top":
                    sb.append(stack.isEmpty() ? -1 : stack.peek());
                    sb.append("\n");
                    break;
                case "pop":
                    sb.append(stack.isEmpty() ? -1 : stack.pop());
                    sb.append("\n");
                    break;
                case "empty":
                    sb.append(stack.isEmpty() ? 1 : 0);
                    sb.append("\n");
                    break;
                case "size":
                    sb.append(stack.size());
                    sb.append("\n");
                    break;
            }
        }
        System.out.println(sb);
    }
}
 

 

가볍게 해줍시다. 

---

 

Boj 1764 듣보잡

 

한번 더 등장하는 파이리..

1번도 듣지 못한 이름 리스트와 

1번도 보지 못한 이름 리스트가 들어온다.

두 리스트에 중복적으로 나오는 이름이라면 듣도 보도 못한거니까 듣보잡이다.

 

중복된 데이터가 없어야 하므로 HashSet 구조를 떠올려주고,

retainAll()이라는 메서드를 통해 두 Set에 중복된 데이터를 찾아 주었다.

이후엔 정렬해야 했기에 Collection.sort 로 마무리.

 

retainAll() 메서드 참고 블로그

 

import java.io.*;
import java.util.*;
 
public class Main { // S4 1764 듣보잡
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
 
        HashSet<String> neverSeen = new HashSet<>();
        HashSet<String> neverHeard = new HashSet<>();
 
        for (int i = 0; i < N; i++) {
            String name = br.readLine();
            neverSeen.add(name);
        }
 
        for (int j = 0; j < M; j++) {
            String name = br.readLine();
            neverHeard.add(name);
        }
 
        neverSeen.retainAll(neverHeard);
        List<String> answer = new ArrayList<>(neverSeen);
        Collections.sort(answer);
 
        sb.append(answer.size());
        sb.append('\n');
        for (int i = 0; i < answer.size(); i++) {
            sb.append(answer.get(i));
            sb.append('\n');
        }
 
        System.out.println(sb);
    }
}
 

 

물론 간단하게 set 하나로 contain 상태면 리스트에 추가하는 방식으로도 가능하다

 

import java.io.*;
import java.util.*;
 
public class Main { // 1764 듣보잡 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
 
        HashSet<String> neverSeen = new HashSet<>();
        List<String> names = new ArrayList<>();
 
        for (int i = 0; i < N; i++) {
            neverSeen.add(br.readLine());
        }
 
        for (int j = 0; j < M; j++) {
            String name = br.readLine();
            // 여기서 듣보잡 검증
            if (neverSeen.contains(name)) {
                names.add(name);
            }
        }
 
        Collections.sort(names);
 
        sb.append(names.size()).append('\n');
        for (String name : names) {
            sb.append(name).append('\n');
        }
 
        System.out.print(sb);
    }
}