혼자 공부하는 공간

안녕하세요 GODZ입니다. 오늘은 문자열을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 [설명] N개의 문자열의 집합에서 특정 문자열이 어떤 문자열의 접두사가 되지 않을 때, 그 집합을 접두사 X 집합이라고 한다. 또한 접두사 X 집합을 만족하는 가장 큰 집합을 만드는 게 관건이다. 문자열의 수(N)가 최대 50, 문자열의 길이(M)가 최대 50이다. ---> 각 문자열을 이중 반복문으로 순회해도 O(N^2)이고, 문자열을 비교할 때 역시 O(M)이므로 결국 O(MN^2) = 125,000회 이내이다. [로직] 기준 문자열(origin)과 N-1개의 비교 문자열(comp)을 비교한다. origin의 길이가 comp의 길이보다 같거나 짧을 때만 비교한다. ---> origin의..

안녕하세요 GODZ입니다. 오늘은 문자열을 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 원본 문자열의 길이 N(1이상 1백만 이하), 비교 문자열의 길이 M(1이상 36이하) 일 때, 원본 문자열을 한 번 순회하면서 비교 문자열을 지우는 작업은 O(NM)의 시간 복잡도를 가진다. O(NM)의 복잡도가 수없이 반복되기 때문에 제한시간을 맞출 수 없다. 따라서 문자열을 순회하면서 비교 문자열과 비교하는 작업을 병행한다. 원본 문자열을 저장할 자료구조는 StringBuilder나 Stack 그 외 List와 같은 mutable 구조를 사용하면 된다. 어떤 자료구조를 사용하든 간에 남은 원본 문자열을 출력해야 하므로 StringBuilder가 다른 자료구조에 비해 빠르다. 4. 코드..

안녕하세요 GODZ입니다. 오늘은 문자열 처리를 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 로직 일단 입력 받은 문자열이 Java 특징에 해당하는지, C++ 특징에 해당하는지 검사합니다. - 특징 - Java - 첫 문자 소문자 // 단어를 구분하기 위해 앞 문자 대문자 사용 C++ - 소문자만 사용 가능 // 단어를 구분하기 위해 언더바(_) 사용 flag라는 변수를 두어 Error인 경우, Java인 경우, C++인 경우, 둘 다 해당되는 경우에 대해 값을 지정합니다. 그 후 각 값마다 해당하는 기능을 하게끔 로직을 만들면 되겠습니다. 처음 flag는 둘 다 포함으로 할당 입력받은 문자열의 첫 문자가 소문자인가? 소문자인 경우 arr[index] == '_' 인 경우 flag..

안녕하세요 GODZ입니다. 오늘은 문자열 처리를 이용한 문제를 풀어볼 예정입니다. 1. 문제 2. 입출력 예제 3. 접근 흔한 괄호 문제인데 생각보다 정답률이 많이 낮아서 가지고 온 문제입니다. 문자열 사이에 들어간 (, [ 와 ), ]가 제대로 짝이 맞게 들어갔는지 확인하는 문제입니다. 핵심은 닫히는 괄호에서 처리하는 로직입니다. 여는 괄호에서는 그냥 Stack에 push작업만 하면 되지만, 닫히는 괄호에서는 몇 가지 처리를 잘해주셔야 통과할 수 있습니다. 닫히는 괄호일 때, 아래와 같은 사항들을 체크해야 합니다. 더보기 1. Stack이 비어있는가? 2. 비어있지 않다면 짝이 맞는 괄호인가? 1에서 비어있는지 체크하지 않으면 런타임 에러가 뜰 수 있습니다. 2에서 짝이 맞지 않는 괄호라면 no를 출력..