반응형
문제 - Sherlock and the Valid String
문제 설명
1개를 지웠을 때 anagram을 만들 수 있는 조건을 충족하는지 판별하는 문제
Map
을 2개를 만들어 개수로 판별하도록 했다.
-
cMap
: 문자열이 몇 개씩 있는지를 저장하는 Map이다. -
fMap
: cMap에서 value들이 개수가 얼마나 되는지를 저장하는 Map이다. 이 Map을 활용해 문자열 삭제 여부를 판단한다. -
dCnt
: 삭제된 개수를 세는 변수이다. 반복문에서 판별할 때 쓰이며, 처음 한 번만 조건을 충족하게 하기 위해 쓰인다. -
반복문을 통해 입력값인 s로
cMap
에 개수를 저장한다. -
반복문을 통해
cMap
에서 value들의 개수를fMap
에 저장한다. -
만약 처음에 입력값이 모두 같은 문자가 들어온다면
YES
를 반환해 아래의 반복문을 돌지 않도록 한다. -
fMap
에서 판별하기 위해 key와 value값을 사용해 반복문을 돈다. -
삭제한다면 참값이 나올지 판별하기 위해 if문으로 조건을 만든다.
v === 1
: value 값이 1이어야 하는 이유는 개수가 다른 것이 2개 이상이면 1개를 삭제해도 개수가 맞지 않는 것이 남아 있기 때문에 결국에 답이NO
가 되게 될 것이다.(k - 1) % 2 === 0
: 여기서 key 값은 문자열에서 특정 문자의 개수인데, 이것에 1을 빼도 홀수 개라면 1개를 다 삭제하면 잘못 판별하는 경우가 생기기 때문에 이 조건을 충족해야 한다.dCnt === 0
: 앞의 두 조건을 충족하는 수가 여러 개 있을 때를 위한 조건이다. 처음에 조건을 만족하는 것만 조건문 안에 들어가도록 처리한 것이다.
-
key 값이 1이 아닐 경우에는 다 삭제하지 않고 key값만 변경시켜 값을 보존하기 위함이다.
-
조건문 안으로 들어왔으니 해당 요소를 삭제한다.
-
bCnt
를 1 증가시킴으로써 다시 이 조건문에 들어오지 않도록 한다. -
조건문 이후에 fMap의 크기가 1이라면 반복문을 더이상 돌지 않고 바로
YES
를 반환한다. -
위의 YES를 반환하는 부분에서 반환되지 못했다면 조건을 충족하지 못한 것이므로
NO
를 반환한다.
성공 코드
function isValid(s) {
let cMap = new Map(); // 1
let fMap = new Map(); // 2
let dCnt = 0; // 3
[...s].forEach((v) => (cMap.get(v) ? cMap.set(v, cMap.get(v) + 1) : cMap.set(v, 1))); // 4
[...cMap.values()].forEach((v) => (fMap.get(v) ? fMap.set(v, fMap.get(v) + 1) : fMap.set(v, 1))); // 5
if ([...s].every((v, i, arr) => v === arr[0])) return "YES"; // 6
for (let [k, v] of fMap) {
// 7
if (v === 1 && (k - 1) % 2 === 0 && dCnt === 0) {
// 8
if (k !== 1) fMap.set(k - 1, v); // 9
fMap.delete(k); // 10
dCnt++; // 11
}
if (fMap.size === 1) return "YES"; // 12
}
return "NO"; // 13
}
반응형