BoBo World

[Programmers] #49191 - 순위 [Java][C++][Python]

문제 링크 1. 아이디어 일부 경기 결과만 주어졌을 때 순위를 정확히 알 수 있는 선수가 몇 명인지 세는 문제다. 선수들의 승패를 이긴 선수에서 진 선수로 가는 간선으로 보면, 실력이 좋은 선수는 항상 이기므로 A 선수가 B 선수를, B 선수가 C 선수를 이겼을 때 A 선수가 C 선수보다 실력이 좋아 직접 붙지 않았어도 A 선수가 C 선수를 ...

[Programmers] #43164 - 여행경로 [Java][C++][Python]

문제 링크 1. 아이디어 항공권을 모두 한 번씩 써서 ICN에서 출발하는 경로를 만들되, 가능한 경로가 여러 개면 알파벳순으로 가장 앞선 경로를 구하는 문제다. 공항 이름은 모두 대문자 3글자라 경로의 알파벳순 비교는 앞에서부터 한 공항씩 비교한 결과이므로, 각 공항에서 도착지가 알파벳순으로 앞선 항공권부터 써 가며 깊이 우선으로 경로를 늘리...

[Programmers] #49189 - 가장 먼 노드 [Java][C++][Python]

문제 링크 1. 아이디어 1번 노드에서 최단경로의 간선 수가 가장 많은 노드가 몇 개인지 세는 문제로, 간선에 가중치가 없으므로 1번 노드에서 BFS를 하면 노드가 처음 닿는 레벨이 곧 최단경로의 간선 수이고, 가장 먼 노드는 마지막 레벨의 노드들이므로 마지막 레벨의 크기가 답이다. 노드가 최대 20,000개라 인접 행렬은 칸이 4억 개나 되...

[LeetCode] #73 - Set Matrix Zeroes [Java][C++][Python]

문제 링크 1. 아이디어 0이 있는 칸의 행과 열을 모두 0으로 만드는 문제이다. 0을 발견하자마자 바꾸면 새로 생긴 0을 원래 있던 0과 구분할 수 없어 다른 행과 열로 번지므로, 먼저 0이 있는 행과 열을 표시해 두고 나중에 한꺼번에 바꾼다. 행마다 하나, 열마다 하나씩 표시를 두면 보조 공간은 $O(m + n)$이다. 지문의 Follo...

[LeetCode] #190 - Reverse Bits [Java][C++][Python]

문제 링크 1. 아이디어 32비트 정수의 비트 순서를 뒤집는 문제로, 입력의 가장 낮은 비트부터 하나씩 떼어 결과를 한 칸 왼쪽으로 밀고 그 자리에 붙이면 먼저 뗀 비트가 밀려 올라가 결국 가장 높은 자리에 놓여 순서가 뒤집힌다. 입력이 0이 될 때까지가 아니라 32번을 정확히 돌려야 하는데, 입력의 높은 자리가 0이면 일찍 0이 되어 멈추고...