[Python] 백준 문자열(Strings), Linked-Lists 문제 풀이 팁(tip) 정리

Strings - 10808, 10809, 10820, 11655, 10824, 11656
Linked-lists - 1406, 1158

---

~ 목차 ~

 

문자열 STRINGS 문제

1. char <-> 아스키코드

2. rstrip, lsrtip
3. islower(), isupper(), isdigit(), isspace()
4. 주어진 문자열을 바꿀 때, "replace 메소드 사용" vs "빈 문자열에 추가해서 저장" ( 백준 11655 )
5. string a에 int 값을 할당하면?

6. 문자열 내림차순 정렬
7. 시간 복잡도에서, "list 슬라이싱" vs "append, pop"

 

---

링크드 리스트 Linked-Lists 문제

1. 시간 복잡도에서, "String.join(words) " vs "append"

2. " ".join 의 return 값

3. 기본 요세푸스 문제 ( 백준 1158번 )

 

---

문자열 STRINGS 문제

1. char <-> 아스키코드

ord("a"), chr(97)

ord 이름의 뜻은? ordinal of a one character.

 

2. rstrip, lsrtip

각각 string의 right, left공백을 지워준다.

줄바꿈만 지우고 싶으면? input.rstrip("\n") 로 적용한다.

 

3. islower(), isupper(), isdigit(), isspace()

문자열에 유용한 함수들

 

4. 주어진 문자열을 바꿀 때, "replace 메소드 사용" vs "빈 문자열에 추가해서 저장" 

( 백준 11655 )

replace는 주어진 문자열을 모두 찾아 바꿔버리고 새로운 str을 return한다. 따라서 한 문자씩 읽어가며 바꿔야할 경우에는 앞서 바꾼 문자열이 또 바뀔 수 있다.

for문을 사용해서 앞에서부터 읽어나갈때는 replace를 쓰지않고 새로운 문자열을 만들어 +해가며 저장해야한다.

 

5. string a에 int 값을 할당하면?

자동으로 a가 int로 형변환된다.

 

6. 문자열 내림차순 정렬

sorted(s)[::-1] : stride 1인데 음수니까 역으로 진행

s[0:6:2] 이면 s[0],s[2],s[4] 출력, s[6]은 출력안됨

 

7. 시간 복잡도에서, "list 슬라이싱" vs "append, pop" ( 백준 11656 ) 

list 슬라이싱은 O(N)이다. append, pop은 O(1)이다.

list 슬라이싱으로 했을 때, 시간 초과가 나면 list를 스택으로 생각한다.

또 다른 한 개의 빈 스택을 만들어 준다.

그리고 append, pop을 이용하면서 데이터를 두 개로 쪼개준다. ( 백준 11656 에 사용된 아이디어 ) 

쪼갰다 붙였다 하면서 기존 스택의 가장 윗 부분을 커서로 생각한다.

---

LINKED-LISTS 문제

1. 시간 복잡도에서, "String.join(words) " vs "append"

string.join(words)의 시간 복잡도는 append보다 훨씬 높다.

string.join(words) joins words by inserting string between them.

Complexity = len(words) * len(string)

 

2. " ".join 의 return 값

The join() string method returns a string by joining all the elements of an iterable, separated by a string separator.

 

3. 기본 요세푸스 문제( 백준 1158번 )

print(sep=", ") 대신

sys.stdout.write(", ".join( )) 을 이용하면 iterater사이에 원하는 문구를 넣을 수 있다.

import sys

n, k = map(int, sys.stdin.readline().rstrip().split())

people = [i for i in range(1, n + 1)]
answer = []
num = 0

for _ in range(n):
    num += k - 1
    if num >= len(people):
        num = num % len(people)
    answer.append(str(people.pop(num)))

sys.stdout.write("<" + ", ".join(answer) + ">")

- for문 내의 if문에서 = (equal) 을 해주지않으면 indexError발생의 원인이 된다. 유의!

-Q. sorting문제 처럼 index대로 사람을 넘버링하면 안되냐?

-A. 안됨. 사람이 계속 움직이므로 인덱스로 재넘버링됨.

 

* len(people) : O(1)(constant time, not depending of actual length of the element)

 

 

 

소통하고 싶은 내용이 있으면 언제든 댓글주세요.