내일은 알고리즘

https://school.programmers.co.kr/learn/courses/30/lessons/77486

기본적인 DFS로 구현이 가능한 문제입니다.

입력에 따라 판매원들의 이름을 Dictionary에 저장해서 Index화 해줍니다. 

이후 판매원들의 referral을 입력받아 자신을 초대한 사원을 가리키게 해주면 위로만 타고 올라가지는 그래프 형태의 구조가 됩니다.

이제 매출이 발생한 입력마다 위로 타고 올라가며 상납금(?)을 더해주면 됩니다.

11~13번에서 런타임 에러가 발생한다면 해당 테스트케이스의 사원들의 초대 형태가 일렬로 길게 이어진 모양이라 타고 올라가다가 스택 오버플로우가 발생한 것입니다.

종료조건이 제대로 잡히지 않았을때 자주 발생하는 에러인데, 생각해 보면 판매에서 얻어지는 이익의 최댓값은 10000입니다. (칫솔 하나의 이익이 100원, 판매수의 최대가 100)

상납금은 10%씩을 납부하는데, 가장 큰 이익이 발생해도 몇 단계만 올라가면 상납금은 0원이 됩니다.

10000 (매출 발생) -> 1000원 상납 -> 100원 상납 -> 10원 상납 -> 1원 상납 -> 0원 상납 (판매자의 5단계 위는 돈을 얻을 수 없다!)

따라서 상납금이 0원이 되는 경우 다음 호출을 하지 않도록 탈출 조건을 잡아주면 됩니다.

if lead == -1 or tax == 0: (돈을 보낼 초대자가 존재하지 않거나, 보낼 돈이 0원일시 더 이상 호출하지 않음)

def solution(enroll, referral, seller, amount):
    result = [0 for i in range(len(enroll))]
    follow = [-1 for i in range(len(enroll))]
    name_dict = {}

    index = 0
    for name in enroll:
        name_dict[name] = index
        index += 1

    for i in range(len(referral)):
        if referral[i] != '-':
            target = name_dict[referral[i]]
            follow[i] = target

    for i in range(len(seller)):
        start = name_dict[seller[i]]
        money = amount[i] * 100
        send_money(follow, result, money, start)

    return result


def send_money(follow, result, money, me):
    lead = follow[me]
    tax = int(money / 10)
    result[me] += money - tax

    if lead == -1 or tax == 0:
        return
    else:
        send_money(follow, result, tax, lead)

https://school.programmers.co.kr/learn/courses/30/lessons/1845

해쉬의 연습문제로 등록되어 있지만, Key값으로 쓸 이름이 숫자형태여서 그냥 boolean 배열로 관리해도 충분히 풀이할 수 있습니다.

폰켓몬을 가져갈수 있는 최대값(N/2)범위 이내에서 겹치지 않게 카운팅을 해주면 됩니다.

boolean 배열과 Dictionary 두가지 형태로 작성했습니다.

def solution(nums):
    answer = 0
    count = len(nums) // 2
    picked = [False for i in range(200_001)]
    
    index = 0
    while answer < count and index < len(nums):
        if not picked[nums[index]]:
            picked[nums[index]] = True
            answer += 1
            
        index += 1
    
    return answer


//딕셔너리 사용
def solution_with_dict(nums):
    answer = 0
    count = len(nums) // 2
    picked = {}
    
    index = 0
    while answer < count and index < len(nums):
        if not nums[index] in picked:
            picked[nums[index]] = 1
            answer += 1
        index += 1
    
    return answer

https://leetcode.com/problems/isomorphic-strings/

상당히 낯선 단어인데 Isomorphic은 동형사상이라는 뜻이라고 합니다.

Isomorphic String은 두 String의 형태가 닮아있는 것을 말하는데요. 예를 들어 glass와 shell이 동형관계입니다.

두 단어는 생김새가 전혀 다르지만 알파벳이 등장하는 순서대로 번호를 매기면 12344, 12344로 구조가 같음을 알 수 있습니다.

반대로 banana와 canada는 단어 생긴건 비슷하지만 번호를 매기면 123232와 123242로 차이가 있습니다.

문제에서 주어진 String을 앞에서부터 읽어가며 처음 만나는 알파벳인 경우 Dictionary에 Index값을 넣어주고, 이미 만났던 알파벳인 경우 Index값을 비교해 같은 구조인지 체크해줬습니다.

물론 알파벳의 내용은 다르므로 Dictionary를 두개 만들어서 따로 저장했습니다.

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        sDict = {}
        tDict = {}
        idx = 0

        for i in range(0,len(s)):
            if(not (s[i] in sDict) and not (t[i] in tDict)):
                sDict[s[i]] = idx
                tDict[t[i]] = idx
                idx += 1
            elif(s[i] in sDict and t[i] in tDict):
                if(sDict[s[i]] != tDict[t[i]]):
                    return False
            else: 
                return False
        
        return True

input = [["egg","add"],["foo","bar"],["paper","title"]]

