코딩하는 eroke

문제

피보나치 수 F(n) = F(n-1) + F(n-2)

input: 2<=n<=100,000 

return : n번째 피보나치 수 % 1234567

그냥 재귀함수로만 구현하면 틀리는 문제로 메모이제이션이 중요한 문제이다.

(실패이유 : 재귀함수 호출 수 초과)

메모이제이션 (memoization) :

한 번 계산한 결과는 저장, 이후 저장한 값으로 호출하여 재귀가 계속해서 호출되는 것을 방지

풀이

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int d[100001]; //전역=0초기화
int fibo(int n){
    if(n<=2) return 1;
    
    if(d[n]!=0) return d[n]%1234567; //메모이제이션
    else{
        d[n]=fibo(n-1)+fibo(n-2);
        return d[n]%1234567;
    }    
}

int solution(int n) {
    return fibo(n);
}

문제

input :

0과 1로 이루어진 어떤 문자열 x

1. x의 모든 0을 제거
2. x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 변환

return :
x가 "1"이 될 때까지 계속해서 x에 변환을 가했을 때의

[이진 변환의 횟수, 변환 과정에서 제거된 모든 0의 개수]

   ex)

x = "0111010"이라면,

x = "0111010" -> 0제거 -> "1111" -> 4("1111"의 길이) 이진변환 -> "100" 

[3,5] return

풀이

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

vector<int> solution(string s) {
    vector<int> answer={0,0};
    int zero=0,ztotal=0,cnt=0,len=0;
    string cp=s;
    
    if(cp=="1") return answer;
    
    while(cp!="1"){
        cnt++; //이진변환 횟수
        zero=0;
        for(int i=0;i<cp.length();i++){
            if(cp[i]=='0')zero++;
        }
        ztotal+=zero; //제거한 0개수
        len = cp.length()-zero;

        string bin="";
        while(len){
            bin+=to_string(len%2);
            len/=2;
        }
        reverse(bin.begin(),bin.end());
        cp=bin;
    }
    answer[0]=cnt;
    answer[1]=ztotal;
    return answer;
}

요새 파이썬으로만 문제를 풀다가 오랜만에 C++ 로 문제를 풀려고하니 문법을 죄다 까먹었다;;

특히 STL, 문자열........... 당분간 C++ 문법 복기용 문제들을 풀어볼 예정이다..

문제

위의 입출력 예시 그대로인 간단한 문제이다. 뒤의 숫자 네개를 제외하고 마스킹(*)하면 된다.

(phone_number는 길이 4 이상, 20이하인 문자열)

풀이

#include <string>
#include <iostream>

using namespace std;

string solution(string phone_number) {
    string star = "****************";
    
    string subs = phone_number.substr(phone_number.size()-4, phone_number.size());
    int ln = phone_number.size()-4;
    string answer = star.substr(0,ln);
    answer+=subs;
    
    return answer;
}

전화번호의 뒤 숫자 4개를 substr로 끊고

4개를 제외한 길이만큼 * 문자열을 만들어 둘을 합쳐서 return 했다.

문제

그림과 같이 N*M 맵에서좌측 맨 상단에서 우측 맨 하단까지 갈 수 있는 최단거리를 출력하는 문제이다.

맵에서 0인 구간은 못가고 1인 구간만 갈 수 있으며 목적지까지 도달할 수 없으면 -1을 출력한다.

주의할 점은 N,M은 같을 수도 다를 수도 있다.

큐를 사용해 BFS로 풀었고 이동한 거리는 현재 지점+1로 계산했다.

BFS 개념 복습하기 좋은 문제인 것 같다.

입출력 예

풀이

from collections import deque

dx=[1,0,-1,0]
dy=[0,1,0,-1]

def solution(maps):

    n = len(maps)
    m = len(maps[0])
    
    dq=deque()
    dq.append((0,0))
    
    while dq:
        cx, cy = dq.popleft()
        
        if cx==n-1 and cy==m-1: 
            #for m in maps: print(m)
            return maps[cx][cy]
        
        for i in range(4):
            nx = cx+dx[i]
            ny = cy+dy[i]
            if 0<=nx<n and 0<=ny<m and maps[nx][ny]==1:
                dq.append((nx,ny))
                maps[nx][ny] = maps[cx][cy]+1

    return -1

문제

문제 설명

제한 조건

• s는 길이 1 이상 200 이하인 문자열입니다.
• s는 알파벳과 숫자, 공백문자(" ")로 이루어져 있습니다.
  • 숫자는 단어의 첫 문자로만 나옵니다.
  • 숫자로만 이루어진 단어는 없습니다.
  • 공백문자가 연속해서 나올 수 있습니다.

입출력 예

유의해야 할 점은 공백문자가 여러 개일 수 있어 단순 split()을 하면 안된다.

풀이 (python)

