[Hackerrank] Sherlock and the Valid String (Medium)

[Hackerrank] Sherlock and the Valid String - (String - Medium)

www.hackerrank.com/challenges/sherlock-and-valid-string/problem

Sherlock and the Valid String | HackerRank

---

문제

문자열 s가 입력될 때, 모든 문자의 개수가 동일하면 true 아니면 false인 문제다

여기서 1개의 문자열을 지울 수 있는 기회를 준다 

예를 들면, 

s = abc가 들어오면 True

s = abbc가 들어오면 a:1 b:2 c:1이고, 문자 b를 하나 지우면 a:1, b:1, c:1로 같아져서 True이다

s = aabbcd가 들어오면 a:2, b:2, c:1, d:1이고, 문자 하나를 지워도 같은 경우가 없으니 False이다

해결

ex) aabbccd

우선 map에 각 문자열의 개수를 넣는다 

a:2, b:2, c:2, d:1

그리고 다시 map에 개수를 Key로 하고, 그 개수의 개수를 value에 넣는다

2:3, 1:1

여기서 map에 1개만 있다면 YES,

map에 2개보다 많다면 NO,

map에 2개가 들어있을때, 경우에 따라 YES or NO이다

- YES인 경우 둘 중 1개는 값이 1이다

1. Key의 값이 1인 경우

- 해당 알파벳만 지워주면 map에는 1개만 남아 YES

2. Key의 값이 n인 경우

- 만약 n이 5라면, 알파벳이 5개 있는거라 1개를 지워도 4개가 남는다

- 완전이 지우는게 불가능하다면, 앞의 개수와 맞춰주면 된다

- 예를 들어, aaabbbcc의 경우

- a:3, b:3, c:2이다

다시 개수를 키로 하여 map을 만들면, 

- 3:2, 2:1 이다

- 여기서 c의 개수 1개를 생성해주면 a와 b처럼 c도 3개가 되므로 YES가 된다

- 따라서 Math.abs(keys.get(0) - keys.get(1)) == 1인 경우도 YES이다

public String isValid(String s) {

    Map<Character, Integer> map = new HashMap<>();

    for (char c : s.toCharArray()) {
        map.putIfAbsent(c, 0);
        map.computeIfPresent(c, (k,v) -> v+1);
    }
    List<Integer> list = new ArrayList<>();
    for (int i : map.values()) list.add(i);

    Map<Integer, Integer> map2 = new HashMap<>();

    for (int c : list) {
        map2.putIfAbsent(c, 0);
        map2.computeIfPresent(c, (k,v) -> v+1);
    }

    List<Integer> keys = new ArrayList<>();
    List<Integer> values = new ArrayList<>();

    for (int i : map2.keySet()) keys.add(i);
    for (int i : map2.values()) values.add(i);

    if (values.size() == 1) return "YES";
    if (values.size() == 2) {
        int one_value_key = 0;
        for (int i=0; i< values.size(); i++) if (values.get(i) == 1)  one_value_key = keys.get(i);
        if (values.contains(1) && Math.abs(keys.get(0) - keys.get(1)) == 1) return "YES";
        if (values.contains(1) && one_value_key == 1) return "YES";

    }
    return "NO";
}