알고리즘 !! 진짜 오랜만이다. 알고리즘 쉬는 시험 기간동안 팀플 때문에 js만 하다가 파이썬 문법이 아득해졌다... ~ 그래도 금방 되찾음 ㅎㅋㅋㅎㅎ

17413: 단어 뒤집기 2

이전에 단어만 뒤집는 단어 뒤집기 1이 있었는데, 이번에는 tag 안에 있는 문자는 바꾸지 않고, tag 밖에 있는 문자만 뒤집는 문제였다. 생각 나는 풀이 방법은 되게 많았는데 막상 하려니까 쉽지 않았다...

1. 내 풀이: 성공

import sys

sentence = list(sys.stdin.readline().strip())
tag = False
word = ''
result = ''

for i in sentence:
    if tag == False:
        if i == '<':
            tag = True
            word += i
        elif i == ' ':
            word += i
            result += word
            word = ''
        else:
            word = i+word
    elif tag == True:
        word += i
        if i=='>':
            tag = False
            result += word
            word = ''

print(result + word)

일단 ! 풀이를 먼저 설명하자면,

import sys

sentence = list(sys.stdin.readline().strip())
tag = False
word = ''
result = ''

애초에 input을 받을 때부터 전부 다 잘라버린다. -> list() 이용
그 후에 tag 값을 Boolean으로 주어, tag 안인지 아닌지를 판단하게 한다.
그리고 word와 result 값을 빈 문자열로 초기화 한다.

for i in sentence:
    if tag == False:
        if i == '<':
            tag = True
            word += i
        elif i == ' ':
            word += i
            result += word
            word = ''
        else:
            word = i+word
    elif tag == True:
        word += i
        if i=='>':
            tag = False
            result += word
            word = ''

print(result + word)

자, 그럼 이제 sentence 리스트를 하나씩 돌면서 i를 어디다가 추가할건지를 정한다. 일단 tag가 False인지 True인지부터 판단해준다. False라면 tag 밖일 것이고, True면 tag 안일 것이다.

만약 tag가 False라면, 즉 tag 밖의 문자열이라면 i가 마주할 수 있는 경우의 수는 총 3가지이다.

1. 여는 tag '<'
2. 빈 칸 (스페이스)
3. 그냥 문자

첫 번째 경우라면, 일단 그 뒤에 나오는 값들은 모두 tag 안의 문자열이라는 말이다. 그러니 tag=True를 취해준다. 그리고 해당 i, 즉 '<'는 word 문자열에 추가해준다.
두 번째의 경우라면, 문장이 한 템포 쉬어가는 것(?)을 의미하므로 이 역시 word에 추가해주고, 이 word를 result를 더해준다. 그리고 word는 다시 빈 문자열로 초기화해준다.

음 여기서 이 한 템포 쉰다라는 의미가 애매한데, 예를 들어 설명해보자.
만약 baejoon online judge라는 문장을 boojkeab enilno egduj로 바꿔야 한다고 하면,
이 중간의 스페이스, 즉 한 단어가 끝나는 것을 의미한다.
그러므로 단어가 끝날 때마다 or 스페이스가 나올 때마다 다시 word를 빈 문자열로 바꾸어주어야 하는 것이다.

마지막 경우가 바로 그냥 문자가 등장하는 것이다. 즉, 거꾸로 출력해주어야 하는 문자이므로,
word += i가 아닌
word = i+word로
코드를 작성해야 한다.

다음으로 tag가 True라면, 즉 tag 안의 문자열이라면 i는 word라는 문자열에 그대로 추가될 것이다. 그리고 '>' 태그를 만났을 때 해당 word는 끝이 나게 되고, 이를 result에 추가, word는 다시 빈 문자열로 초기화를 해주면 되는 것이다. 그리고 '>' 태그를 만났다는 것은 이 뒤에 등장하는 문자들은 모두 tag 바깥의 문자임을 의미하므로 tag=False로 바꾸어주면 완성!

이렇게 설명하고 보니 그렇게 어렵지 않은 문제 같다.

2. 다른 풀이

이 문제는 말했다시피 다양한 풀이가 존재한다. 내가 위에처럼 풀기 전에 슬라이싱으로 풀려고 했는데, 도저히 생각이 안나서 못 풀었구,,, 나중에 다른 풀이 찾아보다가 스택을 이용한 풀이를 보았다. 아래의 블로그를 참고하였다.
(출처: https://my-coding-notes.tistory.com/401)

answer = ''
tag = False
stack = ''

for i in input():
	if i == "<":
		tag = True
        answer += stack [::-1]
        stack = ""
        answer += i
        continue
    elif i == ">":
    	tag = False
        answer += i
        continue
    elif i == " ":
    answer += stack[::-1]+" "
    stack = ""
    continue
    
    if tag: answer += i
    else: stack += i
    
print(answer+stack[::-1])

이렇게 보니까 그렇게 나랑 다를 거 없는 거 같기도 ,,,? 다만 신기한 건 input ()을 바로 for range에 박아버린 것... 저렇게도 할 수 있구나 !!! 멋지다.

이렇게 오늘도 신기한 알고리즘의 세계 끝!