for i in input:
    print(Solution().isIsomorphic(i[0],i[1]))

https://leetcode.com/problems/roman-to-integer/

최근에 추천받았던 LeetCode라는 외국 PS사이트입니다.

디자인도 예쁘고 개인이 사용한 자료구조, 알고리즘 통계나 문제 풀이 코스같이 특정 기간동안 스케쥴 관리 해주는 기능이 참 좋아보이네요.

LeetCode는 Easy - Medium - Hard 3단계로 문제의 난이도가 구분되어 있습니다. 회원가입하자마자 문제 리스트를 추천받았는데 가장 위에 있던 문제입니다. 

문제 자체는 문자열을 조건에 맞추어 숫자로 변환하기만 하면 되는데요, if문을 중첩하거나 switch-case를 쓰거나 여러가지 방법이 있을겁니다.

Python의 Dictionary를 이용해서 두가지 방법으로 풀었는데요.

첫 코드는 if문을 여러개 쪼개서 조건을 구분한 코드인데 통과는 되었지만 코드라인도 길고 깔끔하지 않아서 Dictionary를 좀 더 사용하는 코드로 다시 작성했습니다.

class Solution(object):
    def romanToInt(self, s: str) -> int:
        sum = 0
        i = 0
        symbol = {'I': 1, 'V': 5,'X': 10,'L': 50,'C': 100,'D': 500,'M': 1000}

        while(i < len(s)):
            if( i < len(s) - 1) :
                if(s[i] == 'I'):
                    if(s[i+1] == 'V'):
                        sum += 4
                        i += 1
                    elif(s[i+1] == 'X'):
                        sum += 9
                        i += 1
                    else : 
                        sum += symbol[s[i]]
                elif(s[i] == 'X'):
                    if(s[i+1] == 'L'):
                        sum += 40
                        i += 1
                    elif(s[i+1] == 'C'):
                        sum += 90
                        i += 1
                    else : 
                        sum += symbol[s[i]]
                elif(s[i] == 'C'):
                    if(s[i+1] == 'D'):
                        sum += 400
                        i += 1
                    elif(s[i+1] == 'M'):
                        sum += 900
                        i += 1
                    else : 
                        sum += symbol[s[i]]
                else : 
                    sum += symbol[s[i]]
            else:
                sum += symbol[s[i]]
            i += 1
        return sum


input = ["III","LVIII","MCMXCIV"]

for i in input:
    print(Solution().romanToInt(i))

# Solution().romanToInt(input[2])

class Solution(object):
    def romanToInt(self, s: str) -> int:
        symbolValue = {'I': 1, 'IV':4, 'V': 5, 'IX':9, 'X': 10, 'XL':40, 'L': 50, 'XC':90, 'C': 100, 'CD': 400, 'D': 500, 'CM': 900, 'M': 1000}
        sum = 0
        i = 0

        while(self.indexInString(i, s)):
            if(self.indexInString(i+1, s) and s[i: i+2] in symbolValue):
                sum += symbolValue[s[i: i+2]]
                i += 2
            else:
                sum += symbolValue[s[i]]
                i += 1
        return sum

    def indexInString(self, i: int, s:str)-> bool:
        return i < len(s)



input = ["III","LVIII","MCMXCIV"]

for i in input:
    print(Solution().romanToInt(i))

# Solution().romanToInt(input[2])

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

참가자와 완주자 사이에 맞지 않는 한 명을 찾는 문제입니다.

HashMap (파이썬의 Dictionary)자료구조를 사용해 풀이했습니다.

문제를 처음 보면 참가자들을 저장하고, 완주자들을 제외 한 뒤 남은 한 명을 구하는 식으로 구현해야할것 같습니다.

하지만 가만히 생각해보면 완주자들을 저장한 뒤 참가자들을 순회하면서 완주자 목록에 없는 사람을 찾는 역순으로 구현하는게 더 간단합니다. 

완주자들의 이름을 key로 Dictionary에 넣어 존재하지 않는다면 value를 1로 저장하고 동명이인이 있다면 value+1로 갱신해줍니다.

이후 참가자들의 이름을 완주자를 저장한 Dictionary에서 확인하면서 하나씩 지워주다가 존재하지 않는 이름이나 완주 목록이 이미 0이 된 이름이 나오면 그 참가자가 우리가 찾는 답이 됩니다.

def solution(participant, completion):
    map = {}

    for i in completion :
        if(i in map):
            map[i] = map.get(i) + 1
        else : 
            map[i] = 1

    for i in participant:
        if(i in map and map[i] > 0):
            map[i] = map.get(i) - 1
        else : 
            return i


participant = [["leo", "kiki", "eden"], ["marina", "josipa", "nikola", "vinko", "filipa"], ["mislav", "stanko", "mislav", "ana"]]
completion = [["eden", "kiki"], ["josipa", "filipa", "marina", "nikola"], ["stanko", "ana", "mislav"]]

for i in range(0,3):
    print(solution(participant[i], completion[i]))