개발자 아지트

1주차의 공부 주제는 다음과 같다. 

• 코딩 테스트를 준비하기 전에 알아야할 팁
• 코딩 테스트를 효율적으로 준비하기 위해서 어떻게 해야하는가
• 코딩 테스트 준비를 위해 프로그래머스를 적극 활용하기

코딩 테스트를 준비하기 전에 알아야할 팁

1) 코딩테스트 준비를 위한 사이트 선정 

코딩테스트의 문제들을 풀기위한 사이트를 선정해야한다. 

선정 기준은 다음과 같은 기준을 고려하면 좋다. 

• 타인의 풀이를 볼 수 있는가?
• 내가 생각한 테스트 케이스를 추가할 수 있는가? 

테스트에 필요한 코드를 작성하기 전에 문제 분석 단계에서 테스트 케이스를 고려할 때, 충분히 생각하여 테스트 케이스를 추가하여 공부하는 것이 좋다. 

2) 문제 풀다 막힐 경우에 취해야할 태도

코딩테스트 준비를 위해 문제를 풀 때, 문제를 다 풀지 못했을 경우가 생길 수 있다. 

이런 경우 상실감에 그냥 다른 문제 풀이로 넘어가거나, 그날 공부를 접지 말고 이것을 생각해봐야한다. 

내가 이 문제를 풀기위해서 어디까지 생각을 했는가?

이것을 생각하고 어떤 알고리즘을 적용하려고 했는지, 그렇게 생각한 근거는 무엇인지, 어떻게 구현하려고 했는지를 자신만의 공간에 기록해두는 것이 좋다 .

3) 나무보단 숲을 보자 = 코딩 테스트 준비를 위해 한정된 시간안에 효율적으로 준비를 마치자 

효율적으로 코딩테스트를 준비하기 위해서 문제 풀 때, 문제가 잘 안풀려서 1시간 이상 넘어가는 경우가 있다.

이럴 경우, 시험 보듯 공부하는 것이 좋다. 아무리 잘 안풀리는 문제라도 1시간 이상 고민하게 되면 코딩 테스트라는 시험 준비 자체에 효율이 떨어진다. 1시간이 넘어가면 다른 사람의 코드를 참고하든 하는 것이 좋다. 

4) 코딩 테스트 준비에 있어서 요행을 바라는것은 도둑놈 심보

짧은 시간 공부해서는 절대로 코딩 테스트에 통과할 수 없다. 

통상적으로 코딩 테스트는 최소 한 달에서 두 달 정도를 매우 집중해서 공부해야한다. 

5) 개념이나 원리 공부후 자신만의 언어로 개념 정리 하면 도움이 된다. 

코딩 테스트를 효율적으로 준비하기 위해서 어떻게 해야하는가

1)자신이 가장 잘 할 수 있는 프로그래밍 언어를 선택하자. 

2)문제 분석하는 방법을 연습하라 

3)의사 코드로 설계하는 연습을 몸에 익히자

4)문제를 푸는 사이트의 환경이 실제 시험 장소에서 제공하는 환경과 비슷한 프로그래머스 사이트 사용을 추천한다. 

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

문제설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

k는 1 이상 5,000 이하인 자연수입니다.

dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.

dungeons의 가로(열) 길이는 2 입니다.

dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.

"최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.

"최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.

서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

입출력 예

k         dungeons         result

80        [[80,20],[50,40],[30,10]]      3

입출력 예 설명

현재 피로도는 80입니다.

만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면

현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.

남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.

남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.

만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면

현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.

남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.

남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.

따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.

문제 해결 방법

1. dungeons에서 모두 나올 수 있는 순서에 대해 경우의 수를 순열로 뽑는다.

2. 리스트를 하나 만들고, 순열로 뽑은 모든 경우의 수에 대해서 조건을 따져가면서 던전에 방문한 횟수를 카운트 하여 최종적으로 카운트 한 수를 해당 리스트에 추가한다. 

2-1. 위에서 말한 조건으로 각 던전의 최소 필요 피로도가  k와 같거나 커야지 던전에 방문할 수 있으니 해당하는 조건을 체크한다. 

2-2. 만약 k가 특정 던전에 방문할 수 있다면 k에서 소모 피로도를 빼준다. 

3. 2번에서 만든 리스트에서 max값을 구하여 출력한다. 

