내일은 알고리즘

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

슬라이딩 윈도우(혹은 투포인터), 맵 자료구조의 개념을 알면 쉽게 풀 수 있는 문제입니다.

가입한 날로부터 10일간 할인을 받을 수 있는 것을 이용해 1~10일동안 살 수 있는 품목을 카운팅합니다.

만약 2~11일 동안 살 수 있는 품목이 궁금하다면, 10일간을 전부 찾을게 아니라 카운팅한 값에서 1일의 할인상품을 빼주고,  11일의 할인상품을 더해주면 됩니다.

우리가 원하는 상품목록이 있기 때문에 그 상품들만 찾아주면 되고 카운팅과 범위 처리는 예외가 나지 않도록 적당히 잘 해주면 됩니다. (설명이 좀 그런데 정말 적당히 잘 하면 됩니다. ㅋㅋ;;)

def solution(want, number, discount) -> int:
    answer = 0
    product = {}
    idx = 0

    for w in want:
        product[w] = idx
        idx += 1

    for i in range(10):
        if discount[i] in product:
            number[product[discount[i]]] -= 1

    for i in range(len(discount)):
        if checklist(number):
            answer += 1

        if discount[i] in product:
            number[product[discount[i]]] += 1
        
        if i + 10 < len(discount) and discount[i + 10] in product:
            number[product[discount[i + 10]]] -= 1

    return answer


def checklist(number) -> bool:
    for n in number:
        if n > 0:
            return False
    return True

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]))