아침-코테-스터디-4주차

4주차

• Day22 | 네트워크 #138
• Day23 | 베스트앨범 #146
  ~~- Day24 | 다리를 지나는 트럭 #153, 피로도 #154
• Day25 | 주식가격 #155, 전력망을 둘로 나누기 #156
  ~~
• Day26 | 단속카메라 #146
• Day 27 | 여행경로 #171 ,아이템줍기 #170
  단속카메라 #169

네트워크

// x를 갈 수 있다는 걸 알고 방문한 상태
static void dfs(int start){                   // -> 모든 정점이 x로 한번씩만 O(V) 
		// x 방문
		visit[start] = true;
		
		// x에서 갈 수 있는 곳들을 모두 방문
		for(int i : start에서 갈 수 있는 점 들){       // -> 인접행렬 O(V) || 인접리스트 O(deg(x))
				if(visit[i])     // visit[y]가 true면 이 y는 무시
					continue;

				// 아직 안가본 y라면 가보자
				dfs(i);
		}
}

• dfs로 접근해야하는 이유
  • 컴퓨터개수와 연결정보가 주어진다.
  • 연결정보로. 같은 네트워크 안에 있는지 확인해야한다.
  • dfs를 이용해 인접한 노드를 방문한다. dfs로 연결된 노드를 모두 방문하고 나면 answer+1해준다.
  • 단순 그래프 탐색.

def main():
    print(solution(3,[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	))

def solution(n, computers):
    answer = 0
    visited = [False for i in range(n)]
    for start in range(n):
        if visited[start] == False:
            dfs(n,computers,start,visited)
            answer += 1
    return answer

def dfs(n,computers,start,visited):
    visited[start] = True
    for i in range(n):
        if(visited[i] == False and computers[start][i] == 1):
            visited = dfs(n,computers,i,visited)
    return visited

    
if __name__ == "__main__":
    main()

💡 if(visited[i] == False and computers[start][i] == 1): visited = dfs(n,computers,i,visited)

베스트앨범

1. zip(index,genres,plays) 실패

   zip으로 엮어도, 장르별 해쉬 테이블 필요.

   index = [ i for i in range(len(genres))]

2. 전체 재생횟수의 1,2위의 장르의 1등,2등 index

   total, genre 2개의 딕셔너리 필요

def main():
    print(solution(["classic", "pop", "classic", "classic", "pop"],[500, 600, 150, 800, 2500]))

def solution(genres, plays):
    answer = []

    total={}
    genre={}
    
    for i in range(len(genres)):
        if genres[i] in total:
            total[genres[i]] += plays[i]
        else:
            total[genres[i]] = plays[i]
        if genres[i] in genre:
            genre[genres[i]].append([plays[i],i])
        else:
            genre[genres[i]] = [[plays[i],i]]
    
    sort_total = sorted(total,reverse=True)

    for x in sort_total:
        sort_genre = sorted(genre[x],key=lambda x: (-x[0],x[1])) #내림차순, 오름차순

        if len(sort_genre) == 1: # 1개일 경우
            answer.append(sort_genre[0][1])
        else:
            for i in range(2): # 2개일 경우 
                answer.append(sort_genre[i][1])
    
    return answer
    
if __name__ == "__main__":
    main()

lamda

def hap(x,y):
	return x + y
hap(10,20)

(lamda(x,y):x+y)(10,20)

# 첫번째 인자를 기준으로 내림차순, 두번째 인자를 기준으로 오름차순
newarr = sorted(arr,key=lambda x: (-x[0],x[1])))

단속카메라

고속도로에서 빠져나가는 시점에 포인트를 두어야한다.

가장 먼저 나가는 차를 찾아야 첫번째 카메라 위치를 찾을 수 있다.

이후 해당하지 않는 차들은 확인해주면서 추가해주면 된다.

def main():
    print(solution([[-20,-15], [-14,-5], [-18,-13], [-5,-3]]))

