코딩 인터뷰 완전 분석 | 9. 면접 문제 - 배열과 문자열

배열과 문자열

해시테이블 (hash table)

키(key) : 값(value) 형태의 자료구조

 

구현 방법

1) 해시코드와 연결리스트 활용

수행시간

- 최악: O(N), N = 키의 개수

- 최선: O(1)

2) 균형 이진 탐색 트리

탐색 시간

- O(log N), 적은 공간 사용

 

ArrayList 와 가변 크기 배열

동적 가변 크기 배열의 자료구조

접근 시간, 상환 입력 시간: O(1)

cf. 크기를 2 배 늘리면 시간은 O(n)이 되나 발생 빈도가 낮아 영향 없음

삽입 시간

- 평균: O(1)

- 최악: O(N)

 

StringBuilder

가변 크기 배열를 활용해 각 문자들을 이어붙여 새로운 문자열을 만들 수 있음

수행 시간 O(n^2)

 

---

 

면접 문제

1.1 중복이 없는가

자료구조 set 활용

def has_duplicates(s):
    char_set = set()
    for char in s:
        if char in char_set:
            return True
        char_set.add(char)
    return False

# ex
input_string = "abcdefg"
result = has_duplicates(input_string)
print(result)  # False

input_string = "hello"
result = has_duplicates(input_string)
print(result)  # True

 

1.2 순열 확인

자료구조 dictionary (hash table) 활용

def are_permutations(str1, str2):
    if len(str1) != len(str2):
        return False
    
    char_count = {}
    
    for char in str1:
        char_count[char] = char_count.get(char, 0) + 1
    
    for char in str2:
        if char not in char_count or char_count[char] == 0:
            return False
        char_count[char] -= 1
    
    return all(count == 0 for count in char_count.values())

# ex
str1 = "abc"
str2 = "bca"
result = are_permutations(str1, str2)
print(result)  # True

 

 

1.3 URL 화

def replace_spaces(s, length):
    return s.replace(' ','%20')
    
# ex
print(replace_spaces('Mr John', 7)) # 'Mr%20John'