def solution(s):
    answer = ''
    lspace = list()
    is_space = False
    
    space = ''
    for x in s:
        if x==' ':
            is_space = True
            space+=' '
        elif x!=' ' and is_space==True:
            is_space = False
            lspace.append(space)
            space=''
    if space!='': lspace.append(space)
            
    sp = 0            
    tmp = s.split()
    for t in tmp:
        y = t.lower().capitalize() #문자열 전체 소문자 치환 후 첫글자만 대문자화
        answer+=y
        if sp<len(lspace):
            answer+=lspace[sp]
        sp+=1
        
    return answer

첫번째 반복문에서 공백이 등장할때마다 공백 문자열을 리스트에 추가 했다.

두번째 반복문에서 공백이 아닌 문자열들을 소문자화, 첫 문자만 대문자화한 뒤 

결과 문자열에 재처리한 문자열들과 공백 문자열들을 더해 리턴해주었다.

공백 문자열이 마지막까지 있는 경우도 고려해주어야 모든 케이스가 통과된다.

문제

1칸, 2칸을 갈 수 있을때 n칸 까지 도달하기 위한 경우의 수를 리턴하는 문제이다.

 n=1일때, (1칸) = return 1

n=2일때, (1칸, 1칸), (2칸) = return 2

n=3, n=4 는 그림을참고하면 된다.

결국 피보나치 문제였다.

주의할 점은 n이 1 또는 2일때 어떠한 메모리 할당도 하지 않고 바로 리턴해야 테스트1번이 통과된다.

풀이

def solution(n):
    if n<3: return n
    
    dp=[0]*(n+1)
    dp[1]=1
    dp[2]=2
    
    for i in range(3,n+1):
        dp[i]=dp[i-1]+dp[i-2]
    
    return dp[n]%1234567

문제

시키는 대로 하면 되는 문제이고 파이썬 문자열 연습하는데 좋은 문제인 것 같다.

풀이 (python)

def solution(new_id):
	#1단계
    new_id1 = new_id.lower()
    
    #2단계
    new_id2=''
    for x in new_id1:
        if x.isalpha() or x.isdigit() or x=='-' or x=='_' or x=='.':
            new_id2+=x
    
    #3단계
    while '..' in new_id2:
        new_id2 = new_id2.replace('..','.')
    
    #4단계
    new_id3=list(new_id2)
    if new_id3 and new_id3[0]=='.': del new_id3[0]
    if new_id3 and new_id3[-1]=='.':del new_id3[-1]
    
    new_id4 = ''.join(new_id3)
    
    #5단계
    if new_id4=='': return 'aaa'
    #6단계
    if len(new_id4)>=16: new_id4 = new_id4[:15]
    if new_id4[-1]=='.': new_id4 = new_id4[:14]
    #7단계
    if len(new_id4)<3:
        while len(new_id4)!=3:
            new_id4+=new_id4[-1]
            
    return new_id4

문자열 함수들과 리스트변환, 슬라이스를 사용해 풀이했다.

문제

풀이 (Python)

from collections import deque

def getThird(dq, n):
    a=n//3
    p=n%3
    if n==0: return dq
    else: 
        dq.appendleft(p)
        return getThird(dq,a)

def solution(n):
    answer = 0
    
    dq=deque()
    t = getThird(dq,n)
    
    for i in range(len(dq)):
        answer+=((3**i)*dq[i])

    return answer

위 소스로 풀긴 했지만 찾아보니 아래처럼 풀이할 수도 있다고 한다.

deque를 안쓰고 리스트로 푼담에 바로 return(answer, 3) 하면 좀더 간단할 것 같다.

int(answer, n) # n진법으로 구성된 str형의 answer를 10진수로 반환

레벨2 언제풀지..............

문제

로또 번호로 가능한 최고 등수와 최저 등수를 리턴하는 문제이다.

로또 숫자는 1~45인데, 0인 경우는 알아볼 수 없는 숫자이다.

그래서 0의 개수에 따라 가능한 최고 등수가 바뀐다.

14번 케이스만 계속 틀려서 시간이 좀 걸렸는데 0의 개수도 없고 6개 다 틀린경우를

생각하지 못했다ㅠ 어떤 문제든 제약사항을 잘 고려해야 하는 것 같다.

풀이 (Python)

def solution(lottos, win_nums):
    #0 없앰
    notzero = set(lottos) 
    if 0 in notzero: notzero.remove(0) #0이 한개일 경우 
    
    if len(notzero)==0: return [1,6]

    zero_cnt = len(lottos) - len(notzero) #0 개수
    lotto_len = len(set(win_nums)-set(notzero)) #1등과 차이 개수 
    
    if lotto_len==0: return [1,1]
    elif zero_cnt==0 and lotto_len==6: return [6,6]
    else:
        if zero_cnt==0: return [lotto_len+1,lotto_len+1]
        else: return [lotto_len-zero_cnt+1,lotto_len+1]

문제

nums 배열에 n개의 폰켓몬 수가 주어지고 최대 n/2마리 폰켓몬을 선택해야하는데 

중복없이 선택해야하는 문제이다.

풀이

def solution(nums):
    
    po=len(nums)//2
    snums = set(nums)

    if len(snums)<po:
        return len(snums)
    else:
        return po

파이썬의 set으로 nums에서 중복제거 후 n/2와 비교하여 선택할 수 있는 수를 return했다.