def solution(routes):
    answer = 0
    routes.sort(key=lambda x : x[1])
    camera=[routes[0][1]]
    for i in range(1,len(routes)):
        if routes[i][0] <= camera[-1] and routes[i][1] >= camera[-1]:
            continue
        else:
            camera.append(routes[i][1])
    return len(camera)

    
if __name__ == "__main__":
    main()

1. routes.sort(key=lambda x : x[1]) 빠져나가는거 기준으로 정렬.
2. 가장 나중에 빠져나가는 [routes[0][1]] 를 camera에 append.
3. camera list 기준으로 충족하지 못하는 것들 append

여행경로

import collections
answer = []
graph = collections.defaultdict(list)
visited = collections.defaultdict(list)

def main():
    print(solution([["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]))

def dfs(s, cnt, list, l):
    if cnt == l:
        answer.append(list)
        return

    for a in range(len(graph[s])):
        if visited[s][a] == 0:
            visited[s][a] = 1
            dfs(graph[s][a], cnt+1, list+[graph[s][a]], l)
            visited[s][a] = 0

def solution(tickets):
    
    for a,b in tickets:
        graph[a].append(b)
        visited[a].append(0)
    for a, b in graph.items():
        graph[a].sort() ## sort

    dfs("ICN",0, ["ICN"], len(tickets))

    return answer[:][0]

if __name__ == "__main__":
    main()

1. graph list 에 append
2. visited = 0 이면 dfs 방문
3. cnt == len(tickets) 이면 재귀 종료

아이템줍기

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0

    field = [[-1] * 102 for i in range(102)]
    
    for r in rectangle:
        x1, y1, x2, y2 = map(lambda x: x*2, r) # 모든 좌표값 2배
        for i in range(x1, x2+1):
            for j in range(y1, y2+1):
                # 직사각형 내부
                if x1 < i < x2 and y1 < j < y2:
                    field[i][j] = 0
                # 직사각형의 테두리
                elif field[i][j] != 0:
                    field[i][j] = 1
                    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    q = deque()
    q.append([characterX * 2, characterY * 2])

    visited = [[1] * 102 for i in range(102)]

    visited[characterX * 2][characterY * 2] = 0 
    
    while q:
        x, y = q.popleft()
        
        # 도착
        if x == itemX * 2 and y == itemY * 2:
            answer = visited[x][y] // 2
            break
        
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            
            # 현재 좌표가 테두리이고 아직 방문하지 않은 곳이라면 q에 추가 후 visited를 최단거리로 갱신
            if field[nx][ny] == 1 and visited[nx][ny] == 1:
                q.append([nx, ny])
                visited[nx][ny] = visited[x][y] + 1
    
    return answer

1. ㄷ을 ㅁ으로 인식하기에, 모든 값을 2배 해준다.

   map(lambda x: x*2, r)

2. 테두리 안이면 field 0, 테두리이면 field 1

3. dx,dy 이용하여 주변 노드 탐색. 방문 횟수 visited에 저장.

4. 결과값은 //2 해야함.

모음사전

def solution(word):
    answer = 0
    arr = ['A', 'E', 'I', 'O', 'U']
    num = [781, 156, 31, 6, 1]
    for i in range(len(word)):
        answer += arr.index(word[i]) * num[i] + 1
    return answer

AAAA와 AAAE의 차이는 1*5 + 1 = 6
AAA와 AAE의 차이는 6*5 + 1 = 31.
AA와 AE의 차이는 31*5 + 1 = 156.
A와 E의 차이는 156*5 + 1 = 781.

• AAAA와 AAAE의 차이 1*5 + 1 = 6 AAAA AAAAA,AAAAE,AAAAI,AAAAO,AAAAU(5) AAAE AAAEA,AAAEI,,
  
• AAA와 AAE의 차이 6*5 + 1 = 31. **AAA** : AAAA : AAAE,AAAI,AAAO,AAAU/AAEA,AAEE,AAEI,AAEO,AAEU .. AAAAA,AAAAE,AAAAI,AAAAO,AAAAU(5) AAE AAI,AAO,AAU
  
• AA와 AE의 차이는 31*5 + 1 = 156 …….