[프로그래머스] 코딩테스트 개념 해시(딕셔너리) / Greedy

 

 

1. 해시 문제

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

프로그래머스

 

 

아래 코드처럼 remove를 사용했더니

def solution(participant, completion):
    d = {}
    for x in completion:
        participant.remove(x)
    answer = participant[-1]
    return answer

37점으로 시간 초과가 나왔다.

아마도 remove 모듈이 시간 복잡도 O(n)라서

총 O(n^2)이 되었고, 문자열이라서 메모리까지 초과가 되었던 것 같다. 

 

 

다른 풀이를 보니 

해시로 O(n) 만으로도 풀 수 있었다. (전수조사)

def solution(participant, completion):
    d = {}
    for x in participant:
        d[x] = d.get(x, 0) + 1
    for x in completion:
        d[x] -= 1
    person = [k for k, v in d.items() if d[k] != 0]
    answer = person[-1]
    return answer

 

와.. 이렇게 푼 사람도 있었다.

Counter는 collections 모듈 내에서도 딕셔너리에 특화된 클래스이다.

리스트나 문자열 등 iterable 객체나 iterable 객체의 집합을 받아서 각 값들이 몇 개 인지를 value 값으로 리턴하는 클래스이다.

요소는 딕셔너리의 키고 저장되고 갯수는 딕셔너리 값으로 반환한다.

import collections


def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

answer의 keys들을 모아서 리스트로 만들고 첫번째 인덱스(원소는 하나뿐이므로)만 봅아서 반환해준다.

 

---

2. 탐욕법(Greedy)

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

프로그래머스

 

def solution(n, lost, reserve):
    lst = [1] * (n + 2)
    # 각 번호별로 학생들일 가지고 있는 체육복 수
    for x in reserve:
        lst[x] += 1
    for x in lost:
        lst[x] -= 1
    # 여분 있는 학생이 양 옆 없는 학생에게 나눠줌
    for x in range(1, n + 1):
        if lst[x] == 0 and lst[x - 1] == 2:
            lst[x - 1: x + 1] = [1, 1]
        elif lst[x] == 0 and lst[x + 1] == 2:
            lst[x : x + 2] = [1, 1]
    # 체육복이 있는 사람의 최종 합을 구한다.
    answer = 0

    for x in lst:
        if x > 0:
            answer += 1
    answer -= 2
    return answer

 

---

3. 정렬

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

프로그래머스

 

def solution(numbers):
    nums = []
    for number in numbers:
        nums.append(list(str(number)))
    nums.sort(reverse = True)
    # print(nums)
    # nums.sort(key = lambda x : (x[0]), reverse = True)
    answer = ''
    print(nums)
    for num in nums:
        for x in num:
            answer += x
    return answer

이렇게 풀었더니 

테스트 1
입력값 〉	[6, 10, 2]
기댓값 〉	"6210"
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	[['6'], ['2'], ['1', '0']]

테스트 2
입력값 〉	[3, 30, 34, 5, 9]
기댓값 〉	"9534330"
실행 결과 〉	실행한 결괏값 "9534303"이 기댓값 "9534330"과 다릅니다.
출력 〉	[['9'], ['5'], ['3', '4'], ['3', '0'], ['3']]

테스트 3
입력값 〉	[6, 14, 10, 12, 2]
기댓값 〉	"62141210"
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	[['6'], ['2'], ['1', '4'], ['1', '2'], ['1', '0']]

테스트 결과 (~˘▾˘)~

3개 중 2개 성공

 

테스트 2에서 3, 30이

330 > 303 이 되어 틀린 케이스가 되게 된다.

어떻게 비교해야할까

 

해답에서 얻은 아이디어

정렬의 기준을 정하기(패턴의 탐색) 숫자의 크기는 0이상 1000이하인 자연수이므로 어떤 수를 가져오든 4번을 반복한 수로 변환한 값으로 서로의 크기를 비교한다면(ex. 23 -> 23232323) 앞선 '크게 만드는 것 우선'을 만족하는 기준을 만들 수 있게 된다.

어떻게 이 생각을 했지..

def solution(numbers):
    # 모든 숫자를 문자열로 변환해주기
    numbers = [str(number) for number in numbers]
    # 변환한 숫자를 4번 반복한 값으로 정렬하기
    numbers.sort(key = lambda x : (x*4)[: 4], reverse = True)
    print(numbers)
    # 숫자가 0인 경우 따로 설정해둔다.
    if numbers[0] == '0':
        answer = '0'
    else:
        answer = ''.join(numbers)
    return answer

 

테스트 1
입력값 〉	[6, 10, 2]
기댓값 〉	"6210"
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	['6', '2', '10']

테스트 2
입력값 〉	[3, 30, 34, 5, 9]
기댓값 〉	"9534330"
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	['9', '5', '34', '3', '30']

테스트 3
입력값 〉	[6, 14, 10, 12, 2]
기댓값 〉	"62141210"
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	['6', '2', '14', '12', '10']

테스트 결과 (~˘▾˘)~

3개 중 3개 성공

 

참고로 리스트 정수 요소들을 str 요소들로 바꿔줄 때 아래처럼 표현 가능하다는 걸 알아주면 좋다.

numbers = [1, 309, 4434]
numbers1 = list(map(str, numbers))
numbers2 = [str(number) for number in numbers]
print(numbers1)
print(numbers2)

출력

['1', '309', '4434']
['1', '309', '4434']

 

 

 

---

4. 탐욕법으로 큰 수 만들기

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

프로그래머스

 

 

 

참고 블로그

https://velog.io/@clayryu328/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%9D%B8%EA%B3%B5%EC%A7%80%EB%8A%A5-%EB%8D%B0%EB%B8%8C%EC%BD%94%EC%8A%A4-3%EA%B8%B0-%EC%88%98%EC%97%85%EB%82%B4%EC%9A%A9-%EC%A0%95%EB%A6%AC-2-6en4iow2