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

문제 링크

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

 

예상 난이도

B1 - S4

 

알고리즘 분류

문자열, 구현

 

풀이

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

 

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

 

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

 

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

 

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

 

 

코드(C++)

#include <bits/stdc++.h>
using namespace std;

string solution(string new_id) {    
    string id1;
    for(auto c: new_id) id1 += tolower(c);
    
    string step2_filter = "0123456789abcdefghijklmnopqrstuvwxyz-_.";
    string id2;
    for(auto c : id1){
        if(find(step2_filter.begin(), step2_filter.end(), c) != step2_filter.end())
            id2 += c;
    }
    
    string id3;
    for(auto c : id2){
        if(c != '.') id3 += c;
        else{
            if(!id3.empty() && id3.back() == '.') continue;
            id3 += c;
        }
    }
    
    string id4;
    for(int i = 0; i < id3.size(); i++){
        if((i == 0 || i+1 == id3.size()) && id3[i] == '.') continue;
        id4 += id3[i];
    }
    
    string id5 = id4;
    if(id5.empty()) id5 = "a";
    
    string id6 = id5.substr(0, 15);
    if(id6.back() == '.') id6.pop_back();
    
    string id7 = id6;
    while(id7.size() < 3) id7 += id7.back();
    
    return id7;
}

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

 

코드(Python)

import string
def solution(new_id):
    id1 = new_id.lower()
    
    step2_filter = string.digits + string.ascii_lowercase + '-_.'
    id2 = ''
    for c in id1:
        if c in step2_filter: id2 += c
    
    id3 = ''
    for c in id2:
        if c != '.': id3 += c
        else:
            if id3 and id3[-1] == '.': continue
            id3 += c

    id4 = id3.strip('.')
    
    id5 = id4[:]
    if not id5: id5='a'
    
    id6 = id5[:15]
    if id6[-1]=='.': id6 = id6[:-1]
    
    id7 = id6[:]
    while len(id7) < 3: id7 = id7 + id7[-1]
    return id7

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

 

코드(Java)

import java.util.*;

class Solution {
    public String solution(String new_id) {
        String id1 = new_id.toLowerCase();
        
        String step2_filter = "0123456789abcdefghijklmnopqrstuvwxyz-_.";
        String id2 = "";
        for(int i = 0; i < id1.length(); i++){
            if(step2_filter.indexOf(id1.charAt(i)) != -1)
                id2 += id1.charAt(i);
        }
        
        String id3 = "";
        for(int i = 0; i < id2.length(); i++){
            if(id2.charAt(i) != '.')
                id3 += id2.charAt(i);
            else{
                if(id3.length() > 0 && id3.charAt(id3.length() - 1) == '.') continue;
                id3 += id2.charAt(i);
            }
        }
        
        String id4 = "";
        for(int i = 0; i < id3.length(); i++){
            if((i == 0 || i+1 == id3.length()) && id3.charAt(i) == '.') continue;
            id4 += id3.charAt(i);
        }
        
        String id5 = id4;
        if(id5.length() == 0) id5 = "a";
        
        String id6 = id5;
        if(id6.length() > 15)
            id6 = id6.substring(0, 15);
        if(id6.charAt(id6.length() - 1) == '.') id6 = id6.substring(0, id6.length() - 1);
        
        String id7 = id6;
        while(id7.length() < 3) id7 += id7.charAt(id7.length() - 1);
        return id7;
    }
}

매 단계를 정직하게 수행하는 방식으로 구현했습니다. 자바의 경우 한 가지 꼭 아셔야하는 점이 있는데, 자바의 String은 immutable이기 때문에 id2 += id1.charAt(i); 이 명령이 O(1)이 아니라 O(id2.length()) 입니다. 그렇기 때문에 지금 코드의 시간 복잡도는 O(N)이 아닌 O(N2)이 됩니다. 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)
  Comments
댓글 쓰기