[백준] #10807 개수 세기

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

10807번: 개수 세기

 

---

 

문제 이해하기

문제 자체는 크게 어렵지 않다!

1. 입력 받을 정수 개수 n 받아오기
2. 공백으로 구분되어있는 정수들이 담긴 문자열 받아오기
3. 찾고자 하는 값 v 를 받은 뒤, 2번 과정에서 받은 정수들 중에 몇 개가 있는지 파악하기

따라서 내가 생각한 문제의 포인트는 아래와 같다

1. 사용자에게 받은 문자열을 공백을 기준으로 분리하기
2. 찾고자하는 값 v를 문자열에서 찾기

 

문제 해체하기

 

0. 정수 n 입력받기

입력 방법에 대해서 한번쯤은 정리가 필요할 것 같아 내용을 추가하였다.

JAVA에서 사용자에게 값을 받는 방법에는 두가지가 있다.

 

특별한 경우가 아니라면, 속도 측면에서 더 우세한 BufferedReader를 주로 사용하게 되는 것 같다.

 

자세한 내용은 따로 정리해두었다.

https://muunii.tistory.com/7

[JAVA] BufferedReader & Scanner & System.in

 

1. 사용자에게 받은 문자열을 공백을 기준으로 분리하기

BufferedReader 로 입력을 받게 되면 하나의 String 값에 공백으로 값이 구분되어 있기 때문에

비교하기 위해선 공백을 기준으로 문자열을 잘라서 값을 알아내야 한다.

즉 문자열을 각자의 값들로 분리를 해야한다.

Java에서 문자열을 특정 구분자로 분리할 수 있는 방법은 크게 2가지가 있다

1. split( )
2. StringTokenizer( )

split과 StringTokenizer 또한 동작 방식에서 차이가 있기 때문에, 속도에서도 차이가 발생한다.

보통 데이터 양이 적을 때에는, split은 값을 배열에 담아 반환하지만 StringTokenizer 는 데이터를 바로 잘라서 반환하기 때문에 속도면에서 더 우세하다.

하지만 StringTokenizer는 Legacy Class(; 더이상 쓰기를 권장하지 않는 클래스) 라는 공식 문서가 있으며, split으로 대체할 것을 권장하고 있다.

 

특정 상황(ex. 구분자가 한 문자인 경우 등) 에서는 StringTokenizer가 split보다 나은 성능을 보이기 때문에 당장의 문제 풀이에서는 사용하지만,

그래도 StringTokenizer를 레거시 클래스로 분류한 이상, split 을 사용하는데 익숙해지는 것이 더 좋아보인다

 

(필자 또한 블로그를 정리하면서 알게 되었기 때문에 지금은 StringTokenizer 를 사용했다,,,)

 

구체적인 내용은 나중에 추가로 정리해보도록 하겠다.

(참고한 내용)

https://velog.io/@effirin/Java-StringTokenizer와-Split-메서드-언제-써야할까

https://blog.naver.com/makga87/221949199317

[StringTokenizer VS String.split] 누가 더 빠른가

 

2. 찾고자하는 값 v를 문자열에서 찾기

위 과정을 통해서 분리된 값들을, 찾고자하는 값과 비교해야하는데

3가지 방법을 통해서 비교해볼 수 있다

 

1) 값들을 차례대로 넣은 배열 arr[ ] 를 생성 → 차례대로 배열을 돌며 동일한 값이 있는 경우 count 를 올린다

 

1번 방법은 배열을 생성하고, 해당 배열을 for 문으로 돌며 값을 할당하고, 다시 for문으로 처음부터 끝까지 값들을 비교해야 하기 때문에 메모리적으로나, 시간적으로나 비효율적이라는 생각이 들었다.

문자열을 잘라서 바로 비교해버리면 되지 않을까?

 

따라서 개선된 방법을 생각해보았다.

 

2) 문자열을 차례대로 잘라 값 v와 비교하고, 같다면 count +1 / 같지 않다면 넘어간다.

 

 

HashMap을 이용한 방법도 존재한다.

 

3) HashMap을 통해서 잘라낸 값을 Key 값으로, count 를 Value 값으로 매핑하고, v 값을 key로 가지는 value(count) 를 출력한다.

→ 문자열에서 분리한 값을 HashMap의 Key 값으로 할당하는데,

만약 Map에 Key 값이 없다면 값을 새로 할당하고, 있다면 해당 Key값에 매핑된 count 값을 올려준다.

이때, Map 을 사용하기 위해선 두가지 포인트를 고려해보아야 한다.

 

3-1) 찾고자 하는 V 값 이 없는 경우, 0이 출력되어야 함

→ HashMap에서 존재하지 않는 key 값에 접근하면 null 을 출력할 것이다. 따라서 key 값이 경우에 대한 예외 처리를 해주어야 하는데, 총 2번의 예외처리가 필요하다.

• HashMap에서 key에 해당하는 count 값을 ++ 해야하는데, map에 처음 추가된 값일 때
• 최종 출력에서 v를 key로 가지는 값이 없을 때

