HackerRank: Basic Problems

HackerRank: Basic Problems

---

Solution Type

• Approximate solution
  하나의 정답만 있지 않은 문제를 말한다.
  예를 들면, Image processing이나 computer vision이 이쪽 문제에 해당 한다.

1. Array: Left Rotation

def array_left_rotation_ext(a, n, k):
    for i in range(0,k):
        # change array
        temp = a [0]
        for j in range(0,n):
            if j+1 != n:
                a[j] = a[j+1]
        a[n-1] = temp
    return a
        
def array_left_rotation(a, n, k):
    return a[k:] + a[:k]
    

n, k = map(int, input().strip().split(' '))
a = list(map(int, input().strip().split(' ')))
answer = array_left_rotation(a, n, k);
print(*answer, sep=' ')

첫 번째 함수는 시간이 너무 오래 걸려서 time-out 걸린다.

2. Strings: Making Anagrams

import string


def number_needed(a, b):
    for char in list(string.ascii_lowercase):
        al.append(a.count(char))
        bl.append(b.count(char))
    return sum(abs(x-y) for (x, y) in zip(al, bl))

a = input().strip()
b = input().strip()

al = []
bl = []

print(number_needed(a, b))

Input (stdin)

cde
abc

Your Output (stdout)

4

Expected Output

4

3. Hash Tables: Ransom Note

def ransom_note(magazine, ransom):
    d = {}
    for word in magazine:
        d.setdefault(word, 0)
        d[word] += 1
    
    for word in ransom:
        if word in d:
            d[word] -= 1
        else:
            return False
    return all([x >= 0 for x in d.values()])    

m, n = map(int, input().strip().split(' '))
magazine = input().strip().split(' ')
ransom = input().strip().split(' ')
answer = ransom_note(magazine, ransom)
if(answer):
    print("Yes")
else:
    print("No")

실행결과

6 4
give me one grand today night
give one grand today

Yes

6 5
two times three is not four
two times two is four

No

4. Linked Lists: Detect a Cycle

head point

cycle = true
no cycle = false

"""
Detect a cycle in a linked list. Note that the head pointer may be 'None' if the list is empty.

A Node is defined as: 
 
    class Node(object):
        def __init__(self, data = None, next_node = None):
            self.data = data
            self.next = next_node
"""
def has_cycle(head):
    i = 0
    if head.next == None:
        return False
    
    prev_head = head.next
    next_head = head.next
    
    while next_head != None:
        if i > 100 :
            return True      
        next_head = prev_head.next
        prev_head = next_head
        i += 1
    return False

실행 결과

0
1

5. Sorting: Bubble Sort

n = int(input().strip())
a = list(map(int, input().strip().split(' ')))

cumulatedNumSwap = 0

for i in range(0,n):
    numSwap = 0
    for j in range(0,n-1):
        if a[j] > a[j+1]:
            temp = a[j]
            a[j] = a[j+1]
            a[j+1] = temp
            numSwap += 1
    cumulatedNumSwap += numSwap
    if numSwap == 0:
        break

print("Array is sorted in %d swaps."%cumulatedNumSwap)
print("First Element: %d"%a[0])
print("Last Element: %d"%a[n-1])

In

3
3 2 1

Out

Array is sorted in 3 swaps.
First Element: 1
Last Element: 3

6. Sorting: Comparator

입력값

n // 플레이어 숫자
줄 바꾸고
공백을 두고 플레이어의 이름과 스코어

from functools import cmp_to_key

def cmp_to_key(key):
    return key

class Player:
    def __init__(self, name, score):
        self.name = name
        self.score = score
        
    def comparator(self):
        return(-self.score, self.name)

#--- reference code
n = int(input())
data = []
for i in range(n):
    name, score = input().split()
    score = int(score)
    player = Player(name, score)
    data.append(player)
    
data = sorted(data, key=cmp_to_key(Player.comparator))
for i in data:
    print(i.name, i.score)

