글 읽기 - 반례가 있는지 궁금합니다

readiz 3년 전 0

nodejs 로 푸신 다른 분들 풀이 보니 정규표현식 쓰신 분들이 보이는데.. 해당 풀이가 깔끔해보여 저도 그렇게 접근해야했나 싶지만

제가 시도해본 방법에서 반례가 따로 존재하는지 궁금합니다. 17% 정도에서 계속 fail이 나는데, 아래 예시들과 게시판의 반례들은 다 통과 되는 것 같거든요.

the quick brown fox.
the <i><b>quick</b> brown</i> fox.
<doc>fox & socks.</doc>
3x+5>7
Null: &x00;
<doc>the quick brown fox.
the <i>quick <b>brown</i></b> fox
fox & socks.
3x+5>7
Null: &x0;

some ascii text????2#$@#$@#$ OK
balanced  <tag1><tag2>tags</tag2>brown</tag1> OK
additional <tag1><tag2>tag</tag2>without</tag1><tag3/>closing context. OK
popped off <tag1><tag2>in wrong</tag1></tag2> order.
stack non-empty <tag1>at</tag1>end<tag1>.
pop<tag1></tag1>from</tag2>empty stack.
incorrect <tag?><b>syntax</b>for tag</tag?>.
incorrect <tag/tag>syntax for tag</tag/tag>.
no match >tag
no match <tag
37<38 OK
38>37 OK
ampersand&ersand OK
hex number&xab99; OK
hex number&xAB99; OK
semicolon;part of ascii text OK
odd number of hex digits&x345;
ampersand without closing semicolon>xxx
tags that are not lowercase <Tag1>hello</Tag1>
blank line follows

multiple tags of the same name, nested: <tag1><tag1><tag1> <tag1/>hello </tag1> </tag1></tag1>

&at;
&bmp;
&l<t;
&aaa;
&xax;
</>
<></>
<><
/>
<b><
/b>


<>

