✅ 한 것들
- 코딩 인터뷰 완전 분석
📖 코딩 인터뷰 완전 분석
IX 면접 문제
01 배열과 문자열
해시 테이블
간단한 구현
- 배열, 연결리스트, 해시 코드 함수 사용
- 키의 해시 코드를 계산한다.
- 자료형은 보통 int 혹은 long이다.
- 키의 개수는 무한하지만 int는 유한하기 때문에 충돌 가능
- 해시 코드로 배열의 인덱스를 구한다
- 배열의 각 인덱스에는 키와 값으로 이루어진 연결 리스트가 존재한다.
- 키와 값을 해당 인덱스에 저장한다.
균형 이진 탐색 트리로 구현할 수도 있다.
면접 문제
1.1 중복이 없는가
문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘 작성하라.
자료구조 추가로 사용하지 않고 풀 수 있는 알고리즘도 고민하라.
내 접근
- 방법 1: 해시테이블에 문자 등록 이미 돼있으면 중복 판정
- 방법 2: 문자마다 나머지 배열 훑으며 자신과 같은지 확인. 시간 O(N^2), 추가 공간 없음
해법
- 먼저 면접관에게 문자열이 ASCII인지 유니코드인지 물어봐야 한다
- ASCII라고 가정하고 문제 풀면,
- 해법 1: ASCII 문자 집합의 bool 배열을 선언한 뒤, 찾으면 true, 이미 true면 중복 처리
- 자료 구조 추가 사용 불가하다면
- 방법 1: 내 접근 2와 동일
- 방법 2: O(nlogn)으로 문자열 정렬한 뒤 순회하며 인접한 문자 중복 검사
- 많은 정렬 알고리즘이 공간을 추가로 쓴다는 사실에 주의
1.2 순열 확인
문자열 두 개가 주어졌을 때 이 둘이 서로 순열 관계에 있는지 확인하는 메서드 작성하라.
내 접근
- 문자 집합 크기 int 배열 두 개 선언 후 문자마다 각 배열 +1. 두 배열 같은지 점검. O(N).
해법
- 방법 1: 정렬한 뒤 같은지 확인. 최적은 아니지만 이해가 쉽다.
- 방법 2: 내 접근과 동일
1.4 회문 순열
문자 편집 방법이 세 가지 주어진다. 문자 삽입, 문자 삭제, 문자 교체.
문자열을 같게 만들기 위한 편집 횟수가 1회 이내인지 확인하는 함수 작성
내 해법 (정답)
- 문자열 길이가 같으면 문자 교체해서 가능한지 확인
- flag 세워놓고 문자가 다를 때 아직 true라면 교체하고, false면 return false
- 문자열 길이의 절대값 차이가 1이라면 문자 삭제로 가능한지 확인
- 필요한 문자를 삽입하는 건, 다른 문자를 삭제하는 것과 본질적으로 동일
- 문자열을 순회하다 달라지는 문자는 flag를 세워 1번만 무시.
- flag로 1번만 무시하는 식으로 로직 통합
- 아예 길이도 상관 없이 순회 중에 한 쪽 배열 다 탐색해버리면 false 처리
1.5 하나 빼기
aabcccc → a2bc4로 압축하는 메서드를 작성하라
압축된 문자열의 길이가 기존 문자열보다 길면 기존 문자열 반환하라
내 해법
- a는 a1이 되니까 1에서 2, +1
- aa는 a2가 되니까 2에서 2, +0
- aaa는 a3가 되니까 3에서 2, -1
- (2 - 압축할 문자 substr)를 합산하면서 새로운 배열에 문자열을 삽입한다
- 같은 배열에 하면 1을 압축할 때 뒤의 문자열이 오염된다
- 합산했던 값이 음수면 기존 문자를 반환한다
- 이걸 위해서도 기존 배열을 건드리면 안된다
너 정말 **핵심**을 찔렀어