[코딩테스트] 백준 단어뒤집기2 (17413) S3

문제 링크 : 단어뒤집기2 (17413) s3

아이디어

공백을 기준으로 단어이고, 단어를 기준으로 뒤집는다. 이때 태그는 제외하고 뒤집는다.

1. 뒤집는 함수를 정의한다(넣으면 뒤집어서만 나옴)
2. 어떤 문자열을 1의 함수에 넣을지 판단하는 로직
   1. 태그를 먼저 제외(태그 안에도 공백 가능하니까),
   2. 공백을 기준으로 단어를 끊어 뒤집기

시간 복잡도 계산

문자열 S의 길이는 100,000이하 시간 제한은 1초이다. 1초에 2천만번 연산을 하니까 log(n)탐색, O(nlogN)(log10만 == 16정도, 1,600,000) 정도만 허용이 되겠다.

구현

 line = input()

def flip(tags) :
    flipStack = []
    flippedWord = ''
    answer = ''
    ## 단어 뒤집는 로직
    for w in tags :
      if w[0] == '<' :
        answer += w
      else :
        for i in range(len(w)) :
          flipStack.append(w[i])

        for k in range(len(w)) :
          flippedWord += flipStack.pop()

        answer += flippedWord
        flippedWord = ""
            
    return answer

## <> 뽑아내기
tagq = ""
tags = []
words = ""
isTagOpended = False

for i in line :
    if isTagOpended == False :
        if i == '<' :
            if len(words) >0 :
              tags.append(words)
              words= ""
            isTagOpended = True
            tagq += i
        else : 
            words+= i

    else :
      if i == '>' :
            tagq += i
            tags.append(tagq)
            tagq = ""
            isTagOpended = False
      else :

            tagq+= i

tags.append(words)

print(flip(tags))

하지만 .. 단어간 공백을 생각 안하고 짰다. 따라서 아래와 같이 고쳐보았다.

line = input()

def flip(tags) :
    flipStack = []
    flippedWord = ''
    answer = ''
    
    ## 단어 뒤집는 로직
    for w in tags :
      if w[0] == '<' :
        answer += w
      else :
        for i in range(len(w)) :
          flipStack.append(w[i])
          
        for k in range(len(w)) :
          flippedWord += flipStack.pop()
        answer += flippedWord 
        flippedWord = ""
        
    return answer

## <> 뽑아내기
tagq = ""
tags = []
words = ""
isTagOpended = False

for i in line :
    if isTagOpended == False :
        if i == '<' :
            if len(words) >0 :
              tags.append(words)
              words= ""
            isTagOpended = True
            tagq += i
        else : 
            if i == " " :
              tags.append(" "+ words)
              words = ''
            else :
              words+= i

    else :
      if i == '>' :
            tagq += i
            tags.append(tagq)
            tagq = ""
            isTagOpended = False
      else :
            tagq+= i

if len(words) != 0 :
    tags.append(words)

print(flip(tags))

결과는 .. !

성공! 캬캬 ><