Programmers in Berlin

뱅기타고 기차타고 드디어 베를린 도착!

베를린 가기 전 프랑크푸르트에서 본 유로타워

Thx for 민보

미친 학센.... 독일 오고나서 먹은 첫 음식인데 진짜 미쳤다
potato dumpling? 저거는 감자랑 밀가루랑 뭐 버터 섞어서 만든거 같은데 진짜 말도 안되게 맛있었다.
베를린 가시는 분들은 Zur Haxe 무조건 들리시길!! 강추 드립니다. 가격도 저렇게 하고 팁포함 60유로.

12/31 연말이 되고 오늘 무슨 페스티벌이 있다는데 형님이 티켓을 사놓았다고 한다.
가기 전에 코테 문제 몇개 풀고 갈 계획

문제 풀이

게임 맵 최단거리

from collections import deque
def solution(maps):
    n = len(maps)
    m = len(maps[0])
    visited = [[0]*m for _ in range(n)]
    visited[0][0] = 1
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    queue = deque([(0, 0)])
    while queue:
        x, y = queue.popleft()
        if x == n-1 and y == m-1:
            return visited[x][y]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m and visited[nx][ny] == 0 and maps[x][y] == 1:
                queue.append((nx, ny))
                visited[nx][ny] = visited[x][y] + 1
    return -1

< 풀이 과정 >

• BFS 이용하여 문제 해결
• 행, 열 각각 n, m으로 표기, dx, dy 상하좌우 순서로 만들고 deque에 (0, 0)으로 생성, 0의 값 갖는 행렬(visited) 만들어주기 (방문했는지 여부 판단 가능)
• queue를 돌며 x, y 뽑아서 nx, ny라는 다음 좌표 만들고 주어진 범위 내에서 이동할 경우 방문한 다음 좌표 + 1로 표기. 도착지인 (n-1, m-1)에 도착하면 현재까지 이동한 칸의 수인 visited[x][y] 리턴, 아닌 경우 -1 리턴

할인 행사

from collections import defaultdict
def solution(want, number, discount):
    answer = 0
    hash = defaultdict(int)
    for i in range(len(want)):
        hash[want[i]] = number[i]
    for i in range(len(discount)-9):
        dc_list = discount[i:i+10]
        cnt = 0
        for w in want:
            if hash[w] == dc_list.count(w):
                cnt += 1
        if cnt == len(want):
            answer += 1
    return answer

< 풀이 과정 >

• defaultdict를 사용하여 dict 자료구조를 만들어 default 키를 갖더라도 int 형태로 0의 값을 갖도록 만들어준다.
• 만들어준 hash에 want 제품을 키로, 수량인 number를 value로 dict에 저장해준다.
• 이후 10일 간의 비교를 위해서 len(discount)-9 로 for문을 돌고 dc_list로 10일 간 할인되는 제품들을 저장한다.
• hash[w] 즉 원하는 제품의 수량과 10일 간의 할인 리스트 내의 품목 수량이 일치하면 cnt += 1 진행하고 원하는 전체 품목과 그 수량이 일치하면 answer += 1로 리턴!