개발자 아지트

https://school.programmers.co.kr/learn/courses/30/lessons/92335#

문제설명

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

0P0처럼 소수 양쪽에 0이 있는 경우

P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우

0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우

P처럼 소수 양쪽에 아무것도 없는 경우

단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.

예를 들어, 101은 P가 될 수 없습니다.

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

문제 해결 방법

주어진 값을 n진수의 값으로 변환하기 위해서 divmod함수를 사용하여 나머지 값을 모아 하나의 문자열 형태로 만든뒤, 뒤집어줬다. 

해당 문자열에서 소수로 판단할 수를 하나의 리스트에 담아 모아주었다. 

해당 리스트의 값을 대상으로 소수를 판별하고 값을 리턴했다. 

코드 구현

from collections import deque
def solution(n, k):
    answer = 0
    strr = ''
    
    # n진수 -> n진수로 변환법
    while n > 0:
        n, mod = divmod(n, k)
        strr += str(mod)

    # 문자열에서 소수 조건에 맞는 수 세아리기 
    
    strr = strr[::-1]
    strr = list(strr)
    
    checkList = []
    
    tmp = ''
    cnt = 0
    for idx, i in enumerate(strr):
        if i !='0':
            tmp+=str(i)
            cnt+=1
            if idx == len(strr)-1:
                checkList.append(tmp)
        else:
            while cnt > 0:
                checkList.append(tmp)
                cnt=0
            
            tmp=''
            cnt = 0
            
    for i in checkList:
        if i == '1':
            continue
     
        cnt = 0
        
        for k in range(2, int((int(i) ** 0.5)+1)):
            if int(i) % k == 0:
                cnt +=1
        
        if cnt == 0:
            answer+=1
    
    return answer

시간/공간 복잡도

최악의 경우 O(N)

최적화 및 개선 / 어려웠던 점

주어진 값을 n진수로 변환할 때 코드를 통한 변환 방법을 까먹어서 다시 찾아봤고, 

문자열을 쉽게 뒤집는 방법을 알게됐다. 

주어진 값에 대해 소수판별을 하기 위해서 에라토스테네스의 채 방법을 사용했는데, 두개의 테스트케이스에서 자꾸 시간초과가 났다. 해당 방법을 사용할 수 없었다. 

소수판별을 해야하는 값들 중에서 가장 긴 값의 범위 만큼만 에라토스테네스의 채 방법을 사용해서 코드를 작성해봤지만, 그 역시도 시간 초과가 났다. 해당 방법을 사용할 수 없었다. 

아예 에라토스테네스의 채 방법을 사용하지 않고, 바로바로 소수 판별을 하는게 나으려나 싶어서 아래와 같은 방식을 사용했었다. 

from collections import deque
def solution(n, k):
    answer = 0
    strr = ''
    
    # n진수 -> n진수로 변환법
    while n > 0:
        n, mod = divmod(n, k)
        strr += str(mod)

    # 문자열에서 소수 조건에 맞는 수 세아리기 
    
    strr = strr[::-1]
    
    strr = list(strr)
    
    checkList = []
    
    tmp = ''
    cnt = 0
    for idx, i in enumerate(strr):
        if i !='0':
            tmp+=str(i)
            cnt+=1
            if idx == len(strr)-1:
                checkList.append(tmp)
                
        else:
            while cnt > 0:
                checkList.append(tmp)
                cnt=0
            
            tmp=''
            cnt = 0
    #print('checkList', checkList)
    for i in checkList:
        #print(i, answer)
        if i == '1':
            continue
        
        if i == '2' or i == '3' or i == '5' or i == '7':
            
            answer+=1
        else:
            if int(i) % 2 == 0: 
                continue
            if int(i) % 3 == 0: 
                continue
            if int(i) % 5 == 0: 
                continue
            if int(i) % 7 == 0: 
                continue
            if int(i) % (int(i) ** 0.5) == 0:
                continue
            
            #print('check', i)
            answer+=1
            
        #print(i, answer)
    
    return answer

처음에는 2, 3, 5, 7의 배수만 거르면 나머지는 다 소수라고 생각했었는데, 2, 3, 5, 7이상의 소수의 배수의 소수가 아닌 값을 고려하지 못했다. (ex. 121) 그래서 그런 값들을 고려하기 위해서 제곱근을 활용했다. 

제곱근을 코드로 구현하는 방법을 몰라서 해당 부분도 찾아봤다. 

