본문 바로가기

지식이 늘었다

[Hackerrank - algorithm] Sherlock and the Valid String

=========================================================================================

※ 문제 링크

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

=========================================================================================


한 문자열을 입력 받았을 때 문자열 내 문자 빈도수가 일치하는지 확인하는 문제.

단, 문자 빈도수가 일치하지 않을 경우 한번의 삭제 기회가 주어진다.


변수는 다음과 같다.

s = 문자열


예를 들어, 

1) s = aabbcd 를 입력받았을 경우 "NO"  (a = 2, b = 2, c = 1, d =1)

2) s = aabbc 를 입력받았을 경우 "YES" (a=2, b=2, c=1 이지만 c를 지우면 가능)

3) s = aabbcc 를 입력받았을 경우 "YES" (a=2, b=2, c=2)

4) s = aabbccc 를 입력받았을 경우 "YES" (a=2, b=2, c=3 이지만 c 한개를 지우면 가능)



문제 해결 프로세스는 다음과 같다.

1) 각 문자별 빈도수를 map에 저장하고, 각 빈도수별 map을 생성 -> O(n)

 ex) aabbccd -> 문자별 빈도수 : {a:2, b:2, c:2, d:1}, 빈도수 : {1:1, 2:3}


2) 문자열 빈도수의 values()들을 set으로 만들어 

 2-1) 길이가 1이면 "YES"

 2-2) 길이가 2초과이면 "NO"

 2-3) 길이가 2일 경우, 

  2-3-1) values() 에서 작은 값이 1이고 빈도수가 1이면 "YES"

  2-3-2) 두개의 차이가 1이고 큰 값의 빈도수가 1이면 "YES"

  2-3-3) 그 이외일 경우 "NO"