코드 구현

from itertools import permutations

def solution(k, dungeons):
    answer = -1
    
    cpk=k
    cases = list(permutations(dungeons, len(dungeons)))
    checkList=[]
    
    for i in range(len(cases)):
        cpK=k
        checkcheck = 0
        for j in range(len(cases[i])):
            if cpK >= cases[i][j][0]:
                cpK = cpK - cases[i][j][1]
                checkcheck += 1
            else:
                pass
            
            if j == len(cases[i])-1:
                checkList.append(checkcheck)

    answer = max(checkList)
    
    return answer

주석 포함 코드

from itertools import permutations

def solution(k, dungeons):
    answer = -1
    
    #print('k', k, 'dungeons', dungeons)
    # 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"
    # 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"
    
    #최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됨
    
    #하루에 한 번씩 탐험할 수 있는 던전이 여러개
    
    # 1. dungeons는 [0]기준 MAX를 뽑는다. 
    # 2. dungeons의 순열을 뽑는다. 
    
    
    cpk=k
    
    
    cases = list(permutations(dungeons, len(dungeons)))
    #print(cases)
    
    checkList=[]
    #print("")
    
    for i in range(len(cases)):
        #maxx = cases[i][0][0]
        cpK=k
        #print("1 cpK", cpK)
        checkcheck = 0
        #print('i', i, cases[i])
        for j in range(len(cases[i])):
            #print('j', j, cases[i][j])

            if cpK >= cases[i][j][0]:
                cpK = cpK - cases[i][j][1]
                #print('cpK', cpK)
                checkcheck += 1
            else:
                pass
            
            if j == len(cases[i])-1:
                checkList.append(checkcheck)
            
        #print("")
        #print("")


    #print(checkList)
            
    answer= max(checkList)
    
    return answer

시간/공간 복잡도

최악의 경우 O(N^2)

최적화 및 개선

하지않았다. 

어려웠던 점

안풀어본 문제유형(완전탐색)이라 완전 쫄았다. 완전탐색 문제를 풀기위해서 대략 어떤 알고리즘이 필요한지 찾아보고 일단은 대충이라도 공부했다. (요즘 좀 바쁨) 암튼 대충 이런저런 방법으로 생각해보다가 문제를 풀었다 .

진짜 내가 이 문제를 푼거에 대해서 아주 놀랍다 하하 박수 ~~~ 짝짝~~

생각보다 진짜 별거아니네 !!! 쫄지마 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

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

문제설명

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

• arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
• arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

제한사항

배열 arr의 크기 : 1,000,000 이하의 자연수

배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

입출력 예

arr       answer

[1,1,3,3,0,1,1]      [1,3,0,1]

[4,4,4,3,3]          [4,3]

입출력 예 설명

입출력 예 #1,2

문제의 예시와 같습니다.

문제 해결 방법

stack을 이용하여 문제를 푼다. 
1. stack 구실을 할 임의의 리스트를 하나 만든다. 

2. arr의 원소를 순회하면서 임의의 리스트에 첫번째 원소를 push한다. 

2-1. 첫번째 이후의 원소들은 임의의 리스트의 마지막에 push한 값을 pop을 통해 꺼낸다.

2-2. 2-1번을 통해 꺼낸 값과 현재 넣고자 하는 arr의 원소를 비교하여 값이 같으면 pass하고 같지 않으면 push 한다. 

코드 구현

1. 효율성 통과하지 못한 코드 

def solution(arr):
    answer = []
    
    # pivot 변수 = p
    # 이전 pivot을 기억하는 변수 = pre_p
    check = 0
    pre_p = arr[0]
    l=len(arr)
    for i in range(1, len(arr)):
        p = arr[i]
        #print('p', p, 'pre_p', pre_p)
        if pre_p == p:
            pre_p = p
            arr[i] = 10
            # '-'를 세는 변수 = check
            check+=1
        else:
            pre_p=p
    
    for i in range(check):
        arr.remove(10)
        
    answer = arr
    return answer

2. 효율성 통과한 코드

def solution(arr):
    stack = []
    
    for i in range(len(arr)):
        if i == 0:
            stack.append((arr[i]))
        else:
            top = stack.pop()
            stack.append(top)
            if arr[i]==top:
                pass
            else:
                stack.append(arr[i])
    
    return stack