function solution(scanner) {
    const r = [];
    const lines = scanner.readAll().split('\n');
    for (let line of lines) {
        console.log('-------------------------------------');
        console.log('Current Line:', line);
        console.log('-------------------------------------');

        const stack = [];
        // 1. Context Tag Stack 구성
        let pos = 0;
        let validStack = true;
        while (line.indexOf('<', pos) > -1) {
            const curTagStartPos = line.indexOf('<', pos);
            const curTagEndPos = line.indexOf('>', curTagStartPos);
            const tagName = line.substr(curTagStartPos + 1, curTagEndPos - curTagStartPos - 1);
            console.log(curTagEndPos, tagName);
            if (curTagStartPos !== -1 && curTagEndPos !== -1) {
                // 유효 TagName 검사
                // 빈거 검사..
                if (tagName === '' || tagName === '/') {
                    console.log('tagName is empty! invalid!');
                    validStack = false;
                    break;
                }
                // / 를 제외하고 검사..
                let tagNameforValidation = tagName;
                if (tagName.startsWith('/')) {
                    tagNameforValidation = tagNameforValidation.substr(1);
                } else if (tagName.endsWith('/')) {
                    tagNameforValidation = tagNameforValidation.substr(0, tagNameforValidation.length - 1);
                }
                const checkInvalidChar = tagNameforValidation.split('').filter(_ => !['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h',
                                                                                      'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p',
                                                                                      'q', 'r', 's', 't', 'u', 'v', 'w', 'x' ,'y', 'z',
                                                                                      '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'].includes(_));
                if (checkInvalidChar.length > 0) {
                    console.log('tagName:', tagName, 'is invalid! (reason: invalid tag char detected)', checkInvalidChar);
                    validStack = false;
                    break;
                }

                // 여는 태그 / 닫는 태그
                if (tagName.startsWith('/')) {
                    const stackTop = stack.pop();
                    if (tagName.substr(1) === stackTop) {
                        // 이 경우 올바른 경우임
                        console.log(stackTop, tagName, 'matched!');
                    } else {
                        // 올바르지 않은 스택 구성, false 세팅.
                        console.log(stackTop, tagName, 'unmatched stack! invalid.');
                        validStack = false;
                        break;
                    }
                } else if (tagName.endsWith('/')) {
                    // 이 경우 Push 되지 않음
                    console.log(tagName, 'not added.');
                } else {
                    console.log(tagName, 'added.');
                    stack.push(tagName);
                }
                let newLine = line.split('');
                newLine.splice(curTagStartPos, curTagEndPos - curTagStartPos + 1);
                line = newLine.join('')
                console.log('NewLine:', line);
                pos = 0;
            } else {
                validStack = false;
                break;
            }
        }
        if (validStack === false) {
            r.push('invalid');
            continue;
        }
        // 2. Context Tag Stack Validation
        if (stack.length !== 0) {
            console.log('invalid stack remained:', stack);
            r.push('invalid');
            continue;
        }
        // 3. &xHEX; 검사
        pos = 0;
        let validAmp = true;
        while (line.indexOf('&', pos) > -1) {
            let ampStartPos = line.indexOf('&', pos);
            let ampEndPos = line.indexOf(';', ampStartPos);
            const ampName = line.substr(ampStartPos + 1, ampEndPos - ampStartPos - 1);
            if (ampStartPos !== -1 && ampEndPos !== -1) {
                if (['gt', 'lt', 'amp'].indexOf(ampName) > -1) {
                    console.log('ampName:', ampName, 'is valid.');
                } else if(ampName.startsWith('x')) {
                    const HEX = ampName.substr(1);
                    // 길이 짝수인지 검사
                    if (HEX.length % 2 === 0 && HEX.length > 0) {
                        // 문자열 구성 검사
                        const checkInvalidChar = HEX.split('').filter(_ => !['A', 'B', 'C', 'D', 'E', 'F', 'a', 'b', 'c', 'd', 'e', 'f', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'].includes(_));
                        if (checkInvalidChar.length > 0) {
                            console.log('ampName:', ampName, 'is invalid! (reason: invalid HEX char)');
                            validAmp = false;
                            break;
                        } else {
                            console.log('ampName:', ampName, 'is valid.');
                        }
                    } else {
                        console.log('ampName:', ampName, 'is invalid! (reason: HEX length is not even)');
                        validAmp = false;
                        break;
                    }
                } else {
                    console.log('ampName:', ampName, 'is invalid! (reason: Not available char with &)');
                    validAmp = false;
                    break;
                }
                let newLine = line.split('');
                newLine.splice(ampStartPos, ampEndPos - ampStartPos + 1);
                line = newLine.join('')
                console.log('NewLine:', line);
                pos = 0;
            } else {
                validAmp = false;
                break;
            }
        }
        if (validAmp === false) {
            r.push('invalid');
            continue;
        }

        // 4. 와서는 안되는 문자열이 있는지 확인
        // &, <, > 등
        const checkInvalidChar = line.split('').filter(_ => ['&', '<', '>'].includes(_));
        if (checkInvalidChar.length > 0) {
            console.log('line is invalid! invalid char is remained:', line);
            r.push('invalid');
            continue;
        }
        // 다 통과했으면, valid를 부여
        console.log('line is valid. final:', line);
        r.push('valid');
    }

    return r.join('\n');
}

/////////////////////////////////////////////////////////////////////////////////
// Readiz BOJ JS Util Start
/////////////////////////////////////////////////////////////////////////////////
(function readizInit() {
    const isDebug = process.argv[2] === 'readizDebug';
    const _input = (!isDebug) ?
        require('fs').readFileSync('/dev/stdin') :
        require('fs').readFileSync(process.argv[1].replace('.js', '_input.txt'));
    let _index = 0;
    const _index_max = _input.length;
    const scanner = {
        readInt: () => {
            let result = 0;
            let isMinus = false;
            while ((!(_input[_index] & 0x10) && _input[_index] !== 45) && _index < _index_max) ++_index;
            if (_input[_index] === 45) { isMinus = true; ++_index; }
            while ((_input[_index] & 0x10) && _index < _index_max) { result = result * 10 + (_input[_index] & 0x0f); ++_index; }
            return isMinus ? -result : result;
        },
        readString: () => {
            while ((_input[_index] === 0x0a || _input[_index] === 0x20) && _index < _index_max) ++_index;
            const startIdx = _index;
            while (!(_input[_index] === 0x0a || _input[_index] === 0x20) && _index < _index_max) ++_index;
            const endIdx = _index;
            return _input.toString('utf-8', startIdx, endIdx);
        },
        readLine: () => {
            while ((_input[_index] === 0x0a) && _index < _index_max) ++_index;
            const startIdx = _index;
            while (!(_input[_index] === 0x0a) && _index < _index_max) ++_index;
            const endIdx = _index;
            return _input.toString('utf-8', startIdx, endIdx);
        },
        readAll: () => {
            _index = _index_max;
            return _input.toString('utf-8', 0, _index_max);
        }
    }
    if (!isDebug) {
        global.console = {
            log: () => {},
            warn: () => {},
            info: () => {},
            debug: () => {},
            error: () => {}
        }
        const answer = solution(scanner);
        process.stdout.write(answer + '\n');
    } else {
        while (_index !== _index_max) {
            process.stdout.write('--------------------------------------------\n');
            process.stdout.write('New Start + Log\n');
            process.stdout.write('--------------------------------------------\n');
            const start = _index;
            const answer = solution(scanner);
            const end = _index;
            process.stdout.write('----------------------\n');
            process.stdout.write('Input\n')
            process.stdout.write('----------------------\n');
            process.stdout.write(_input.toString('utf-8', start, end).trim() + '\n');
            process.stdout.write('----------------------\n');
            process.stdout.write('Answer\n')
            process.stdout.write('----------------------\n');
            process.stdout.write(answer + '\n');
        }
    }
})();

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

문제

문제

출처

ICPC

반례가 있는지 궁금합니다

readiz 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말