면접 예상 문제 코테 문제 - 문자열의 중복이 없는가
중복이 없는가
문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라
자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘 또한 고민하라.
해답 :
먼저 면접관에게 문자열이 ASCII 문자열이지 유니코드 문자열인지 물어 봐야 한다.
이를 통해 컴퓨터 과학을 깊이 있게 이해하고 있다는 사실을 알릴 수 있으며,
세부사항을 신경 쓰고 있다는 인상을 남기자.
여기서는 간단하게 ASCII 문자열이라고 가정해보자.
이 가정이 없다면 저장 공간의 크기를 늘려야 할 수도 있다.
이 문제를 푸는 한 가지 방법은 문자 집합에서 i번째 문자가 배열 내에 존재하는지
표시하는 불린(boolean) 배열을 사용하는 것이다.
같은 원소에 두 번 접근하면, 바로 false를 반환한다.
또한 문자열의 길이가 문자 집합의 크기보다 클 경우 바로 false를 반환해도 된다.
결국 256가지 문자를 한 번 씩만 사용해서 길이가 28-인 문자열을 만들 수 없으니까 말이다.
확장된 ASCII의 경우에는 길이가 280인 문자열을 만들 수도 있겠지만,
총 문자의 개수가 256개라고 가정해도 괜찮다.
면접관에게 미리 말해 두기만 하면 된다.
아래는 이 알고리즘을 구현한 코드이다.
// var.java
boolean isUniqueChar(String str)
{
if (str.length() > 128) return false;
boolean[] char_set = new boolean[128];
for (int i = 0; i < str.length(); i++)
{
int val = str.charAt(i);
if (char_set[val]) {
// 이 문자는 이미 문자열에 있음
return false;
}
char_set[val] = true;
}
return true;
}
// var. C#
bool IsUniqueChar(string str)
{
if (str.Length > 128) return false;
bool[] charSet = new bool[128];
for (int i = 0; i < str.Length; i++)
{
int val = str[i];
if (charSet[val])
{
// 이 문자는 이미 문자열에 있음
return false;
}
charSet[val] = true;
}
return true;
}
이 코드의 시간 복잡도는 O(n)이다. (n은 문자열의 길이).
공간 복잡도는 O(1)이다.
(하지만 256개보다 많은 문자를 순회하지 않기 때문에 시간 복잡도가 O(1)이라고 추청할 수 있다.)
문자 집합의 크기를 미리 정해 놓고 싶지 않다면,
공간 복잡도는 O(c), 시간 복잡도는 O(min(c, n)) 혹은 O(c)라고 표현해도 된다.
여기서는 c는 문자 집합의 크기를 나타낸다.
자료구조를 사용할 수 없을 때
1. 문자열 내의 각 문자를 다른 모든 문자와 비교한다.
이렇게하면 O(n^2) 이 걸리고 공간 복잡도는 O(1)이 된다.
2. 입력 문자열을 수정해도 된다면, O(n log n) 시간에 문자열을 정렬한 뒤 문자열을 처음부터 훑어 나가면서
인접한 문자가 동일한지 검사해 볼 수도 있다. 이때 많은 정렬 알고리즘이 공간을 추가로 쓴다는 사실에 주의하자.
1. 방법은 O(n²) 브루트포스 방식
2. 방법은O(n log n) 정렬 후 인접 비교 방식
C, C++, C#, JS 순 코드
// C언어 O(n^2) 브루트포스 방식
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
bool isUniqueChar_bruteforce(const char* str)
{
int len = strlen(str);
for (int i = 0; i < len - 1; i++)
{
for (int j = i + 1; j < len; j++)
{
if (str[i] == str[j]) return false;
}
}
}
// C언어 (n log n) 정렬 후 인접 비교 방식
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>
int cmp_char(const void* a, const void* b)
{
return (*(char)a - *(char)b);
}
bool isUniqueChar_sorted(char* str) {
int len = strlen(str);
char* temp = strdup(str); //원본 문자열 보호
qsort(temp, len, sizeof(char), cmp_char);
for (int i = 1; i < len; i++)
{
if (temp[i] == temp[i - 1]) {
free(temp);
return false;
}
}
free(temp);
return true;
}
// C++ O(n^2) 브루트포스 방식
#include <iostream>
#include <string>
bool isUniqueChar_bruteforce(const std::string& str)
{
for (size_t i = 0; i < str.length() - 1; i++)
{
for (size_t j = i + 1; j < str.length(); j++)
{
if (str[i] == str[j]) return false;
}
}
return true;
}
// C++ O(n log n) 정렬 후 인접 비교 방식
#include <iostream>
#include <string>
#include <algorithm>
bool isUniqueChar_sorted(std::string str) {
std::sort(str.begin(), str.end());
for (size_t i = 1; i < str.length(); i++)
{
if (str[i] == str[i - 1]) return false;
}
return true;
}
// C# O(n^2) 브루트포스 방식
public static bool IsUniqueCharBruteforce(string str)
{
for (int i = 0; i < str.Length - 1; i++)
{
for (int j = i + 1; j < str.Length; j++)
{
if (str[i] == str[j]) return false;
}
}
return true;
}
// C# O(n log n) 정렬 후 인접 비교 방식
using System;
public static bool IsUniqueCharSorted(string str)
{
char[] arr = str.ToCharArray();
Array.Sort(arr);
for (int i = 1; i < arr.Length; i++)
{
if (arr[i] == arr[i - 1]) return false;
}
return true;
}
// js O(n^2) 브루트포스 방식
function isUniqueCharBruteforce(str) {
for (let i = 0; i < str.length - 1; i++)
{
for (let j = i + 1; j < str.length; j++)
{
if (str[i] == = str[j]) return false;
}
}
return true;
}
// js O(n log n) 정렬 후 인접 비교 방식
function isUniqueCharSorted(str) {
let arr = str.split('').sort();
for (let i = 1; i < arr.length; i++) {
if (arr[i] == = arr[i - 1]) return false;
}
return true;
}