시간/공간 복잡도

1. 효율성을 통과하지 못한 코드: O(N^2)

2. 효율성을 통과한 코드: O(N)  

최적화 및 개선

처음에 효율성을 통과하지 못한 코드에 대해서 중첩 되지 않는 for문을 썼는데 왜 시간복잡도 효율성이 통과되지 않는지 이해가 안갔다. 혹시 내가 stack자료구조를 고려하지 않고 코드를 작성해서 그 부분에서 오류가 나는건가? 싶었다. 그래서 코드를 stack자료구조를 고려해서 리스트를 stack화 해서 코드를 짰다. 확실히 pop함수를 사용해서 그런가 편리하고 뒷처리를 해주지 않아도 되는 점이 깔끔하고 좋았다. 그리고 효율성에도 통과했다. 

그렇다면 1번 코드는 어디에서 효율성을 많이 잡아먹는가?

바로 for문에 있는 remove함수 때문이다. 

remove함수는 시간복잡도 O(N)을 잡아먹는다. 그런데 이걸 for문으로 처리하고있으니 시간복잡도가 O(N^2)이 되었던 것이였다. 

어려웠던 점

파이썬 각각의 함수들의 특성에 대해서는 잘 몰랐는데, 이렇게 문제를 풀면서 기억에 각인도 시키고 하니 좋다. 

어쩜 코딩테스트 문제들은 하나같이 문제 푸는 사람이 그 문제를 풀기위해서 알아야 하는것을 모른다면, 그것에 대해서 스스로 알게되지 않고서야 절대 문제를 못풀게끔 되어있는게 너무 신기하다. 이제야 드는 생각인데, 코딩테스트나 알고리즘 공부 어쩌면 좋은 제도일지도 모르겠다는 생각이 든다.  

몇일간 못풀던 문제를 풀었다. 속이 후련해야 하는데 이 문제는 속이 시원하면서도 어딘가 찝찝하다;; 

문제설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

numbers의 길이는 1 이상 100,000 이하입니다.

numbers의 원소는 0 이상 1,000 이하입니다.

정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

numbers return

[6, 10, 2] "6210"

[3, 30, 34, 5, 9]    "9534330"

문제 해결 방법

1. numbers 요소들을 map함수를 통해 문자열로 변경

2. 0번째 요소부터 바로 다음의 요소를 이용해서
'다음의 요소+현재 보는 요소' , '현재 보는 요소+ 다음의 요소'를 int형으로 변환하여 대소 비교를 한 후 
리스트 index 정렬을 해주었다. 

이때 한자리수에 대한 처리가 어려웠다. 

구체적으로 말하자면 

1. 입력값 [979, 97, 978, 81, 818, 817] 일 때 기댓값 "9799797881881817"인 경우,

2. 입력값 [1000, 111, 110, 101, 100, 11, 10, 1, 0] 일 때 기댓값 "1111111101011010010000"인 경우가 해결이 안되었다. 

문자열을 단순히 복사하여 문자열을 부풀린 후 대소비교는 안하려했으나 이 방법 밖에 풀이가 없는듯 하다. ;;

입력값 81, 818, 817이 있다고 쳤을 때, 문자열로 변환후 정렬을 하면

-> 818, 817, 81으로 나올것이다.  

우선 818, 817의 경우 
818817

817818   두가지 경우가 나올 수 있는데, 818817이 더 크다. 따라서 818, 817의 순서는 자연스럽다. 

817과 81의 경우

81817

81781  두가지 경우가 나올 수 있는데, 중에서 81817이 더 크다. 따라서 현재 817, 81의 순서는 자연스럽지 않다. 

이를 전체적으로 종합해보면 818, 81, 817의 순서가 자연스럽다는 결론을 내릴 수 있다. 

그러나 처음에 818, 81, 817을 문자열로 변환한뒤 정렬한게 818, 817, 81인데,
818, 817, 81 이것을 어떻게 818, 81, 817순으로 정렬할 수 있을까?

두자리 수 인 81을 세자리 수로 만들면서 동시에 817보다는 크고 818보다는 작아야 한다. 

81 뒤에 0부터 시작해서 9까지 어느 수를 붙이든간에 부자연스럽다는 것을 알 수 있다. 

