웬만한 기업의 코딩 테스트로 나오기엔 난이도가 낮은 너무 문제이지만 문제를 풀다가 내가 까먹고 있던 부분을 발견하여 다시 한번 기억하고자 포스팅을 한다.
문제는 간단하다. 입력값으로 문자열(word), 문자(ch)가 주어지고, 주어진 문자열에서 ch가 나타나는 위치까지만 문자를 뒤집어 리턴하면 된다. 만약, 문자열 안에 ch가 없다면, 그냥 원본 문자열을 리턴하면 된다.
아래는 내가 제출해 통과한 코드이다.
class Solution:
def reversePrefix(self, word: str, ch: str) -> str:
if ch in word:
reversed_str = word[: word.index(ch) + 1][::-1]
res = reversed_str + word[word.index(ch) + 1:]
return res
else:
return word
여기서 더 효율적으로 코드를 작성 할 수 있는 방법은
- 먼저, find 메서드는 파이썬에서 문자열(string) 객체에 대해 사용되는 메서드로, 특정 문자가 문자열 내에서 처음으로 나타나는 위치(인덱스)를 반환한다. 이 메서드는 찾는 문자가 문자열 내에 없으면 -1을 반환한다.
class Solution:
def reversePrefix(self, word: str, ch: str) -> str:
index = word.find(ch)
if index != -1:
return word[:index+1][::-1] + word[index+1:]
return word
위와 같이 find를 통해 발생하는 인덱스를 미리 저장해놓는다. 나는 .index()메서드만 알고 있었기 때문에(.index()는 존재하지 않으면 예외를 발생시킴) 인덱스를 미리 저장 할 생각을 하지 못했다.
- 인덱스가 존재하지 않는다면 -1을 반환하는데, -1이 아니라면(찾고자 하는 단어가 문자열 안에 존재한다면), 문자열 슬라이싱을 이용해 문자를 합쳐준다.
파이썬에서 문자열은 불변(immutable) 객체이다. 이는 한 번 생성된 문자열 객체는 변경될 수 없다는 것을 의미한다. 따라서 `word[:index+1][::-1] + word[index+1:]`와 같은 표현은 실제로 기존 문자열을 변경하는 것이 아니라, 새로운 문자열을 생성하는 것이다.
return word[:index+1][::-1] + word[index+1:]
1. `word[:index+1]`: 문자열 `word`의 처음부터 `index+1` 위치까지의 부분 문자열을 추출한다. 2. `[:: -1]`: 추출한 부분 문자열을 뒤집는다. 3. `word[index+1:]`: `index+1` 위치부터 끝까지의 부분 문자열을 추출한다. 4. `+`: 뒤집어진 부분 문자열과 원래 문자열의 남은 부분을 결합하여 새로운 문자열을 생성한다.
이 과정에서 `word` 자체는 전혀 변경되지 않고, 대신 `word`로부터 새로운 문자열이 생성된다. 따라서 원래의 문자열 `word`는 여전히 불변이며, 새로운 문자열을 반환하는 것이다.
word = "abcdef"
index = 2 # 'c'의 위치# word[:index+1]는 "abc"를 반환하고, 이를 뒤집으면 "cba"가 된다.# word[index+1:]는 "def"를 반환한다.# 이를 결합하면 "cbadef"가 된다.
new_word = word[:index+1][::-1] + word[index+1:]
print(new_word) # 출력: "cbadef"print(word) # 출력: "abcdef", 원래의 문자열은 변경되지 않음
따라서 이 코드는 원래 문자열 `word`를 변경하지 않고 새로운 문자열을 생성하여 반환한다.
문제는 쉽고 간단하지만 내 소스 코드에 등장한 문자열 슬라이싱을 복습 하고자 포스팅을 써 본다. 문제는 입력값으로 sentence라는 문장이 주어지고, 또 다른 입력값으로 searchWord가 주어진다. 이때, 공백을 기준으로 문자열을 나누어 나누어진 문자의 접두사가 searchWord를 포함하면 그 단어가 있는 인덱스를 리턴하라.(단, 여기서는 인덱스가 1부터 시작한다고 가정한다)
아래는 내가 제출해 통과한 코드이다.
class Solution:
def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
sentence_arr = sentence.split()
for i in range(len(sentence_arr)):
if sentence_arr[i][:len(searchWord)] == searchWord:
return i + 1
return -1
- 우선, sentence_arr 변수에 입력값으로 주어진 문자열을 공백을 기준으로 나누어 리스트에 담아준다. 예를 들어, 첫번째 예시에서는
sentence_arr = ['i', 'love', 'eating', 'burger']이 담길 것이다.
- 이제, for문을 돌며 sentence_arr의 요소들을 하나씩 검색한다.
여기서 sentence_arr[i][:len(searchWord)]는 현재 검사중인(sentence_arr[i]) 요소의 맨 처음 요소부터 searchWord의 길이까지 슬라이싱을 하여 주어진 입력값과 비교한다. 만약, 일치한다면 현재 인덱스 + 1을 리턴하고, 아니면 -1을 리턴한다. 예를 들어, 'burger'를 검사할때 슬라이싱을 이용하면 burg == burg같은 형태로 비교되어 참으로 간주되어 인덱스를 리턴 할것이다.
- 여기서 헷갈렸던 점은 슬라이싱을 할때, 마지막 슬라이싱 범위는 포함되지 않는다. 예를 들어, s = "Hello, World!"이고, print(s[:3])을 한다면 문자열 s의 처음부터 2번째 인덱스까지(0, 1, 2)를 포함시켜 'Hel'이라는 문자열이 출력된다.
🔉 아래는 GPT에게 최적화를 부탁한 내용이다.
주어진 코드를 최적화하고 간결하게 만들 수 있습니다. 먼저, `split()` 메서드를 사용하여 문장을 단어로 분리하고, 각 단어가 `searchWord`로 시작하는지 확인하는 과정은 적절하지만, 인덱스를 직접 사용하는 대신 `enumerate`를 사용하면 코드가 더 간결해질 수 있습니다.
최적화된 코드는 다음과 같습니다:
class Solution:
def isPrefixOfWord(self, sentence: str, searchWord: str) -> int:
for i, word in enumerate(sentence.split(), start=1):
if word.startswith(searchWord):
return i
return -1
변경된 부분: 1. `enumerate(sentence.split(), start=1)`을 사용하여 인덱스를 직접 관리하지 않고, 인덱스와 단어를 동시에 얻습니다. 여기서 `start=1`로 설정하여 인덱스가 1부터 시작하게 합니다. 2. `startswith` 메서드를 사용하여 단어가 `searchWord`로 시작하는지 확인합니다. 이는 부분 문자열 비교보다 더 명확하고 효율적입니다.
그렇다. 파이썬에서는 startsWith라는 메서드를 쓸 수 있고, 이 메서드는 어떠한 문장이 파라미터로 주어진 문자열로 시작하는지 확인 하는 메서드이다.
또한, enumerate도 내가 계속 이용하던건데, 이것도 까먹지 말자. 이걸 사용하면 리스트를 순회할때 리스트의 요소, 인덱스를 동시에 가져와 비교 할 수 있다. 또한, 이번 문제와 같이 (인덱스는 1부터 시작한다고 가정) 시작 인덱스가 0이 아니라 특정 인덱스부터 시작한다면, enumerate의 두번째 파라미터로 start = 1로 지정해주면 된다.
이 문제도 마찬가지, 로직은 직관적이고 간단하지만 배열 선언에 있어서 까먹었던 부분이 있어 풀이를 작성한다. 먼저 이 문제는 입력값으로 리스트가 주어지고, 이 리스트에서 인덱스와 요소를 비교하여, 요소가 짝수이면 짝수 인덱스에, 요소가 홀수 인덱스면 홀수 인덱스에 넣어 결과 배열을 리턴하면 된다. 아래는 내가 제출한 코드이다.
class Solution:
def sortArrayByParityII(self, nums: List[int]) -> List[int]:
even = 0
odd = 1
res = [0] * len(nums)
for i in nums:
if i % 2 == 0:
res[even] = i
even += 2
else:
res[odd] = i
odd += 2
return res
여기서의 로직은 간단하다. 입력값으로 주어진 배열을 하나씩 순회하며 홀수인지 짝수인지 확인한 후, 짝수라면 처음 선언한 결과 배열의 짝수 인덱스에 현재 검사 중인 요소를 넣어주고, `even += 2`를 통해 포인터를 업데이트 시켜준다. `even` 포인터는 0부터 시작했기 때문에 `+= 2`를 하면 0, 2, 4, 6...과 같이 될 것이다. 홀수도 마찬가지이다. 하지만 내가 여기서 까먹었던 부분은 다음과 같다.
나는 처음에 결과 배열을 `res = []`라고 빈 배열로 선언했다. 코드를 제출하기 전에 디버깅을 돌렸을 때 자꾸 `res[even] = i` 부분에서 에러가 났다. 이유는, 배열이 초기화되지 않았기 때문이다. 빈 배열 `res`는 초기화되지 않았기 때문에 특정 인덱스에 접근할 수 없다. 따라서 `res` 배열을 미리 초기화하거나, 배열의 크기를 동적으로 조절하는 로직이 필요하다. 그렇지 않으면 인덱스 에러가 발생하게 된다.
`res = []`로 배열을 초기화하면 빈 배열이 생성되지만, 특정 인덱스에 접근하거나 값을 할당할 수 없다. 예를 들어, `res[even] = i`와 같이 특정 인덱스에 값을 할당하려고 하면 인덱스 오류가 발생한다.
이유 `res = []`는 빈 배열을 초기화하지만, 배열의 길이는 0이다. 따라서 `res[even]`과 같이 배열의 특정 인덱스에 접근하려고 하면 `IndexError`가 발생한다. 빈 배열은 초기화되었지만, 크기를 명시하지 않았기 때문에 특정 인덱스에 직접 값을 할당할 수 없다.
해결 방법 1. 미리 배열의 크기를 초기화하기: 배열의 크기를 미리 알 수 있다면, 배열을 고정된 크기로 초기화할 수 있다.
res = [0] * n # n은 배열의 크기
2. append()를 사용하여 동적으로 배열에 값을 추가하기: 배열의 크기를 미리 알 수 없다면, `append()` 메서드를 사용하여 동적으로 배열에 값을 추가할 수 있다.
res = [] res.append(i) # 배열의 끝에 값을 추가
잘못된 접근 방식:
res = [] even = 2 i = 5
# 이 코드는 IndexError: list assignment index out of range를 발생시킨다. res[even] = i
올바른 접근 방식: 1. 미리 배열의 크기를 초기화하는 방법:
n = 10 # 예시로 배열의 크기를 10으로 설정 res = [0] * n even = 2 i = 5
res[even] = i # 이제 인덱스 2에 값을 할당할 수 있습니다. print(res)
2. append()를 사용하여 동적으로 값을 추가하는 방법:
res = [] res.append(5) # 배열의 끝에 값을 추가 print(res) # 출력: [5]
결론 : 파이썬에서 배열의 인덱스를 참조하고싶다면, 선언된 배열은 초기화가 되어 있어야 한다. 빈 배열을 선언하면 빈 배열의 100번째 인덱스에 값을 넣을 수 없다. 단, .append()메서드로 배열의 맨 뒤에 넣는것은 가능!
문제의 개념 자체는 쉬워 보이지만, 연결 리스트를 다루는법이 아직도 익숙하지 않아 포스팅을 하려고 한다... 어쨌든!
문제는 이렇다.
입력값으로 head, 연결 리스트가 주어지고, 그 연결 리스트의 중간값을 반환하면 된다. 하지만 중간값이 2개라면, 2번째 중간 값을 반환하면 된다.
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
fast = slow = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
'slow'와 'fast' 두개의 포인터를 초기화 한다. 둘 다 처음에는 리스트의 head를 가리킨다.
while loop는 fast 포인터가 끝에 도달 할때까지 반복된다.
fast가 리스트의 끝에 도달하면, slow는 중간에 위치하게 된다.
이 방법은 연결 리스트를 딱 한번만 순회하기 때문에 효율이 좋은 알고리즘이다. O(N)의 시간 복잡도를 가진다.
입력값으로 하나의 문자열이 주어지고, 이 문자열을 모두 뒤집어서 리턴하면 성공! 사실 이 문제는 너무 쉬워서 포스팅을 스킵하려 했으나, 내가 까먹었다가 다시 기억난 부분이 있어 포스팅을 해 보겠다.
아래는 내가 제출해 통과한 코드이다.
class Solution:
def reverseWords(self, s: str) -> str:
words = s.split()
res = []
for i in words:
res.append(i[::-1])
return' '.join(res)
- s.split() : 여기서도 고민한 부분이 있었는데, split의 인자로 ''를 넣어야 하나, ' '를 넣어야 하나 고민을 하고 검색을 해본 결과, split의 인자가 비어있으면 파이썬은 자동으로 문자열을 공백을 기준으로 나눠준다. words라는 변수 안에 입력값으로 받은 문자열 s를 공백을 기준으로 나누어 준다.
- 결괏값을 담을 res 배열을 선언 해준다. 다시 한번 강조하지만, 파이썬의 문자열은 불변의 객체이므로 문자열 원본 자체를 바꿀 순 없고, 새로운 배열에 담아 .join을 이용해 합쳐 문자열로 반환 해야한다.
- 이제 words에는 공백을 기준으로 나누어진 문자열들이 담겼을 것이다. for문으로 순회하며 각각의 단어들을 뒤집어 res 배열에 담아준다. 여기서도 등장했다. 문자열을 뒤집는 가장 편한 방법인 파이썬의 문자열, 리스트 슬라이싱을 이용해[::-1] 문자열을 뒤집어 주었다.
- return ' '.join(res) 여기서 내가 까먹었다가 다시 기억한 부분이다. 난 처음에 ''.join을 했지만, 이렇게 하니
"s'teL ekat edoCteeL tsetnoc"
이렇게 찍히는것이 아니라
"s'teLekatedoCteeLtsetnoc"
이렇게 찍히는 것이였다. 그래서 어떡하지를 고민 하던 중, .join 메서드에 대해 다시 생각을 해 보았다. join메서드는 앞에 구분자를 지정해 주어야 한다. 앞에 나오는 구분자에 따라 리스트를 문자열로 합친다.
예를들어,
1. ''.join(s) : 이건 s라는 리스트의 모든 요소들을 중간 공백 없이 합친다 예) [a,b,c] => "abc"
2. ' '.join(s): 이건 s라는 리스트의 모든 요소들을 공백 하나로 구분지어 합친다. 예) [a,b,c] => "a b c"
3. ', '.join(s): 이건 s라는 리스트의 모든 요소들을 쉼표 하나로 구분지어 합친다. 예) [a,b,c] => "a, b, c"
4. '! '.join(s): 이건 s라는 리스트의 모든 요소들을 느낌표 하나로 구분지어 합친다. 예) [a,b,c] => "a! b! c"
이 문제를 보고 파이썬의 문자열, 리스트 슬라이싱이 생각났다. 슬라이딩 윈도우? 아니면 해시 테이블? 등등 여러가지 자료 구조를 생각해봤다.
이 문제는 대략 입력값으로 문자열 s와 정수 k가 주어지면, 주어진 문자열 s를 순회하며, k*2만큼의 파티션을 만들어 그 파티션 안에서 처음 등장하는 k개의 문자 갯수 만큼 문자열을 뒤집는다. 하지만 조건이 있는데, 만약 하나의 파티션의 길이가 k보다 짧다면, 그 파티션의 모든 문자열을 뒤집는다. 반대로 2k보단 작지만 k보다 크거나 같다면, 파티션의 첫 k개의 문자열만 뒤집어서 마지막에 뒤집어진 문자열을 리턴한다. 아래는 내가 제출해 통과한 코드이다.
class Solution:
def reverseStr(self, s: str, k: int) -> str:
step = k*2
result = []
for i in range(0, len(s), step):
part = s[i:i + step]
if len(part) < k:
result.append(part[::-1])
else:
result.append(part[:k][::-1] + part[k:])
return''.join(result)
먼저, step과 result 변수를 각각 초기화를 해 준다. 파이썬에서는 자바의 stringBuilder같은 라이브러리는 제공되지 않으므로, 여기선 result 배열에 .append를 이용해 결괏값을 담은다음 마지막에 string으로 변환해 줄 생각이다.
for i in range(0, len(s), step): - 내가 한가지 걱정한 부분이 있다. 예를들어, s라는 문자열의 길이가 7이면, 두번째 파티션 생성 당시에 IndexError같은 예외가 발생 하지 않나? 라는 생각을 했다. 검색을 해본 결과, 파이썬의 슬라이싱 기능은 범위를 벗어난 인덱스에 대해 안전하게 동작한다. 예를 들어, s[4:8]과 같이 범위를 벗어난 슬라이싱을 시도하면, 파이썬은 자동으로 s[4:]로 처리하고 남아 있는 부분만 반환한다.그러므로, 이 for문에선 인덱스 0부터 시작하여 s의길이만큼을 반복하며, step만큼씩 건너뛰며 반복문을 수행한다.
part = s[i : i + step] - 이제 파티션을 만들어 준다. 파이썬의 문자열/ 리스트 슬라이싱을 활용해 파티션을 만들어 준다. 여기서는 s라는 변수가 담고있는 문자열에서 인덱스 i 부터 (i + step - 1) 까지의 인덱스를 포함시켜 파티션으로 만들어 준다. 예시에서 s = abcdefg가 있다면, 처음 파티션은 인덱스 [0 : 0 + 4]이므로, 실제 문자열 s에서 인덱스 0부터 3까지를 포함시켜 파티션으로 만든다. 즉, 첫번째 반복문의 파티션은 abcd와 같이 생겼을 것이다.
len(part) < k: - 위에서 첫번째 조건이다. 만약, 파티션의 길이가 k보다 작다면, 우리는 파티션의 모든 문자열을 뒤집어야 한다.
result.append(part[::-1]): - 맨 위에서 선언한 result라는 빈 리스트에 part를 뒤집어서 append해 준다. [::-1]을 보자마자 저번 포스팅에서 언급한 내용이 번뜩 하고 기억이 났다. 이것도 문자열 슬라이싱 구문을 사용한 것인데, start와 end를 비워주고(여기서 start와 end가 생략되면 기본 디폴트값으로 start는 0으로 설정되고, 현재 비교중인 문자열이나 리스트의 길이를 end로 설정한다.) 마지막에 -1을 넣음으로써 문자열을 역순으로 순회하는 것이다!
else: - 여기서의 else는 위에서 언급한 두번째 조건과 같다(반대로 2k보단 작지만 k보다 크거나 같다면, 파티션의 첫 k개의 문자열만 뒤집어서 마지막에 뒤집어진 문자열을 리턴한다.) 이 조건에서는, 파티션 전체를 뒤집는게 아니라, 파티션에서 처음 등장한 k개의 문자열만 뒤집어야 한다.
result.append(part[:k][::-1] + part[k:])
- 1. part[:k] part 문자열의 처음부터 k 번째 문자까지 슬라이싱한다. 예를 들어, part = "abcdef"이고 k = 2인 경우, part[:k]는 "ab"이다.
2. part[:k][::-1] 위에서 슬라이싱한 문자열을 다시 슬라이싱하여 역순으로 만든다. 예를 들어, part[:k]가 "ab"라면, part[:k][::-1]는 "ba"이다.
3. part[k:] part 문자열의 k 번째 문자부터 끝까지 슬라이싱한다. 예를 들어, part = "abcdef"이고 k = 2인 경우, part[k:]는 "cdef"이다.
4. part[:k][::-1] + part[k:] 역순으로 만든 첫 번째 k 문자와 나머지 문자를 결합한다. 예를 들어, part[:k][::-1]가 "ba"이고 part[k:]가 "cdef"라면, 결합한 결과는 "bacdef"이다.
여기서 살짝 헷갈리는 부분은 2번의 part[:k][::-1]인데, 이 부분은 두 부분을 합친 것이다. 여기서의 두 부분은 다음과 같이 표현 할 수 있다.
parted = part[:k]
reversed = parted[::-1]
위의 코드는 part[:k][::-1]과 같다.
return ''.join(result) - 모든 파티션이 끝난 result 배열을 .join 메서드를 활용해 리스트에서 문자열로 변환시킨후 리턴한다.
