ehddud100698   1년 전

g 옵션이 있을때는 틀렸는데 빼주니까 정답처리가 되네요.

글로벌이든 아니든 FBI 가 있을때 true 값이 리턴되는 것은 같지않나요?

혹시 차이가 무엇인지 궁금합니다.

wizardrabbit   1년 전

안녕하세요, 자바스크립트 정규 표현식에서 전역 플래그 (정규 표현식에서의 'g') 를 사용하실 때는 주의하셔야 합니다!

RegExp에서의 lastIndex란

틀린 원인을 알기 위해 먼저 RegExp(정규 표현식 객체) 의 lastIndex 속성을 알아봅시다. lastIndex 속성은 정규 표현식에서 매칭을 어디까지 했는지를 저장하기 위한 속성이며, 초기 값은 0입니다.

정규 표현식에 전역 플래그를 사용한 경우에 한해,

매칭에 성공하면 매칭에 성공한 문자열의 마지막 인덱스 + 1 값이 저장되며, 실패하면 0 값이 저장됩니다.

▼ 아래의 예시를 확인해 보세요.

>  regex = new RegExp('FBI', 'g');
<- /FBI/g
>  regex.lastIndex
<- 0
>  regex.test('01FBI56');
<- true
>  regex.lastIndex
<- 5

예시에서는 '01FBI56' 문자열에서 매칭에 성공해 lastIndex 값이 탐색을 한 마지막 문자열인 'I' 문자열의 다음 인덱스를 가리키고 있습니다.

틀리는 원인

그렇다면 이제 틀린 원인을 알아봅시다. 앞서 매칭에 성공할 경우 lastIndex의 값이 업데이트된다는 것을 이제 알고 있습니다. 같은 정규 표현식 객체에 대해 매칭을 시도할 경우, lastIndex 에 해당하는 인덱스부터 탐색을 시작한다는 것이 작성하신 코드에서 예상치 못한 다른 결과가 나올 수 있는 원인입니다.

▼ 아래의 예시를 확인해 보세요.

>  regex = new RegExp('FBI', 'g');
<- /FBI/g
>  regex.lastIndex
<- 0
>  regex.test('I-am-FBI');
<- true
>  regex.lastIndex
<- 8
>  regex.test('I-am-FBI');
<- false
>  regex.lastIndex
<- 0

같은 정규 표현식에 대해 똑같은 문자열을 매칭하고 있음에도 불구하고 true가 나왔다가 false가 나오는 말도 안 되는 상황이 일어나고 있습니다! 하지만 이제 우리는 그 이유를 알고 있습니다. 바로 lastIndex의 값 때문이죠.

첫 번째 매칭에서는 lastIndex의 값이 0이므로 당연히 매칭에 성공하여 true가 반환됩니다. 성공했으므로 마지막 문자열인 'I' 문자열의 다음 인덱스인 8이 lastIndex에 저장됩니다.

두 번째 매칭에서는 lastIndex의 값이 8이므로 인덱스가 8인 문자열부터 매칭을 시도합니다만, 이미 인덱스 8은 매칭하고자 하는 문자열의 인덱스 범위를 벗어나므로 매칭이 끝나고, 매칭에 실패하게 됩니다. 그래서 false가 반환됩니다. 실패했으므로 lastIndex의 값은 0이 됩니다.

따라서 작성하신 코드에는 아래와 같은 반례가 만들어지게 됩니다:

입력:
I-AM-FBI
I-AM-FBI
I-AM-FBI
I-AM-FBI
I-AM-FBI

정답:
1 2 3 4 5

출력:
1 3 5

해결 방법

그렇다면 이 문제를 어떻게 해결해야 할까요? 1) lastIndex가 항상 0이 되도록 유지하거나, 2) 아예 정규 표현식 객체를 매번 새로 만들어 lastIndex 값이 항상 0을 유지하도록 한다면 해결할 수 있겠네요.

1) 의 경우에는 정규 표현식을 한 번 매칭한 이후, 코드에

regex.lastIndex = 0;

을 추가하시면 됩니다.

2) 의 경우에는 정규 표현식 그대로 대입하는 방법입니다.