0~7을 붙일경우 817보다 같거나 작게되고, 8을 붙일 경우 818과 같게 되고, 9를 붙이면 818보다 크게 된다.

또한 81이 두자리 수라고해서 다른 숫자를 붙일 경우 다른 숫자들에도 해당 숫자를 붙여주는게 바람직 하다. 

그런데 이렇게 다른 규칙이 없는 임의의 숫자를 정하여 붙이게 되면 숫자의 크기가 어긋나게된다. 

따라서 최선의 방법은 자기 자신을 한번더 자신에게 붙이는 방법이 있다. 

818, 81, 817을 

818818, 8181, 817817 로 한 다음, 
제한 사항에 numbers의 원소는 0이상 1,000 이하라는 사항을 반영하여,

위 원소들을 길이 4로 끊는다.  (3으로 끊어버리면 대소 비교가 어려움--> 818, 818, 817)

8188, 8181, 8178 이때 대소 비교를 하면,
8188 > 8181 > 8178 순으로
818, 81, 817의 순서를 유지할 수 있게된다.

이때, 몇가지 고려해야 할 것들이 있는데, 아래의 테스트케이스를 통해 설명하겠다.

위와같은 논리를 아래에 테스트케이스에 적용한다. 

입력값 〉            [3, 30, 34, 5, 9]
기댓값 〉            "9534330" 에 적용하면

문자열로 변환하여 정렬한다. [9, 5, 34, 30, 3]
9534까지 잘 가다가 330과 303에 걸리게 된다.

303보다 330이 더 크다.  

하지만 이때 3은 한자리수로써, 자기 자신을 한번 더 자신에게 붙여봤자 33이 된다. 

이를 모든 원소에 적용하면

99 55 3434 3030 33이 된다.

이 경우일 때는 결과적으로 정렬에 문제가 없다. 


그러나 다음과 같은 경우에서 문제가 된다.  

입력값 〉           [111, 110, 11, 1]

기댓값 〉           "111111110"

입력값을 문자열로 변환후 2배 해보면

111111

110110

1111

11

대소 비교를 해보면,  111111>1111>110110>11

즉, 111, 11, 110, 1이 된다. 

입력값을 문자열로 변환후 3배 해보면

111111111

110110110

111111

111

대소 비교를 해보면, 111111111>111111>111>110110110

즉, 111, 11, 1, 110이 된다. 

제한사항에 numbers의 원소는 0이상 1,000이하라고 되어있다. 

해당 조건을 고려하여 한자리수 문자열을 위해서 입력값 요소들에 대해 3배로 불리기를 해주고 비교해야 한다. 

코드 구현

def solution(numbers):
    answer = ''

    str_list = list(map(str, numbers))
    str_list.sort(key = lambda x: x*3, reverse=True)
    
    for i in str_list:
        answer+=i

    if int(answer)==0:
        answer = '0'
    
    return answer


# 예전 코드
#     tmp=0
#     i=0
#     while 1:
#         tmp=0
#         if i >= len(str_list)-1:
#             break
            
#         if int(str_list[i]+str_list[i+1]) > int(str_list[i+1]+str_list[i]):
#             pass
                            
#         elif int(str_list[i]+str_list[i+1]) < int(str_list[i+1]+str_list[i]):
#             tmp=str_list[i+1]
#             str_list[i+1]= str_list[i]
#             str_list[i]=tmp
#         i+=1
        
# 참회 코드
#for i in str_list:
#    answer+=str_list[i]
# 완전 잊어먹지 않을 정도로 충격먹음ㅋ
#print(answer)

#print(str_list)

시간/공간 복잡도

O(NlogN)

최적화 및 개선

람다를 쓰면서 코드 최적화를 한 것 같다. 

어려웠던 점

뭐랄까.. 이 문제는 문자열로써의 숫자가 갖는 성질에 대한 이해같다. 

문자를 불려서 해당 값을 비교한다는게 숫자로써의 비교가 아니라 대상으로써의 비교의 연속같다. 

30, 34라는 문자와 3이라는 문자의 비교 같다. 

문자열에는 맨 앞자리[0]가 언제나 큰 우선순위를 갖기때문에 

34가 3434가 되는것이 3이 33밖에 안되는 것 30이 3030이 되는것이 전혀 문제가 되지 않는다. 