그런데 저 코드로는 2, 3, 5, 7 이상의 값중 소수인 값을 체크할 수가 없었다. 

소수는 1과 자기자신으로만 나눠지는 값이고, 만약 소수가 아니라면 1과 자기자신의 값 사이에 있는 값으로 나눠져야한다. 

예를들어서 특정 값이 있을때, 그 값이 소수라면, 약수는 1과 자기자신뿐이다. 만약 소수가 아니라면, 약수는 1과 자기자신 그리고 자기자신의 제곱근과 그 제곱근을 기준으로 작은 약수와 큰 약수가 생긴다. 

이 점을 활용해서, 특정 값이 소수임을 판별할때, 1부터 자기자신의 제곱근 사이에 있는 모든 숫자를 가지고 자기자신이 0으로 나눠떨어지는지 확인하면 굳이 큰 약수를 확인하지 않아도 작은 약수임을 확인하는 것 만으로도 특정 값이 소수인지 확인할 수 있게된다. 

https://school.programmers.co.kr/learn/courses/30/lessons/17680#

문제설명

캐시

지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.

이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.

어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

문제 해결 방법

deque를 사용하여 문제를 해결했다. 

LRU 란?
LRU(Least Recently Used)는 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식이다. 
많이 나온 횟수와는 상관 없이 최근(cache size 이내)에 나오지 않았다면 삭제한다.
사용된지 가장 오래된 페이지는 앞으로도 사용될 확률이 낮다는 가설에 의해 만들어진 알고리즘이다.

Cache Hit : CPU 가 참조하고자 하는 메모리가 캐시에 존재하고 있을 경우를 말한다. 
Cache Miss : CPU 가 참조하고자 하는 메모리가 캐시에 존재하지 않을 경우를 말한다. 

코드 구현

from collections import deque
def solution(cacheSize, cities):
    answer = 0
    
    cache = deque(maxlen=cacheSize)

    for i in cities:
        i=i.lower()
        if i in cache:
            cache = list(cache)

            indexx = cache.index(i)
            
            del cache[indexx]
            cache = deque(cache, maxlen=cacheSize)
            
            cache.append(i)
            answer +=1
        else:
            answer +=5
            cache.append(i)
             
    return answer

시간/공간 복잡도

최악의 경우 O(N)

최적화 및 개선 / 어려웠던 점

따로 하지않았음.

https://school.programmers.co.kr/learn/courses/30/lessons/87390

문제설명

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

n행 n열 크기의 비어있는 2차원 배열을 만듭니다.

i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.

1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.

1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.

새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.

정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

문제 해결 방법

2차원 배열 특정 위치에 해당되는 첨자 같은 공식이라고 있었다. 

행첨자는 ([현 위치]) / (전체 열의 수 )

열 첨자는 ([현 위치]) % (전체 열의 수)  

이거랑 코드 구현의 아이디어랑 관련이 있다. 

왜냐하면 문제의 제한사항을 감안하고 구현하려면 left부터 right 까지의 값을 가진 배열을 바로 구해야(left이전의 값이나 right이후의 값을 계산하면 시간초과 이슈 발생)한다. 

해당 배열을 바로 구하기 위해서는 문제에서 제공한 행과 열에 대한 값의 관계를 생각해서 행첨자와 열첨자를 이용해 문제를 풀어야만 한다. 

행과 열 첨자를 구하면 두 값중 큰 값이 해당 위치의 원소의 값이 된다. 

코드 구현

