211229_Code in the morning

Code in the morning, 매일 아침 알고리즘 문제를 풉니다.

💬 문제 설명: 나누어 떨어지는 숫자 배열

array의 각 element 중 divisor로 나누어 떨어지는 값을 오름차순으로 정렬한 배열을 반환하는 함수, solution을 작성해주세요.
divisor로 나누어 떨어지는 element가 하나도 없다면 배열에 -1을 담아 반환하세요.

 

📍 제한 사항

• arr은 자연수를 담은 배열입니다.
• 정수 i, j에 대해 i ≠ j 이면 arr[i] ≠ arr[j] 입니다.
• divisor는 자연수입니다.
• array는 길이 1 이상인 배열입니다.

 

 

💡 나의 풀이 

def solution(arr, divisor):
    answer = []
    for a in arr: 
        if ((a % divisor)==0):
            answer.append(a)
    if len(answer) == 0: 
        answer.append(-1)
    else:
        answer.sort()
    return answer

* Array의 공집합을 표현할 때에는 len이 0이란 것을 사용한다.

👉🏻 문제 바로가기 

코딩테스트 연습 - 나누어 떨어지는 숫자 배열

 

 

 

---

 

 

Code in the morning, 매일 아침 알고리즘 문제를 풉니다. 

💬 문제 설명: 모의고사

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

📍 제한 사항

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

 

 

💡 나의 풀이 

def solution(answers):
    answer = []
    # 정답 사이클
    a1 = [1,2,3,4,5] #5개 반복
    a2 = [2,1,2,3,2,4,2,5] #8개 반복
    a3 = [3,3,1,1,2,2,4,4,5,5] #10개 반복
    
    score1 = 0
    score2 = 0
    score3 = 0
    
    #문제를 맞췄는지 확인, 맞췄을 때 점수 +1
    for i in range (0,len(answers)):
        b1 = i%5
        b2 = i%8
        b3 = i%10
        
        # i번째 문항에 찍은 답
        if a1[b1] == answers[i]:
            score1 += 1
        
        if a2[b2] == answers[i]:
            score2 += 1
        
        if a3[b3] == answers[i]:
            score3 += 1
    winner = max(score1, score2, score3)
    if winner == score1:
        answer.append(1)
    if winner == score2:
        answer.append(2)
    if winner == score3:
        answer.append(3)
    return answer

 

👉🏻 문제 바로가기 

 

---

Code in the morning, 매일 아침 알고리즘 문제를 풉니다. 

💬 문제 설명: 완주하지 못한 선수

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

📍 제한 사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

 

 

💡 나의 풀이 

def solution(participant, completion):
    answer = ''
    for c in completion:
        participant.remove(c)
    participant = ''.join(participant)
    return participant

시간 초과 ^-ㅠ

 

 

* 2중포문으로 풀었더니 효율성에서 전부 실패 하였다. 이는 제한사항에 걸리기 때문이다. 2중포문은 시간복잡도 N^2 이다. 제한사항에 참여한 선수는 1명 이상 10만명 이하인데 10만을 N에 대입하면 100억이 된다. 100억이면 무조건 시간 초과로 테스트에 통과하지 못한다고 보면 된다. 마지노선을 1억이라 생각해야 한다.

* sort를 이용하여 풀었다. sort는 시간복잡도로 nlogn이다. 그리고 for문 하나가 있는 for문은 시간 복잡도 n. 그래서 빅O로 봤을때 총 시간 복잡도는 nlogn이 된다. n에 10만을 대입해보면 50만이다. 충분히 시간효율성에서 통과 할 수 있는 값이다.

 

 * 이 문제는 해시로 풀어야 한다고 함. 해시는 나중에 배워서 풀어보는걸로

 

--------

파이썬에서 권장하지 않는 패턴입니다.

>>> s = [1, 3, 5]
>>> for i in range(len(s)):
...     print(s[i])
... 
1
3
5

• 파이썬에서 권장하는 패턴

>>> for v in s:
...     print(v)
... 

• 리스트.remove(값)
  이 방법은 remove함수에 값을 넘겨주면 리스트에서 같은 값을 가지는 원소를 지워줍니다. 하지만 모든 값들을 지워주지는 않고 가장 먼저 발견된 요소를 지워줍니다. 

 

 

💡 다른 해설

def solution(participant, completion):
    answer = ''
    participant.sort()
    completion.sort()
    for i in range (len(completion)): 
        if participant[i] != completion[i]:
            return participant[i]
        
    return participant[-1]

1. 우선 정렬을 한 후

2. 각 인덱스에 위치하는 값이 일치하는지 확인한 후, 불일치 시 해당 값을 리턴

3. 마지막 리턴문은, completion과 participant 마지막까지 비교해도 값이 모두 같았다면 제일 마지막 정렬의 참가자가 완주못했다는 의미가 되므로, 제일 끝 요소를 리턴해주는 것. 

 

* 나는 당연히 particpant 개수로 for 문을 돌려야 한다고 생각했는데, 그렇게되면 completion의 인덱스보다 숫자가 켜져서 에러가 뜨더라니!

 

출처: https://deftkang.tistory.com/164 [deftkang의 IT 블로그]

👉🏻 문제 바로가기 

 

---

Code in the morning, 매일 아침 알고리즘 문제를 풉니다. 

💬 문제 설명: 2016년

2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까지 각각 SUN,MON,TUE,WED,THU,FRI,SAT 입니다. 예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 "TUE"를 반환하세요.

 

 

📍 제한 사항

• 2016년은 윤년입니다.
• 2016년 a월 b일은 실제로 있는 날입니다. (13월 26일이나 2월 45일같은 날짜는 주어지지 않습니다)

 

 

💡 나의 풀이 

def solution(a, b):
    if (a == 1 or a == 4 or a == 7):
        index = 4
    elif (a == 3 or a == 11):
        index = 1
    elif (a == 5):
        index = 6
    elif (a == 6):
        index = 2
    elif (a == 9 or a == 12):
        index = 3
    elif a == 10:
        index = 5
            
    day_temp = index + b
    if day_temp%7 == 1:
        result = 'MON'
    elif day_temp%7 == 2:
        result = 'TUE'
    elif day_temp%7 == 3:
        result = 'WED'
    elif day_temp%7 == 4:
        result = 'THU'
    elif day_temp%7 == 5:
        result = 'FRI'
    elif day_temp%7 == 6:
        result = 'SAT'
    elif day_temp%7 == 0:
        result = 'SUN'
        
    return result

 

월별로 고유값을 주고, 

해당 고유값 + 날짜 해서 나머지로 요일을 구했는데, 또 런타임 에러가 뜬다....

 

 

* python or 구문을 쓸 때, 

a == 1 or 2 or 3 이렇게 쓰면 X

a == 1 or a == 2 or a == 3 이런식으로 써야 O

 

💡 다른 해설

def solution(a, b):
    months = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    days = ['THU', 'FRI', 'SAT', 'SUN', 'MON', 'TUE', 'WED']
    return days[(sum(months[:a-1])+b)%7]

배열을 엄청 똑똑하게 활용했다. 

 

👉🏻 문제 바로가기