즉 숫자 크기로 보면 안되고 오로지 인덱스가 주는 가중치를 생각해야한다. 3은 30보다 커야 하고 그만큼의 가중치를 받아야 한다. 

아 쓰면서도 뭔말인지 좀 살짝 이해하기 어려운데 아무튼 문자열을 하나의 덩이라고 생각하고 덩이끼리 비교한다고 생각한다. 

람다 사용법을 몰라서 생소하고 쓸줄 몰랐다. 

람다는 간략하게 코드 짜고싶을때 사용하기 좋은 것 같다. 

위 코드에서 str_list의 key(원소)들은 lambda 익명 함수의 매개변수 x로써의 역할을 하게된다. 

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

문제설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119

박준영 : 97 674 223

지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

phone_book의 길이는 1 이상 1,000,000 이하입니다.

각 전화번호의 길이는 1 이상 20 이하입니다.

같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제

입출력 예 설명

입출력 예 #1

앞에서 설명한 예와 같습니다.

입출력 예 #2

한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3

첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

문제 해결 방법

nums를 딕셔너리로 만들고, 파이썬 sort기본 정렬을 한다. 

문자열에 특정 단어가 있는지 확인하기 위해 find함수를 사용하였음

코드 구현

def solution(phone_book):
    answer = True
    dict_phone = {}
    phone_book.sort()
    
    for i in range(len(phone_book)):
        dict_phone.setdefault(phone_book[i])

    for i in range(len(phone_book)):
        if i == len(phone_book)-1:
            break
            
        if (phone_book[i+1].find(phone_book[i])) == -1:
            pass
        else:
            if (phone_book[i+1].find(phone_book[i]))==0:
                answer = False
                return answer
            else:
                pass
        
    return answer

시간/공간 복잡도

O(N)

최적화 및 개선

처음에 while문 하나로 검색하고자 하는 단어를 카운팅 하면서 nums에 있는 모든 단어들을 for문으로 조회하도록 코드를 짰는데, 효율성에서 시간초과가 나서 while문을 없애고 반복문 한번으로 조회할수 있게 해야했다. 

그렇게 하기위해서 파이썬 sort기본 정렬을 사용하였다.

어려웠던 점 및 느낀점

문자열을 sort했을때 맨 앞에 문자일수록 가중치가 높아지고 만약 같은 가중치 선에서 우위를 가릴 수 없다면 그 다음 번호로 넘어가서 우위를 가린다. 나는 sort를 활용할 줄 몰랐다. 그리고 미리 sort를 하는게 이렇게 코드 효율성에 도움이 될줄 몰랐다. 

파이썬 자료형 set에 대해서도 알게되었다. 

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

문제설명

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서N/2마리를 가져가도 좋다고 했습니다.

홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

첫 번째(3번), 두 번째(1번) 폰켓몬을 선택

첫 번째(3번), 세 번째(2번) 폰켓몬을 선택

첫 번째(3번), 네 번째(3번) 폰켓몬을 선택

두 번째(1번), 세 번째(2번) 폰켓몬을 선택

두 번째(1번), 네 번째(3번) 폰켓몬을 선택

세 번째(2번), 네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.

당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.

nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.

폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.

가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

문제 해결 방법

리스트를 해시로 변경하여 문제를 해결하였습니다.

코드 주석을 참고하세요.

코드 구현

def solution(nums):
    answer = 0
    # 총 포켓몬 중에서 N은 데려가도 되는 포켓몬 수임
    N = len(nums) // 2
    
    # 포켓몬 담을 딕셔너리
    # 딕셔너리 key를 nums 값이 중복되지 않게 채우고 value는 0으로 초기화함
    x={}
    for i in range(len(nums)):
        x[nums[i]]= 0
    # 포켓몬 종류대로 수를 세어서 value에 포켓몬 수 만큼 매김
    for i in range(len(nums)):
        tmp = x[nums[i]]
        tmp +=1
        x.update({nums[i] : tmp})
    
    # 포켓몬 종류 수가 포켓몬 잡을 수 있는 수 보다 크거나 같으면 
    # 포켓몬 잡을 수 있는 수를 반환
    if len(x) >= N:
        answer = N
    else:
    # 포켓몬 종류가 포켓몬 잡을 수 있는 수 보다 작으면 
    # 포켓몬 종류 수 반환 
        answer = len(x)
        
    return answer

