[Algorithm] 백준 5397 - 키로거 (Node / C#)

문제

https://www.acmicpc.net/problem/5397

 

풀이

1. Node.js(fs)

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const T = parseInt(input[0]);

function processKeyLogger(str) {
    const leftStack = [];
    const rightStack = [];

    for (let char of str) {
        if (char === '<') {
            if (leftStack.length > 0) {
                rightStack.push(leftStack.pop());
            }
        } else if (char === '>') {
            if (rightStack.length > 0) {
                leftStack.push(rightStack.pop());
            }
        } else if (char === '-') {
            if (leftStack.length > 0) {
                leftStack.pop();
            }
        } else {
            leftStack.push(char);
        }
    }

    return leftStack.join('') + rightStack.reverse().join('');
}

let output = '';
for (let i = 1; i <= T; i++) {
    output += processKeyLogger(input[i]) + '\n';
}

console.log(output.trim());

 

2. Node.js(readLine)

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let T;
let currentCase = 0;

function processKeyLogger(str) {
    const leftStack = [];
    const rightStack = [];

    for (let char of str) {
        if (char === '<') {
            if (leftStack.length > 0) {
                rightStack.push(leftStack.pop());
            }
        } else if (char === '>') {
            if (rightStack.length > 0) {
                leftStack.push(rightStack.pop());
            }
        } else if (char === '-') {
            if (leftStack.length > 0) {
                leftStack.pop();
            }
        } else {
            leftStack.push(char);
        }
    }

    return leftStack.join('') + rightStack.reverse().join('');
}

rl.on('line', (line) => {
    if (!T) {
        T = parseInt(line);
    } else {
        console.log(processKeyLogger(line));
        currentCase++;
        if (currentCase === T) {
            rl.close();
        }
    }
});

3. C#

using System;

class Program
{
    static void Main()
    {
        int caseNumber = 1;
        
        while (true)
        {
            string line = Console.ReadLine();
            if (line[0] == '-') break;
            
            int openCount = 0;
            int operations = 0;
            
            foreach (char c in line)
            {
                if (c == '{')
                {
                    openCount++;
                }
                else if (c == '}')
                {
                    if (openCount > 0)
                    {
                        openCount--;
                    }
                    else
                    {
                        operations++;
                        openCount++;
                    }
                }
            }
            
            operations += openCount / 2;
            
            Console.WriteLine($"{caseNumber}. {operations}");
            caseNumber++;
        }
    }
}

 

 

설명

 

1. 데이터 구조:
   • 두 개의 스택(또는 리스트)을 사용합니다: leftStack과 rightStack
   • leftStack은 커서의 왼쪽에 있는 문자들을, rightStack은 커서의 오른쪽에 있는 문자들을 저장합니다.
2. 알고리즘:
   • 입력 문자열을 순회하며 다음과 같이 처리합니다:
     1. '<': leftStack에서 pop하여 rightStack에 push (커서를 왼쪽으로 이동)
     2. '>': rightStack에서 pop하여 leftStack에 push (커서를 오른쪽으로 이동)
     3. '-': leftStack에서 pop (백스페이스)
     4. 그 외 문자: leftStack에 push
3. 결과 출력:
   • leftStack의 모든 문자와 rightStack을 뒤집은 문자들을 합쳐서 출력합니다.
4. 시간 복잡도:
   • 각 문자를 한 번씩만 처리하므로 O(n)입니다. 여기서 n은 입력 문자열의 길이입니다.
5. 공간 복잡도:
   • 두 개의 스택을 사용하므로 O(n)입니다.