input

5
amy 100
david 100
heraldo 50
aakansha 75
aleksa 150

output

aleksa 150
amy 100
david 100
aakansha 75
heraldo 50

7. oddNumbers (smaple test)

l과 r 사이의 숫자에서 odd number만 구해서 list로 반환

# Complete the function below.

def  oddNumbers(l, r):
    oddNumbers=[]
    i = l
    if l % 2 != 0:
        while (i <= r):
            oddNumbers.append(i)
            i+=2
    else:
        i +=1
        while (i<=r):
            oddNumbers.append(i)
            i+=2
    return oddNumbers

실행 결과

3,9
3, 5, 7, 9

8. find number (sample test)

# Complete the function below.

def  findNumber(arr, k):
    for i in arr:
        if i == int(k):
            return "YES"
        else :
            return "NO"

속도 문제가 Fail난다.

def  findNumber(arr, k):
    if k in arr :
        return "YES"
    else :
        return "NO"

속도 문제가 없다.

9. Recursion: Fibonacci Numbers

$$fibonacci(0)=0$$
$$fibonacci(1)=1$$
$$fibonacci(n)=fibonacci(n-1)+fibonacci(n-2)$$

간단한 구현 (단, timeout 걸림)

def fibonacci(n):
    # Write your code here.
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
    
n = int(input())
print(fibonacci(n))

memory 방식: python dictionary 자료구조를 이용해서 처리한다.

memory = {}
def fibonacci(n):
    if n < 2:
        return n
    if not n in memory.keys():
        memory[n] = fibonacci(n-1) + fibonacci(n-2)
    return memory[n]
    
n = int(input())
print(fibonacci(n))

one line lambda code

fibonacci = lambda n:pow(2<<n,n+1,(4<<2*n)-(2<<n)-1)%(2<<n)

10. Bit Manipulation: Lonely Integer

하나만 Unique하게 나타나고 나머진 모두 2번 나타나게 된다.

#!/bin/python3

import sys

def lonely_integer(a):
    uniqueList = [0 for i in range(101)]
    for number in a:
        uniqueList[number] += 1
    
    return uniqueList.index(1)

n = int(input().strip())
a = [int(a_temp) for a_temp in input().strip().split(' ')]
print(lonely_integer(a))

시간 복잡도 O(3n)
공간 복잡도 O(n)

실행결과

# in
1
1
# out
1

# in
9
4 9 95 93 57 4 57 93 9
# out 
95

좀 더 좋은 방법

XOR개념을 이용해서 중복되면 0가 되는 특성을 활용한다.
시간복잡도 O(n)
공간복잡도 O(1)

def lonely_integer(a):
    result = 0
    for i in a:
        result ^= i
    return result

11. Binary Search: Ice Cream Parlor

아이스크림을 사먹는 문제이다.

• t는 여행 횟수를 의미한다.
  그다음 가각에 대해서 인자가 3개이다.
• 돈
• n
• 각각의 맛에 대한 가격, i 번째가 가격을 의미한다.

t = int(input().strip())
for a0 in range(t):
    m = int(input().strip())
    n = int(input().strip())
    a = list(map(int, input().strip().split(' ')))
 
    # effective cost
    costList = {}
    for i, cost in enumerate(a):
        firUser = cost
        secUser = m - cost
        if secUser in costList.keys():
            print(costList[secUser]+1,i+1)
        else:
            costList[cost] = i

output

# input
2
4
5
1 4 5 3 2
4
4
2 2 4 3


# output
1 4
1 2

해당 문제는 딱히 Binary Search를 사용할 필요가 없다. 그냥 Hash로 사용할 경우 O(n)에 복잡도로 처리가 가능하다.
그저 과거의 cost에 각각의 index를 추가하고 그것에 현재 cost 차액만큼 값이 있는지 확인하면 된다.
ID도 점점 커지므로 딱히 순서를 고려할 필요도 없다.

참고자료
TwoSum