def solution(n, left, right):
    answer = []
    for i in range(left,right+1):
        
        a = (i // n) +1# 몫 행첨자 
        b = (i % n) +1#나머지  열 첨자 
        print('a', a, 'b', b)
        if a < b :
            print('check')
            a, b = b, a
        answer.append(a)

    return answer

시간/공간 복잡도

최악의 경우 O(N)

최적화 및 개선 / 어려웠던 점

진짜 굉장히 어렵다고 생각하는 문제다.

처음에 2중 반복문으로 풀었는데 테스트케이스 대부분 시간초과 났따. 그래서 반복문을 하나로 줄였는데도 비슷했다. 

굉장히 어렵다고 생각한다. 내가 뭘 모르는건가?

그래서 진짜 끙끙 앓다가 힌트랑 남의 코드 봤다. 보고도 이해가 안갔다. 진짜 내가 뭘 모르는게 분명하다. 

찾아보니 2차원 배열 특정 위치에 해당되는 첨자 같은 공식을 참고해서 풀었다. 

확실히 나는 해당 개념을 몰랐다. 그래서 문제 풀때도 아이디어를 거의 없는걸 창조해서 풀듯이 했고, 남의 코드를 봐도 

이해를 잘 못했던 것 같다. 

글로 쓰고나니 별거아닌거 같은 이 느낌은 뭐지 ;;; 휴,, 거진 서너시간은 날린 것 같다. 

그래도 좋은 경험이였다. 

https://school.programmers.co.kr/learn/courses/30/lessons/131701#qna

문제설명

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.

원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

문제 해결 방법

deque의 maxlen 속성을 이용하여 문제를 해결했다. 

deque의 maxlen 속성은 deque를 생성할때 maxlen에 값을 주면 해당 값만큼의 크기의 deq를 만들 수 있는 속성이다. 

만약 사용자가 해당 deque에 maxlen이상의 값을 추가하면 deq에 있는 맨 왼쪽의 값부터 삭제한다. 

(appendleft()를 할 경우, 맨 오른쪽의 원소가 삭제되고 맨 왼쪽에 값이 추가됨)

문제에서는 연속된 값의 길이가 1부터 elements의 크기 까지일 수 있다. 

따라서 해당 경우를 헤아려 가며 deq를 만들어주고 deq 요소의 값을 합해준 후, 해당 값을 하나의 리스트에 넣었다. 

중복값에 대한 처리는 set으로 해줬다. 

코드 구현

from collections import deque

def solution(elements):
    answer = 0
    a = []
    for i in range(1,len(elements)+1) :
        deq = deque(maxlen=i)
        
        for i in elements * 2 :
            deq.append(i)
            a.append(sum(deq))
            
    
            
        
    
    return len(set(a))

시간/공간 복잡도

최악의 경우 O(N^2)

최적화 및 개선 / 어려웠던 점

사실 이 문제를 3중 for문으로 풀었는데 아니나 다를까, 테스트 케이스 5번부터 끝까지 시간초과가 났다. 

근데 아무리 생각해봐도 3중으로 for문을 사용하지 않으면 문제를 풀 수 있는 방법을 떠올릴 수 없었다. 

힌트를 얻어 문제를 풀었다. deque에 maxlen이라는 속성이 있는지 처음 알았다. 최고다!

https://school.programmers.co.kr/learn/courses/30/lessons/12914#

문제설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는

(1칸, 1칸, 1칸, 1칸)

(1칸, 2칸, 1칸)

(1칸, 1칸, 2칸)

(2칸, 1칸, 1칸)

(2칸, 2칸)

의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

문제 해결 방법

n이 1일때, 2일때, 3일때, 4일때의 결과를 문제에서 찾고, 5일때 결과를 만들어서 보니 피보나치 수열의 형태를 띄었다. 

피보나치 수열을 구현하여 해당문제를 해결했다. 

코드 구현

import itertools

def solution(n):
    answer = 0
    tmp=[0, 1, 1]
    cnt = 3
    summ = 0
    while 1:
        if n == 1:
            answer = 1
            return answer % 1234567
        elif n == 2:
            answer = 2
            return answer % 1234567
        else:
            summ = (tmp[cnt-1] + tmp[cnt-2]) 
            tmp.append(summ)
            cnt+=1
        
        if cnt == n+2:
            return summ % 1234567
    
    return answer

시간/공간 복잡도

최악의 경우 O(N)

최적화 및 개선 / 어려웠던 점

입출력의 경우를 쭉 나열해서 문제를 풀어볼 생각을 못하고, 직접 문제 그대로 구현해보려 했다. 

문제 그대로 구현하니 테스트케이스 2번부터 끝까지 시간초과가 났다. 

아무리 생각해봐도 이중 반복문을 사용하지 않고 문제를 해결할 방법이 생각나지 않아서, 힌트를 봤다. 

문제가 안풀리면 입출력문을 문제에서 제시한 부분을 나열해보고 그다음 부분은 직접 경우의 수를 구해 붙인뒤에 

점화식을 세워 문제를 풀 생각을 해봐야겠다. 

문제에 거의 점화식이 주어지는 경우도 있으니, 이런 부분 감안해서 문제를 읽어볼 것.

https://school.programmers.co.kr/learn/courses/30/lessons/12980#qna

문제설명

OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.

예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다.

아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.

처음 위치 0 에서 5 칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5 만큼 듭니다.

처음 위치 0 에서 2 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3 만큼 듭니다.

처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.

위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.

문제 해결 방법

N을 2로 나눌때 나눠 떨어지면 넘어가고 2로 나눠떨어지지 않을때 ans를 1씩 추가한다. 

만약 n이 1까지 도달하면 ans를 1 추가하고 ans를 리턴한다. 

문제에서 한번 점프할때 1칸, 2칸 혹은 N칸 간격 까지 할 수 있지만, 문제에서 제시한 설명처럼 1칸 점프하는게 효율적임을 알 수 있다. 따라서 점프는 1칸만 하는 경우만 고려한다. 

코드 구현

def solution(n):
    ans = 0
    
    
    while 1:
        if n == 1:
            ans+=1
            break
        
        if n % 2 == 0 :
            n = n // 2
        else:
            n = n - 1
            ans += 1
        
    
    return ans

시간/공간 복잡도

최악의 경우 O(N)

최적화 및 개선 및 어려웠던 점

사실 이 문제 도저히 못풀겠어서 힌트를 참고했다. 

이런 식의 문제는 0에서 N으로 가는 코드를 작성할때보다.
N부터 시작해서 0 으로 갈때에 해결되는 경우가 많이 나오는 것을 힌트로 알게되었다. 

현재까지 온 거리가 2의 배수가 되므로 2로 나눠야 되는 것을 알게되었다.  만약 나눠떨어 지지 않으면 점프를 해야한다. 

(점프를 하면 1칸만 이동할 수 있으므로)

아직 이 문제가 직관적으로 와닿지 않는다.

이런 유형의 문제도 좀 많이 풀어봐야겠다. 

https://school.programmers.co.kr/learn/courses/30/lessons/178871

문제설명

얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.

선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.

문제 해결 방법

이문제 진짜 딕셔너리 순환을 위해서 이중 for문을 사용하지 않고, 하나의 반복문만 사용하고,

더이상의 반복문을 사용하지 않기 위해서, 딕셔너리 두개로 선수의 순위를 바로바로 바꿔주었다. 

코드 구현

def solution(players, callings):
    answer = []
    
    dicct={}
    dic={}
    for idx, i in enumerate(players):
        dicct[i]=idx
    
    for idx, i in enumerate(players):
        dic[idx]=i
        
    
    
    
#     print('dic', dic) # key는 숫자 
#     print('dicct', dicct) # key는 이름 
    
    for i in callings:
        value = dicct[i] # 숫자
        key = dic[value]
        
        value2 = dicct[i]-1
        key2 = dic[value2]
        
        
        dic[value] = key2
        dicct[key] = value2
        
        dic[value2] = key
        dicct[key2] = value
    
    for key, value in dic.items():
        answer.append(value)
    
    return answer

시간/공간 복잡도

최악의 경우 O(N)

최적화 및 개선

시간초과가 났다. 

딕셔너리 전체 순환을 하면 안되나보다.

딕셔너리 두개로 반복문 하나만 사용해서 문제를 풀었다. 

하나의 딕셔너리로 key를 통한 검색을 위해 도중에 key와 value를 바꿔주고자 했지만, 해당 방법을 사용하면 또 반복문을 사용해야 해서 해당 방법은 사용할 수 없었다. 

어려웠던 점

막상 풀고보니 전체 순환을 안할 수 있다는게 넘 신기하다. 

https://school.programmers.co.kr/learn/courses/30/lessons/131128

문제설명

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.

예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.)

