[코딩인터뷰] 자료구조 - 배열과 문자열 해법

코딩인터뷰 자료구조 - 배열과 문자열 해법

1. 문자열이 주어졌을 때, 같은 문자열에 같은 문자가 중복되어 등장하는 지 확인하는 알고리즘

💡 아스키코드 문자열인지 유니코드 문자열인지 확인: 유니코드 문자열인 경우 저장 공간이 늘어날 수 있음

 

해법1) 아스키코드 문자열일 경우, 길이가 256개라고 가정한 후 문자열 순회

boolean[] char_set = new boolean[128];
...
    if(char_set[val])
        return false;
...

- 이미 char_set[val]가 true이면 문자열이 있다고 가정

- 시간복잡도: O(n), 공간복잡도: O(1)

 

해법2) 비트 벡터

- 필요 공간은 1/8로 줄일 수 있음

 

해법3) 문자열 내 각 문자를 다른 모든 문자와 비교

- 시간복잡도: O(n^2), 공간복잡도: O(1)

 

해법4) 입력 문자열 수정이 가능하다면, 문자열 정렬 O(nlogn) 후 인접한 문자가 동일한 지 검사

 

 

2. 두 개의 문자열이 주어졌을 때, 서로 순열관계인가

ex) god와 dog는 서로 순열관계인가?

💡 공백과 대소문자 처리에 대해 반드시 물어볼 것

 

해법1) 정렬

- 순열 관계라면 같은 문자로 구성되고, 순서만 다를 것

- 문자열을 정렬했을 때, 두 문자열이 같은 결과가 나와야 함

 

해법2) 문자 출현 횟수 검사

- 동일한 문자 개수를 가지고 있는 지 확인

 

 

3. 문자열에 들어 있는 모든 공백을 다른 문자로 치환

💡 뒤에서 부터 문자열 편집: 마지막 부분 여유 공간을 사용하기 위해

 

해법1) 문자열 내 공백 개수를 센 후, 두번째 문자열 탐색 시에는 역방향으로 진행하면서 문자열 편집

 

 

4. 문자열이 회문인지 확인

 

해법1) 짝수/홀수

- 짝수: 모든 문자의 개수가 짝수개

- 홀수: 단 한 개의 문자만 홀수개, 나머지는 모두 짝수개

- 시간복잡도: O(N)

 

해법2) 위 방법에 문자열을 훑어나가면서 동시에 홀수의 개수 확인

 

해법3) 스위치와 같이 껐다 키는 방법... ▶️ 어려움

- 시간복잡도: O(N)

 

 

5. 문자열 두 개가 주어졌을 때, 문자열을 같게 만들기 위한 편집(문잡 삽입, 삭제, 교체) 횟수가 1회 이내인지 확인

ex) pale, ple -> true

 

해법1) 한 번의 편집으로 생성할 수 있는 모든 문자열 나열: 비효율적

 

해법2) 의미

- 교체: 문자열이 단 한 개만 달라야 함

- 삽입: 어떤 문자열에서 특정 공간을 빈 공간으로 남겨두면 동일

- 삭제: 삽입의 반대

 

💡 문자열의 길이를 짧은 문자열로 표현하는 이유: 문자열 길이에서 차이가 나면 O(1)의 시간에 알고리즘이 종료됨

 

 

6. 반복되는 문자의 개수를 세는 방식의 기본적인 문자열 압축 메서드

ex) aabcccaaa = a2b1c5a3

 

해법1) 문자열을 순회하면서 새로운 문자열에 문자들을 복사하고 반복되는 횟수 세기

- 시간복잡도: O(p+k^2), p: 문자열 길이, k: 같은 문자가 연속되는 부분 문자열 개수 + 문자열을 합치는 시간 O(n^2)

- StringBuilder를 사용해 문자열 합치는 시간 개선

 

해법2) 압축된 문자열의 길이가 입력 문자열보다 길다면 입력 문자열 반환

 

 

7. N*N 행렬을 90도 회전시키는 메서드. 단, 행렬을 추가로 사용하지 않음

 

해법1) 레이어 별로 회전

 

해법2) 인덱스 별로 수수행

- 제일 바깥쪽 레이어부터 안쪽으로 진행하여 레이어에 대해 작업 수행

- 시간복잡도: O(N^2)

 

 

8. M*N 행렬의 한 원소가 0일 때, 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘

 

해법1) 0의 위치를 기록할 행렬 하나를 더 추가하여, 바뀐 0과 차이점을 둠

- 공간복잡도: O(MN)

💡 cell[2][4]가 0일 때, 같은 행과 열을 0으로 만들것이기 때문에 정확한 위치를 알지 않아도 됨: 공간복잡도O(N)

-> 💡 첫 번째 행을 row, 첫 번째 열을 col 배열로 사용하여 공간 효율을 O(1)로 낮춤

 

 

9. 한 단어가 다른 문자열에 포함되는 지 판단하는 isSubstring 함수를 한 번만 사용하여 s2가 s1을 회전시킨 결과인지 판별

 

해법1) 회전한 지점이 어디인 지 알아야 함

ex) waterbottle 에서 wat 이후에 회전을 적용하면 erbottlewat이 됨

- 회전은 s1을 x와 y로 분리한 후, s2가 되도록 재배치

s1 = xy = waterbottle

x = wat
y = erbottle
s2 = yx = erbottlewat

- xy = s1이 되고, yx = s2가 되는 방법 확인

 

해법2) x와 y로 쪼개지는 지점에 관계없이 yx는 언제나 xyxy의 부분문자열

isSubstring(s1s1, s2)

- true이면 정답

- 시간복잡도: O(N)