=========================================================================================
※ 문제 링크
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"
'지식이 늘었다' 카테고리의 다른 글
[cve-2019-9978] 특정 파라미터를 이용한 wordpress 원격 명령 실행 공격 (0) | 2019.06.07 |
---|---|
[Hackerrank - algorithm] Sherlock and Anagrams (0) | 2019.01.19 |
[Hackerrank - algorithm] Highest Value Palindrome (0) | 2019.01.19 |
[Hackerrank - algorithm] Array Manipulation (0) | 2018.12.03 |
[Hacker_rank - SQL] Projects (0) | 2018.11.14 |