두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요.

문제 해결 방법

순회를 통한 문제 해결 

코드 구현

from collections import deque
def solution(X, Y):
    answer = ''
    
    tem = []
    
    Y=list(Y)
    Y.sort()
    
    X=list(X)
    X.sort()
    
    y = deque(Y)
    
    new = deque()
    cnt = 0
    for idx, i in enumerate(X):
        while 1:
            if cnt == len(y):
                break

            t= y[cnt]
            if i == t:
                del y[cnt]
                tem.append(t)
                break
            else:
                if y[cnt]<i:
                    cnt+=1
                else:
                    break
    
    if len(tem) == 0:
        return '-1'
    else:
        cntt = 0
        check = 0
        while 1:
            if cntt == len(tem):
                break
                
            if check == 1:
                break
            
            if tem[cntt] =='0':
                check = 0
                cntt +=1
            else:
                check =1
                
    if check == 0:
        return "0"
        
    tem.sort(reverse=True)
    answer = "".join(tem)
    
    return answer

시간/공간 복잡도

최악의 경우 O(N)

최적화 및 개선

테스트케이스 11번~ 15번까지 실패했다. 

실패 이유는 시간초과였는데, 문제 조건에서 X, Y는 최대 300만 까지의 길이를 가질 수 있다고 했다. 

