[Day3] 코딩테스트 예제

이석영·2020년 12월 3일
0

Programmers

목록 보기
3/47
post-thumbnail

3일차는 1. 코딩테스트 예제의 설명을 듣고 2. 풀이예제를 확인하고 3. 실습을하는 순서로 진행된다.
하지만 나는 2.풀이예제를 확인하기전에 3.실습부터 진행하는 것으로 순서를 바꾸어 진행하겠다.

해시(Hash) 대표 문제 풀이 : 완주하지 못한 선수

  • 내가 작성한 코드
def solution(participant, completion):
    answer = {}
    
    for i in participant:
        answer[i] = 0
        
    for i in participant:
        answer[i] += 1
        
    for j in completion:
        answer[j] -= 1
    

    for k in participant:
        if answer[k] == 1:
            result = k
    
    return result

아래의 get과 items 메소드를 알고있었다면 조금 더 간단하게 풀이할 수 있었을 것같다.

dict.get() 메소드

get(key[, default])
Return the value for key if key is in the dictionary, else default. If default is not given, it defaults to None, so that this method never raises a KeyError.

출처 : Python Standard Library

딕셔너리에서 특정 key가 존재하면 원래있던 value를 key에 반환하고 그렇지않으면 여기서는 default라고 놓은 어떤 값을 반환하는 메소드이다.

dict.items() 메소드

딕셔너리의 key와 value값을 모두 반환하는 메소드로 사용법은 아래와같다

dict = {'name' : 10}
for a, b in dict.items():
  print(a,b)

탐욕법(Greedy) 대표 문제 : 체육복

  • 내가 작성한 코드
def solution(n, lost, reserve):
    answer = 0
    total = []
    ## 학생수 + 2 만큼의 원소1을 가지는 배열
    for i in range(n+2):
        total.append(1)
    for i in lost:
        total[i] -= 1
    for i in reserve:
        total[i] += 1
    
    for i in range(n+2):
        if total[i] == 2: ## 여벌이있을 때
            if total[i-1] == 0: ## 왼쪽 인원이 채육복이 없으면
                total[i-1] += 1
                total[i] -= 1
            elif total[i+1] ==0: ## 오른쪽 인원이 체육복이 없으면
                total[i+1] += 1
                total[i] -= 1
    # 체육복 가진사람 수 체크
    for i in range(n+2):
        if total[i] >0:
            answer += 1
    ## 편의를 위해 맨앞, 뒤 값을 추가했으므로 빼준다
    answer = answer - 2
    
    return answer

코드가 좀 길다. 풀이 예제를 보니 역시나 더 간편한 방법들이 있었다.
1. 배열 초기화

## 길이 n+2를 가지고 원소가 모두 1인 배열 생성
total = [1] * (n+2)
  1. 체육복 가진 학생수 확인
  • List Comprehension을 이용하여 코드를 한줄로 작성 할 수 있다. 단, 코드 길이만 줄어든 것이지 시간 복잡도는 기존과 비슷할 것이다.
len([n for n in total[1:-1] if n > 0])

정렬 대표 문제 : 가장큰수

def solution(numbers):
    answer = ''
    ## list comprehension을 사용해 원소들을 str type으로 변경한다
    numbers = [str(i) for i in numbers ]
    ## 각 원소를 4번 반복하고 
    numbers.sort(key = lambda x : (x*4)[0:4], reverse = True)
    ## 원소가 모두 0인 경우
    if numbers[0] == '0':
        answer = '0'
    else:
        answer = ''.join(numbers)
    
    return answer
profile
원하는 대로 살자

0개의 댓글