230114 TIL

Today I Learned

Sovle Leet code easy to medium algorithms

Question 1

Super game developer Orelli is in big trouble. The Franz Oh Cheon-seong, which she created, was a huge success, but the number of new users has plummeted these days. The cause was that the stage difference between new users and existing users was too large.

Thinking about how to deal with this problem, she decided to adjust the difficulty by dynamically increasing the game time. As expected, he was a super developer, so he implemented most of the logic easily, but he fell into a crisis in the part of finding the failure rate. Complete the failure rate code for O'Reilly.

The failure rate is defined as:
Number of players who have reached the stage but have not yet cleared it / Number of players who have reached the stage

Complete the solution function to return an array containing the number of stages in descending order from the stage with the highest failure rate when the total number of stages N and an array stages containing the number of stages the user is currently stopping using the game are given as parameters. .

Restrictions
The number N of stages is a natural number between 1 and 500.
The length of stages is greater than 1 and less than 200,000.
Stages contain natural numbers greater than or equal to 1 and less than or equal to N + 1.
Each natural number represents the number of the stage the user is currently challenging.
However, N + 1 indicates a user who has cleared up to the last stage (Nth stage).
If there are stages with the same failure rate, the stage with the lower number should come first.
If no user has reached the stage, the failure rate of the stage is defined as 0.

I/O Example

I/O Example Description

I/O example #1
A total of 8 users challenged Stage 1, and one of them has yet to clear it. Therefore, the failure rate for stage 1 is:

Stage 1 failure rate: 1/8
A total of 7 users challenged Stage 2, of which 3 users have yet to clear it. Therefore, the failure rate for stage 2 is:

Stage 2 Failure Rate: 3/7
Similarly, the failure rates for the rest of the stages are:

Stage 3 Failure Rate: 2/4
Stage 4 failure rate: 1/2
Stage 5 failure rate: 0/1
If the number of each stage is sorted in descending order of failure rate, it is as follows.

[3,4,2,1,5]
I/O Example #2

Since all users are in the last stage, the failure rate for stage 4 is 1 and the failure rate for the remaining stages is 0.

[4,1,2,3]

Timeout code

def solution(N, stages):
    a = [0] * N
    b = [0] * N
    e = {}
    for i in range(1, N + 1):
        for j in range(len(stages)):
            if stages[j] >= i:
                b[i - 1] += 1
            if stages[j] == i:
                a[i - 1] += 1
    for k in range(len(a)):
        if b[k] == 0:
            e[k+1] = 0
        else:
            e[k + 1] = a[k] / b[k]
    d1 = sorted(e.items(), key=operator.itemgetter(1), reverse=True)
    d1 = dict(d1)
    d1 = list(d1.keys())
    return d1

Time exceeds test code 5,9,22

The first code, Logic was okay but time was over. so I tried to figure it out remove last for.

Pass code

def solution(N, stages):
    e = {}
    f = len(stages)
    for i in range(1, N + 1):
        a = 0
        for j in range(len(stages)):
            if stages[j] == i:
                a += 1
        if a == 0:
            e[i] =0
        else:
            e[i] = a/f
        f = f - a
    d1 = sorted(e.items(), key=operator.itemgetter(1), reverse=True)
    d1 = dict(d1)
    d1 = list(d1.keys())
    return d1

https://github.com/developer-Park/Algorithm/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv1/42889.%E2%80%85%EC%8B%A4%ED%8C%A8%EC%9C%A8

Athletes who did not finish

Problem description
Many marathon runners have participated in the marathon. All but one runner completed the marathon.

Write a solution function to return the name of the athlete who did not complete the marathon when the array participant containing the names of the athletes who participated in the marathon and the array completion containing the names of the athletes who completed the marathon are given.

Restrictions
The number of runners participating in the marathon is between 1 and 100,000.
The length of completion is one less than the length of participant.
The participant's name must consist of at least 1 and no more than 20 lowercase letters of the alphabet.
There may be other participants with the same name.

I/O example

I/O Example Description
Example #1
"leo" is on the list of participants, but not on the list of finishers, so he couldn't finish.

Example #2
"vinko" is on the list of participants, but not on the list of finishers, so he couldn't finish.

Example #3
There are two "mislav" on the entrant list, but only one on the finisher list, so one didn't finish.

Timeout code

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

1. I tried solve the problem wihtout hash algorithm. However, Logic was okay but It could not pass the efficiency test. so I tried to make another code.

Pass code

import collections

def solution(participant, completion):
    a=collections.Counter(participant)
    b=collections.Counter(completion)
    c=a-b
    c= list(c)
    answer = ''.join(c)
    return answer

2. I used this code by collections.

'Collections'
import collections
Counter(), a function built into collections, is used to count the number of values ​​of hash-type data such as Dic.
Made in {key:value} format like Dic
Counter() objects can also be subtracted from each other
Values ​​of 0 (zero) or negative (minus) are also possible.
Returns 0, not an error, even if there is no corresponding value
import collections
lst = ['aa', 'cc', 'dd', 'aa', 'bb', 'ee']
print(collections. Counter(lst))
'''
Result
Counter({'aa': 2, 'cc': 1, 'dd': 1, 'bb': 1, 'ee': 1})
'''

set:Remove duplicates