[2021 KAKAO Blind Recruitment] Q1. 신규 아이디 추천 (C++, Python, Java)

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/72410

 

예상 난이도

B1 - S4

 

알고리즘 분류

문자열, 구현

 

풀이

1번 문제 답게 곧이곧대로 구현하면 되는 쉬운 문제입니다. N이 1000으로 작아 2단계를 O(N²)으로 구현해도 아무 문제가 없습니다만 O(N)으로 구현할 수 있습니다. 이 부분을 짚고 넘어가면 좋을 것 같아 다음 슬라이드에서 별도로 설명을 드리겠습니다.

 

이 문제의 경우 정규표현식으로 풀이를 한 분들의 코드를 여럿 볼 수 있었는데, 이 문제에서는 N이 작아서 괜찮지만 길이가 10000 이상으로 길다면 시간복잡도의 가늠이 어렵기 때문에 정규표현식 사용을 비추천합니다.

 

2단계에서는 배열에서 특정 조건을 만족하는 원소를 제거합니다. 이 때 앞에서부터 보면서 원소를 지워나가면 배열에서 원소의 제거는 O(N)이기 때문에 총 O(N²)이 필요합니다.

 

반면 살릴 원소만 따로 모은다는 개념으로 접근하면 특정 조건을 만족하는 원소의 제거를 O(N)에 수행 가능합니다.

 

이외에는 크게 설명이 필요한 부분이 없습니다.

 

코드(C++)

 

매 단계를 정직하게 수행하는 방식으로 구현했습니다. id2를 처리할 때 id2 = id2 + c; 로 코드를 작성한다면 매번 새로운 string을 생성하기 때문에 의도와 다르게 O(N)이 아니라 O(N²)에 동작한다는 점을 주의해주세요.

 

코드(Python)

 

매 단계를 정직하게 수행하는 방식으로 구현했습니다. id2를 처리할 때 id2 = id2 + c; 로 코드를 작성한다면 매번 새로운 string을 생성하기 때문에 의도와 다르게 O(N)이 아니라 O(N²)에 동작한다는 점을 주의해주세요.

 

코드(Java)

 

매 단계를 정직하게 수행하는 방식으로 구현했습니다. 자바의 경우 한 가지 꼭 아셔야하는 점이 있는데, 자바의 String은 immutable이기 때문에 id2 += id1.charAt(i); 이 명령이 O(1)이 아니라 O(id2.length()) 입니다. 그렇기 때문에 지금 코드의 시간 복잡도는 O(N)이 아닌 O(N²)이 됩니다. O(N)에 작성하고 싶다면 StringBuilder를 이용해야 합니다. 자세한 사용법은 StringBuilder를 찾아보세요.

 

String t = "";
int n = 300000;
for(int i = 0; i < n; i++) t += "a"; // O(N^2)

StringBuilder s = new StringBuilder();
for(int i = 0; i < n; i++) s.append("a"); // O(N)