[ 파이썬 알고리즘 인터뷰 ] 문자열 뒤집기 & 로그 파일 재정렬

문제1. 문자열 뒤집기

Q. 문자열을 뒤집는 함수를 작성하라. 입력값은 문자 배열이며, 리턴 없이 리스트 내부를 직접 조작하라!

 

EX1_입력 ] ["H","E","L","L","O"]
EX1_출력 ] ["O","L","L","E","H"]

EX2_입력 ] ["H","a","n","n","a","h"]
EX2_출력 ] ["h","a","n","n","a","H"]

 

해당 문제를 푸는 방법?!

1. 두 개의 포인터를 이용한 스왑
2. 파이썬 함수 사용
3. 슬라이싱 사용

 

방법1. 두개의 포인터를 이용한 스왑

class Test:
    def reverseString(self, s):
        left, right =0 , len(s)-1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left+=1
            right-=1
    
test = Test()
string =["H","a","n","n","a","h"]
test.reverseString(string)
print(string)

 

- 위 코드의 방식은 아래 그림과 같다. left, right가 문자리스트의 양 끝부터 시작해 하나씩 범위를 좁혀가며 스왑하는 방식이다. 

 

💢주의할 점💢

- 만약 입력이 리스트가 아니라 string 즉 "hello"이런 식으로 되어있다면 TypeError: 'str' object does not support item assignment 이런 에러를 만났을 수 있다. 문제에서 조건이 ' 리턴 없이 내부를 조작하라' 이 부분 때문에..! 위 함수 코드에서 문자열 자체를 조작 불가하다. 문자열의 경우 수정이 불가능한 자료구조로 immutable type이라고 한다. 그래서 문자열을 조작하고플 때는 리스트로 변환하거나 replace 메소드를 사용해야한다. 여기서는 문자열이 입력되었다고 하면 슬라이싱을 사용해서 해결할 수 있다.

 

 

방법2. 파이썬 함수 사용

class Test:
    def reverseString(self, str):
        str.reverse()

test=Test()
string =["H","a","n","n","a","h"]
print(string)

 

- reverse()함수를 사용하면 문자열을 뒤집을 수 있다. reverse 함수는 리스트에만 제공된다. 

 

 

방법3. 슬라이싱 사용

string ="hello"
# string =["H","a","n","n","a","h"]
print(string[::-1])

 

- 문자열이 입력되었을 경우 슬라이싱을 사용하여 해결할 수 있다. 가끔 공간복잡도의 제약으로 s = s[::-1]이 오류가 발생할 때도 있다.(거의 그러지는 않지만..) 이럴 때는 s[:] =s[::-1]로 적어주면 해결된다!

 

 

문제2. 로그파일 재정렬

Q. 로그를 재정렬하라. 기준은 다음과 같다.
   
   1. 로그의 가장 앞 부분은 식별자이다.
   2. 문자로 구성된 로그가 숫자 로그보다 앞에 온다.
   3. 식별자는 순서에 영향을 끼치지 않지만, 문자가 동일할 경우 식별자 순으로 한다. 
   4. 숫자 로그는 입력 순서대로 한다.

 

EX1_입력 ] ["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"]

EX1_출력 ] ["let1 art can", "let3 art zero", "let2 own kit dig", "dig1 8 1 5 1", "dig2 3 6"]

 

방법 1. 람다 & 연산자 사용

class Test:
    def orderLogFiles(self, logs:str):
        letters , digits =list(),list()
        
        for log in logs :
            if log.split()[1].isdigit():
                digits.append(log)
            else :
                letters.append(log)
        
        letters.sort(key=lambda x : (x.split()[1:], x.split()[0]))
        
        return letters+digits

test=Test()
logs= ["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"]
print(test.orderLogFiles(logs))

 

- 가장 먼저 해당 로그가 숫자로그인지 문자로그인지를 확인한다. 숫자인 경우 digits에 문자인 경우 letters에 append된다.

- 문자 로그의 경우, 로그가 동일 시 식별자 순으로 sort 되어야하므로, 식별자를 제외한 로그 부분으로 먼저 sort 하고 동일할 시 식별자 순으로 정렬되도록 람다식을 작성한다. 

- 이후 letters+digits를 출력한다.

 

❕ 람다 (lambda) 란
- 람다 표현식이란 식별자 없이 실행 가능한 함수를 말한다. 함수 선언이 없어도 하나의 식으로 함수를 단순하게 표현할 수 있다. lamda 매개변수 : 표현식 형태이다. x, y 두 수를 받아 더하는 함수를 람다식으로 표현하면 (lamda x,y : x+y)(10,20) 으로 작성할 수 있다. 위 문제에서는 람다식에서 반환한 두 개의 리스트를 sort의 키로 사용하고 있다. 

 

  

 

---

[ 참고자료 ]

- 도서 : 파이썬 알고리즘 인터뷰 

파이썬 알고리즘 인터뷰 - 교보문고