[자바] 백준 21508 - Список школ (java)

 문제 : boj21508

  타 언어 문제이므로 한글로 문제의 핵심 조건만 작성해본다.

 

1. 첫 줄에 이하 몇줄이 입력으로 들어올지에 대한 N이 주어진다.

2. 입력은 공백, 영어 대소문자, 숫자로 이루어져 있는데, 이 중 숫자만 뽑아낸게 학교 번호이다. 즉, "A41B"와 "41 AB"는 동일한 학교를 나타낸다.

3. 학교 번호 기준으로 각 학교가 몇 명 참가했는지 확인해서, 1명이상 5명이하가 참여한 학교의 학교 번호를 출력한다. 순서는 상관없다.

---

 

필요 알고리즘 개념

• 해시를 사용한 집합과 맵
  
  • 해시가 필요하다. 숫자로 처리되므로 그냥 배열같은걸로 처리해도 되지 않나 싶겠지만, 문제 어디에도 숫자가 몇 이하임이 제시되지 않았다. 따라서 문자열 길이가 100까지 가능하므로 100자리 숫자까지 판단해야 된다고 보는게 안전하므로, 숫자지만 문자열로 처리하는게 맞다.
• 정규식 혹은 파싱
  
  • 문자열에서 숫자 부분만 뽑아내기 위해 정규식 혹은 파싱을 할 수 있어야 한다. 이 글에서는 두 방식을 모두 풀이한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  결국 대소문자, 공백, 숫자가 존재하는 문자열에서 숫자부분만 뽑아내는게 문제의 핵심이다. 이 때 문제의 조건에서 제시되지 않은건 모두 가능하다고 생각해보자. 그렇다면 주의해야할 부분은 아래와 같다.

 

1. "1 ASDFASDFSDFJKSDFJ 9 ASDFASDF"와 같이 숫자가 떨어져 있어도 19를 뽑아낼 수 있어야 한다.

2. "123123...34234" 숫자가 몇까지 될 것인지 제한이 없으므로, 문자열의 최대 길이인 100에 따라 10^100-1 까지 표현 가능해야 한다. 따라서 int나 long 등으론 표현 불가하므로, 그냥 String 자체로 다뤄야 한다.

 

  직접 파싱한다면 아래처럼 할 수 있다.

String s = br.readLine();
StringBuilder num = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    if (c >= '0' && c <= '9')	// 숫자에 해당한다면
        num.append(c);	// StringBuilder에 추가한다.
}
String numStr = num.toString();

 

  정규식을 사용하면 아래처럼 할 수 있다. ' ', 'a-z', 'A-Z' 를 제외한것으로 공백, 소문자, 대문자를 제외한거다.

String numStr = br.readLine().replaceAll("[ a-zA-Z]", "");

 

 

  숫자부분만 문자로 남긴 numStr을 기준으로 HashMap을 key는 numStr, value는 해당 numStr이 등장한 횟수로 정의해서 사용해준다. 그럼 keySet을 순회하며 아래처럼 출력해주면 된다.

int cnt = 0;
StringBuilder answer = new StringBuilder();
for (String key : hm.keySet()) {	// 해시맵의 모든 key를 순회
    if (hm.get(key) >= 1 && hm.get(key) <= 5) {	// 해당 key의 value가 1~5라면 출력
        answer.append(key).append('\n');
        cnt++;
    }
}
System.out.println(cnt);
System.out.print(answer);

 

---

 

코드 (직접 파싱) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        HashMap<String, Integer> hm = new HashMap<>();
        while (n-->0) {
            String s = br.readLine();
            StringBuilder num = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c >= '0' && c <= '9')
                    num.append(c);
            }
            String numStr = num.toString();
            hm.put(numStr, hm.getOrDefault(numStr, 0) + 1);
        }

        int cnt = 0;
        StringBuilder answer = new StringBuilder();
        for (String key : hm.keySet()) {
            if (hm.get(key) >= 1 && hm.get(key) <= 5) {
                answer.append(key).append('\n');
                cnt++;
            }
        }
        System.out.println(cnt);
        System.out.print(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

코드 (정규식) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        HashMap<String, Integer> hm = new HashMap<>();
        while (n-->0) {
            String numStr = br.readLine().replaceAll("[ a-zA-Z]", "");
            hm.put(numStr, hm.getOrDefault(numStr, 0) + 1);
        }

        int cnt = 0;
        StringBuilder answer = new StringBuilder();
        for (String key : hm.keySet()) {
            if (hm.get(key) >= 1 && hm.get(key) <= 5) {
                answer.append(key).append('\n');
                cnt++;
            }
        }
        System.out.println(cnt);
        System.out.print(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}