시간/공간 복잡도

O(n)

최적화 및 개선

하지않음 

어려웠던 점

아직 파이썬 딕셔너리 문법에 익숙하지 않아서 헤멘다.
변수.update({바꾸고싶은 key: 바꾸고 싶은 value})

그리고 내가 변수 이름을 정할 때 너무 생각나는대로 막 정해서 그런지 스스로도 코드 짜면서 헷갈린다....

다음부터는 이런 점을 고쳐나가야겠다. 

안녕하세요. 지금 기분이 굉장히 좋습니다.!!!!! 자료구조를 공부하고 이렇게 통쾌하게 문제를 풀어본 경험은 오늘이 처음입니다!!! 세상 사람들아!! 내가 이 문제를 드디어 자료구조로 풀었다!!!!!!

문제설명

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

5
12 7 9 15 5
13 8 11 19 6
21 10 26 31 16
48 14 28 35 25
52 20 32 41 49

35

문제 해결 방법

우선 실버2를 푼다는 생각에 넘넘 긴장되고 겁이나서 페이지 하단에 있는 '알고리즘 분류'를 먼저 보고 참고하여 문제를 풀었다. 해당 문제는 우선순위 큐에 속한다. 따라서 파이썬의 heapq모듈을 활용하여 해당 문제를 풀고자 했다. 

코드 구현

import heapq

n = int(input())
#n개의 줄에 n개의 수가 주어짐 
#n개의 줄에 n개의 원소가 들어가게끔 만들어야함
list_list = []
total=[]
for i in range(n): # 이렇게 쓰면 딱 원소가 5개임
    #print('i', i)
    list_list.append(list(map(int, input().split())))
    
    
    for j in range(n):
        total.append(list_list[0][j])
    list_list=[]

    heapq.heapify(total)
    answer = heapq.nlargest(n,total)

    if i==0: 
        pass
    else:
        #print('i', i, 'prev total', total)
        for p in range(n):
            heapq.heappop(total)
    
    #print('i', i, 'total', total)
    #print('i', i, 'answer', answer)
    
   
# total=[]

print(answer[-1])

시간/공간 복잡도

????? 뭘적징

최적화 및 개선

처음에는 '메모리 초과'가 떴다. 엥 메모리초과가 뭐지? 설마 이것이 공간복잡도 인가?? 와우!! 처음 보는 결과다 ㅠㅠ

감격스러운 마음에 막 찾아봤다. 

메모리 초과란?

공간 복잡도를 초과한 경우를 말하고, 공간 복잡도란 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양을 말한다. 

과연내가 어디서 공간을 많이 잡아먹은거지... 첨엔 어떻게 이걸 찾아야 하는건지 잘 모르겠었다. 

그래서 무작정 코드를 다시 봤다.. 코드를 다시 보니까 첫 제출할때는 미처 발견하지 못한 에러들을 3개나 발견했다. !!

혹시나 이 에러를 해결하면 문제를 풀까 해서 다시 제출해봤는데 택도없었다! 

모든 입력을 배열에 저장하면 당연히 메모리 초과입니다. 문제의 메모리 제한은 겨우 8MB입니다. 아무리 작은 자료형으로 저장한다고 해도 short형 (2바이트) 천만 개면 약 20MB로 역시 메모리 초과입니다. 입력을 전부 저장하지 않고 푸는 방법을 생각해 보세요. 힌트는 입력되는 정수의 범위에 있습니다. (백준 가이드)

그래서 설마 내가 total 리스트에 모든 n개의 원소 n개 받은것을 풀어서 넣고 갖고 다닌것이 공간복잡도를 많이 잡아먹는건가 싶어서 그 부분을 좀 최적화 해봤다. 그랬더니 

느낀점

기분이 너무 좋다 진짜!!! 공부할 맛 난다. 오늘 큰거 깨달았다.

코테 준비 및 알고리즘 공부는 이런식으로 하면 되겠구나 

자료구조 및 알고리즘 미리 공부 후에 문제 풀이하기~

근데 한편으로는 아쉽다 이렇게 하면되는걸.. 그동안 맨땅의 헤딩을 즐겨했던 나..
그래서 사기가 많이 떨어졌던 과거의 나... 

나야 고생했고 앞으로 잘해보자~ ^^