오늘의 알고리즘(4월 8일)

1. 백준, 5397, 키로거 

 

www.acmicpc.net/problem/5397

5397번: 키로거

 

---

2. 생각해보자

 

a) 문제 정보

• 첫줄은 테스트케이스의 개수다.
• 백스페이스는 - 로 표현한다.
• 화살표는 <>로 커서의 움직임을 표현한다.
• 나머지 문자는 비밀번호다.

 

 

b) 어떻게 풀 수 있을까?

• 테스트 케이스를 하나의 배열에 담는다. 
• 비밀번호를 기록하기 위한 배열을 하나 더 만든다. 
• 비밀번호 배열의 길이가 0일 때, 테스트케이스 배열에서 방향키가 나오면 아무런 영향이 없다. 다음 요소로 이동한다.  
• 비밀번호 배열의 길이가 0 이상일 때, 테스트케이스 배열에서 방향키가 나오면 index 0번 ~ -1번까지 이동할 수 있다.
• 비밀번호 배열의 현재 길이를 저장하는 변수를 만들어 커서의 위치를 구현하다. 
• 만약에 0번과 1번 인덱스 사이에 비밀번호의 문자가 저장되어야 한다면 어떻게 삽입할 수 있을까?
• 아무리 생각해봐도 어떻게 비밀번호를 정렬해야할지 모르겠다. 예를 들어, 0번과 1번 인덱스 사이의 자리에 새로운 비밀번호가 들어가야한다면 어떻게 정렬해야 할까? 

 

---

3. 풀이 및 코드분석 

• 스택을 2개만들고, 스택 2개의 중간지점을 커서의 위치라고 간주한다.
• 문자는 왼쪽 스택에 삽입한다.
• 삭제는 왼쪽 스택에서 삭제한다.
• 커서의 왼쪽 이동(<)은 왼쪽 스택의 원소를 오른쪽 스택으로 이동시킨다.
• 커서의 오른쪽 이동(>)은 오른쪽 스택의 원소를 왼쪽 스택으로 이동시킨다. 
• 최종적으로 이 2개의 스택을 하나로 합치면 된다. 

 

풀이방법 예시

 

 

case_num = int(input())

for _ in range(case_num):
    left = [] # 왼쪽 스택
    right = [] # 오른쪽 스택
    data = input() # 테스트케이스
    for i in data:
        if i == '-':
            if left:
                left.pop()
        elif i == '<':
            if left:
                right.append(left.pop())
        elif i == '>':
            if right:
                left.append(right.pop())
        else: # 문자인 경우
            left.append(i)
    left.extend(reversed(right)) # 오른쪽 스택의 내용을 뒤집어서 왼쪽 스택에 붙여준다. 
    print(''.join(left))

 

---

 4. 주요함수

a) extend

• extend 함수는 두개의 배열이 있을 때, 한 배열의 원소들을 다른 배열의 원소로 삽입하는 기능을 한다.
• extend와 append가 비슷해 보일 수 있는데, append 함수는 어떤 배열 자체를 원소로 삽입한다는 차이점이 있다.

https://m.blog.naver.com/wideeyed/221541104629

 

b) reversed

• 파이썬에는 reverse() 함수와 reversed() 함수, 두가지가 존재한다. 
• reverse() 함수는 리스트 라이브러리에 포함되어 있는 함수이며, reversed() 함수는 파이썬의 내장함수라는 차이점이 있다.
• reverse() 함수는 리스트의 요소 순서를 완전히 바꾸어 버린다.
• 반면에, reversed() 함수는 리스트의 요소 순서를 바꿔서 출력하는데, 실제로 리스트 내부의 요소 순서를 변경시키지는 않는다. 출력만 거꾸로 하는 것이다. 

https://pydole.tistory.com/entry/Python-sort-reverse%EC%99%80-sorted-reversed-%EC%B0%A8%EC%9D%B4

 

 

c) join

• join() 함수는 문자열을 합쳐서 반환하는 기능을 한다. 
• 위의 코드를 보면 ''.join() 을 사용한 것을 알 수 있는데, 여기서 ''는 무슨 역할을 할까? 
• join() 함수는 구분자를 이용하여 함께 쓸 수 있다. '구분자'.join() 이런 형태로 말이다.

https://blockdmask.tistory.com/468

 

 

 

d) 왜 reversed를 사용했을까? 

• 코드를 직접 돌려서 확인해보자. 그러면 쉽게 알 수 있다.