티스토리 뷰
1. 문제
https://www.acmicpc.net/problem/5397
5397번: 키로거
문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다. 강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 테
www.acmicpc.net
2. 문제 개요
주어진 입력을 분석하여 실제 비밀번호 문자열을 계산하기.
3. 문제 힌트
보통 시간초과가 많이 나는데 Vector의 삽입 삭제의 시간복잡도는 O(n)이다.
다른 자료구조를 사용하여 O(1)의 시간에 삽입, 삭제를 할 수 있도록 하자.
4. 문제 풀기
List : <Head> // 1개를 선언한다.
이러면 우리가 알고있는 커서는 Head의 오른쪽에 위치하게된다. // 현재 커서의 위치 list.begin()
ex) List : <Head> -> <P> -> <A> -> <S> -> <S> 라고 가정하면,
cursor
가 된다.
여기서 커서를 움직이는 것은 List Iterator (Cursor)를 한칸씩 움직여준것과 동일하다고 볼 수 있다.
ex) List : <Head> -> <P> -> <A> -> <S> -> <S>이고, Iterator(=Cursor)가 A를 가르킨다면,
iterator
이러한 상황과 동일하다고 생각하면 된다.
이 아이디어를 가지고 코드로 옮기면,
5. 코드
#include <cstdio>
#include <cstring>
#include <list>
using namespace std;
int main()
{
int tc;
scanf("%d", &tc);
while (tc--)
{
char str_input[1000000] = { 0 };
scanf("%s", str_input);
int str_len = strlen(str_input);
list<char> ret(1); //header
list<char>::iterator head = ret.begin();
list<char>::iterator cursor = head;
for (int i = 0; i < str_len; ++i)
{
char ch_input = str_input[i];
if (ch_input == '<')
{
if (cursor != head)
{
cursor--;
}
}
else if (ch_input == '>')
{
if (cursor != --ret.end())
{
cursor++;
}
}
else if (ch_input == '-')
{
if (cursor != head)
{
cursor = ret.erase(cursor);
cursor--;
}
}
else
{
cursor = ret.insert(++cursor, ch_input);
}
}
for (list<char>::iterator iter = ++ret.begin(); iter != ret.end(); iter++)
printf("%c", *iter);
printf("\n");
}
return 0;
}
6. 결과 사진
시간과 메모리를 좀 더 줄여보려고 했으나 list로는 줄일만큼 줄인것 같다.
stack을 사용하면 더 줄일 수 있을것 같다.
지적, 댓글 언제나 환영입니다~
'알고리즘 > Implementation' 카테고리의 다른 글
| boj, 백준) 1655. 가운데를 말해요 ( C / C++) (0) | 2020.06.22 |
|---|---|
| boj) 1021 회전하는 큐 (C++) (0) | 2020.02.17 |
| boj, 백준 ) 1049 기타줄 (C++) (1) | 2020.01.28 |
| boj, 백준 ) 2615 오목 (0) | 2020.01.28 |
| boj, 백준 ) 17143 낚시왕 ( C / C++ ) (0) | 2020.01.08 |