if (/FBI/g.test(el)) {
    result += `${idx + 1} `;
}

어느 쪽을 선택하시든 코드가 통과한다는 것을 확인하실 수 있을 것입니다. 자세한 내용은 https://developer.mozilla.org/... 에서 '전역 플래그와 test()' 문단을 확인하시면 될 것 같습니다.

궁금증이 해결되었기를 바랍니다!

ehddud100698   1년 전

와.. 진짜 너무 친절하게 댓글을 달아주셔서 이해가 한방에 되었습니다.

자바스크립트로 푸시는분중에 누구코드를 참고해야될지 했는데 문제도 많이 푸셔서 앞으로 wizardrabbit 님 푸신 문제로 저도 풀고 코드 참고 하면 될 것같네요. 정말 감사합니다 ㅠㅠ 깃허브 팔로우했습니다! 

저도 같은 문제로 고민하시는분 있으면 꼭 해당부분 알려드리겠습니다 (꾸벅) 정말감사합니다!

ehddud100698   1년 전

토탐정님 질문이 있습니다. 혹시 큐처럼 타 언어와 달리 자바스크립트에서는 라이브러리가 없는 자료구조 같은경우는 어떻게 하시는 편이신가요? 이전에 10845번 문제를 푸신것을 봤는데 배열로 푸셨던데 이러면 shift나 unshift 에서는 O(n) 이 되어버리지 않나요?

wizardrabbit   1년 전

안녕하세요?

말씀하신 대로 당시의 제 풀이에서 shift(), unshift() 를 사용하는 경우는 O(n)이 되어버리는 게 맞습니다. 비효율적인 풀이입니다. 10845번은 입력량이 압도적으로 많지는 않아서 통과할 수 있었지만, 해당 풀이와 똑같은 풀이로 18258(큐 2)번을 푸려고 시도할 경우 당연히 시간 초과가 납니다.

JavaScript는 큐에 대한 자료구조를 지원하지 않으므로 연결 리스트 등을 이용한 방법으로 직접 큐 클래스를 구현해 사용하는 것이 권장됩니다. 이것에 대해서는 그냥 인터넷에 '자바스크립트 큐 구현하는 법' 정도만 검색해도 다양한 클래스들이 많이 나옵니다.

제가 어떻게 큐를 사용하고 있느냐를 물어보신다면 저는 그냥 평소에 백준에서 문제 풀 때는 클래스 구현을 굳이 하지는 않고 여전히 배열을 사용하고 있습니다. 하지만 이 경우 unshift(), shift()에 대해서  O(n)의 시간복잡도가 나올 수 있으므로, 저는 원소를 추가하는 방법은 평범하게 push()를 사용하고, 원소를 제거할 때에는 배열에서 첫 번째 원소를 shift()로 제거하는 대신 그냥 첫 번째 원소를 사용하지 않는다 치고 시작 원소를 한 칸 오른쪽으로 옮기는 방법을 사용했습니다.

즉, 단순한 두 포인터 방법을 사용한 큐이며, 큐에서 원소를 제거할 때 직접 배열에서 원소를 제거하지 않는 대신 큐가 시작되는 인덱스와 끝나는 인덱스를 저장하는 방식으로 사용한다는 뜻입니다. 이 방법은 제거된 원소가 그대로 메모리를 차지하므로 메모리 면에서는 조금 손해를 보는 방법이기는 합니다.

결론적으로는 클래스를 통한 구현을 추천합니다.

preview

위에서 설명한 제가 사용하는 평소 방법대로 큐 2 문제를 제출했습니다만 괜찮은 시간대로 통과합니다.

preview

ehddud100698   1년 전

감사합니다 토탐정님. 10845번을 class queue를 구현해서 방금 풀었는데 제가 코테에서도 이 class queue를 구현할 수 있을까란 생각이 드네요. 열심히 외우거나 토탐정님처럼 두 포인터 개념을 공부해야겠습니다. 두포인터로 앞에있는 요소를 없애는 방법은 정말 생각도 못했네요. 우문현답 주셔서 정말 감사합니다. 

댓글을 작성하려면 로그인해야 합니다.