기존에 내가 작성한 코드는 X를 전부 돌면서 Y또한 전부 순회하도록 돼있었는데, 그러면 시간초과가 날 수 밖에 없는 상황이였다. 즉, 길이가 긴 대상을 전부 순회하지 않고 원하는 값을 찾아야 했다. 

한번의 순회로 각 숫자들의 개수를 셀 수 있어야 했다. 

어려웠던 점

길이가 긴 대상에 대한 고려를 생각해내지 못했다. 

이부분에 대해서 담엔 틀리지 말아야징 ㅎ,,

for i in range(10):
    length = int(input())
    check=[]
    for j in range(8):
        stringg = input()
        check.append(stringg)
    

    #print(check)
    answer = 0
    ccheck = 0
    if length % 2 == 0: # 짝수
        checkN = length // 2
        ccheck = 0
    else:
        checkN = ((length+1)//2)-1 # 홀수 한 가운데 
        ccheck = 1
    
    for one in check: # 가로 체크
        stackk = []
        if ccheck == 0:
            for idx, k in enumerate(one):
                if idx > len(one) - length:
                    break
                
                for ik in range(checkN):
                    stackk.append(one[idx+1])
                
                good = 0
                for jk in range(checkN):
                    print
                    if stackk.pop == one[checkN+idx+1]:
                        good = 1
                    else:
                        good = 0
                        break
                    
                if good == 1:
                        answer+=1
        else:
            for idx, k in enumerate(one):
                if idx > len(one) - length:
                    break
                
                for ik in range(checkN):
                    stackk.append(one[idx+1])
                
                good = 0
                stackk.pop()

                for jk in range(checkN-1):
                    if stackk.pop == one[checkN+idx+1]:
                        good = 1
                    else:
                        good = 0
                    
                if good == 1:
                        answer+=1
    
    for p in range(8): # 세로 체크
        stackk = []
        if ccheck == 0:
            for idx, two in enumerate(check):
                if idx > len(two) - length:
                    break

                for ik in range(checkN):
                    stackk.append(check[idx+ik][p])
                
                good = 0
                for jk in range(checkN):
                    if stackk.pop == check[checkN+idx+jk][p]:
                        good = 1
                    else:
                        good = 0
                    
                if good == 1:
                        answer+=1
        else:
            # 홀수 
            for idx, two in enumerate(check):
                if idx > len(two) - length:
                    break
                
                for ik in range(checkN):
                    stackk.append(check[idx+ik][p])
                
                good = 0
                stackk.pop()
                for jk in range(checkN-1):
                    if stackk.pop == check[checkN+idx+jk][p]:
                        good = 1
                    else:
                        good = 0
                    
                if good == 1:
                        answer+=1


    
    
    print("#"+str(i+1), str(answer))

https://swexpertacademy.com/main/code/problem/problemDetail.do

문제 해결 방법 및 코드 구현

N = int(input())

for i in range(N):
    stringg=""
    n, a, b = input().split()
    n = int(n)
    a = int(a)
    b = int(b)

    so = 0
    dae = 0
    if a+b <= n:
        so = 0
    else:
        so = abs(a+b) - n

    if a>= b:
        dae = b
    else:
        dae = a

    if a == b == n:
        so = a
        dae = b
    
    if a == b and a != n:
        dae = a

    
    stringg="#"+str(i+1)+" "+ str(dae)+" "+ str(so)
    print(stringg)

시간/공간 복잡도

최악의 경우 O(N)

최적화 및 개선

따로 하지않음

어려웠던 점 / 느낀점

애매하게 테스트케이스를 절반만 맞추고 이랬는데, 별 다르게 고쳐나갈 방법을 생각할 수 없었다. 

테스트케이스로 들어갈만한 실제 값을 임의로 넣어보는 수 밖에 없었다. 

사실 프로그래머스로 공부하다보면 질문하기 기능에 의존하게 되는데, swea는 질문 할 수도 없고 사람들이 댓글로 힌트를 달지 않은 경우, 오로지 혼자 힘으로 테스트케이스를 만들어서 적용해보는 수 밖에 없다. 

코테 칠때 도움 많이 될 듯

D3 정답률 70.12로 시작했으니  80으로 가봐야겠다.