해당 문제는 Map의 getOrDefault 메소드를 사용하면 해결할 수 있다.

default V getOrDefault(Object key, V defaultValue) {
        V v;
        return (((v = get(key)) != null) || containsKey(key))
            ? v
            : defaultValue;
    }

Key 값과 대체할 Value V 값을 받아온다.

만약, Key 값로 매핑된 값이 존재한다면 해당 key 값의 Value를 가져오지만

존재하지 않는 경우 대체값 defaultValue 가 매핑되게 된다.

 

3-2) key 값이 존재한다면 (n번째로 나온 숫자라면) 매핑되어 있는 count 값을 어떻게 올릴 것인지

• replace( ) : 지정된 키가 이미 맵에 존재하는 경우 매핑되어있는 값을 새 값으로 대체하고, 없다면 아무것도 하지 않음
• put( ) : 지정된 키가 이미 맵에 존재하는 경우 매핑되어있는 값을 새 값을 대체하고, 없더라도 값을 저장하거나 대체한다.

→ 즉 Key가 이미 존재하는 경우에만 값을 대체할 경우에는 replace( )가 조금 더 적합해보이지만,

map에 새로운 데이터를 추가하거나, 덮어 씌우는 과정이 필요한 경우엔 put( )이 조금 더 적합해 보인다 생각한다.

 

 

코드

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int v = Integer.parseInt(br.readLine());

 

세 가지 방법 모두 공통적으로 BufferedReader 를 통해서 n과 숫자들, v 값 입력을 받아오고,

숫자들을 StringTokenizer로 분리해주었다.

 

방법 1 : int[ ] arr

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

StringTokenizer 에서 관리하는 character 값들을 int 형으로 변환하여 (Integer.parseInt ( )) 배열에 할당해주었다

int count = 0;
for(int num : arr) {
    if(num == v) count++;
}

이후 해당 배열을 돌면서 v 값과 동일한지 확인 후, 같다면 count 값을 +1 해주었다.

 

 

방법 2 : 배열 없이 바로 count

int count = 0;
for(int i=0; i<n; i++){
    if(v == Integer.parseInt(st.nextToken())){
        count++;
    }
}

StringTokenizer 에서 관리하는 값을 굳이 배열에 할당하고, 다시 꺼내볼 필요가 없다.

따라서 n개의 숫자에 맞춰서 값을 꺼내 바로 비교 후, count 값을 +1 해주었다.

 

 

방법 3 : HashMap<Key, Value>

Map<Integer, Integer> map = new HashMap<>();
while (st.hasMoreTokens()) {
    int m = Integer.parseInt(st.nextToken());
    map.put(m, map.getOrDefault(m, 0) + 1);
}

if (map.containsKey(v)) {
    System.out.print(map.get(v));
} else {
    System.out.print(0);
}

HashMap을 만든 후, StrignTokenizer에 있던 값이 빌 때까지 map에 넣어준다.

 

map.put(key 값, map.getOrDefault(m, 0) + 1);

이때, map.getOrDefault 를 이용해

만약 m을 key로 가지는 값이 있다면 매핑된 value(count)값을,

없다면 0을 가져오도록 하여 count + 1 를 수행해준다.

 

이후 map에 찾고자하는 v 값이 있다면, v 값에 매핑된 count 값을,

없다면 문자열에 없었던 숫자이기 때문에 0이 출력되도록 한다.

 

 

전체 코드

방법 1

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(br.readLine());
				int v = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int count = 0;
        for(int num : arr) {
            if(num == v) count++;
        }
        System.out.println(count);
    }
}

 

 

방법 2

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(br.readLine());
        int v = Integer.parseInt(br.readLine());
        int count = 0;
        for(int i=0; i<n; i++){
            if(v == Integer.parseInt(st.nextToken())){
                count++;
            }
        }
        System.out.print(count);
    }
}

 

 

방법 3

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(br.readLine());
				int v = Integer.parseInt(br.readLine());
        Map<Integer, Integer> map = new HashMap<>();
        while (st.hasMoreTokens()) {
            int m = Integer.parseInt(st.nextToken());
            map.put(m, map.getOrDefault(m, 0) + 1);
        }
        if (map.containsKey(v)) {
            System.out.print(map.get(v));
        } else {
            System.out.print(0);
        }
    }
}

 

 

결과

위에서부터 아래 순으로 방법3 -> 방법2 -> 방법1

 

 

정리

얼마전 이 문제를 다시 접했을 때, 기존의 코드(방법1)를 보지 않고 내 생각대로 다시 코드를 작성하였었고(방법2), 그 결과 더 단축된 시간에 해결할 수 있었다.

하지만 문제를 조금 더 고민하는 과정에서 HashMap을 통해서도 문제을 해결해 볼 수 있으며,

특별한 고민 없이 익숙하게 사용하고 있었던 StringBuilder 와 Scanner / Split 과 StringTokenizer 에 대해서 다시 한번 공부해 볼 수 있었던 좋은 기회였던 것 같다.