[Programmers] #49191 - 순위 [Java][C++][Python]
문제 링크 1. 아이디어 일부 경기 결과만 주어졌을 때 순위를 정확히 알 수 있는 선수가 몇 명인지 세는 문제다. 선수들의 승패를 이긴 선수에서 진 선수로 가는 간선으로 보면, 실력이 좋은 선수는 항상 이기므로 A 선수가 B 선수를, B 선수가 C 선수를 이겼을 때 A 선수가 C 선수보다 실력이 좋아 직접 붙지 않았어도 A 선수가 C 선수를 ...
문제 링크 1. 아이디어 일부 경기 결과만 주어졌을 때 순위를 정확히 알 수 있는 선수가 몇 명인지 세는 문제다. 선수들의 승패를 이긴 선수에서 진 선수로 가는 간선으로 보면, 실력이 좋은 선수는 항상 이기므로 A 선수가 B 선수를, B 선수가 C 선수를 이겼을 때 A 선수가 C 선수보다 실력이 좋아 직접 붙지 않았어도 A 선수가 C 선수를 ...
문제 링크 1. 아이디어 항공권을 모두 한 번씩 써서 ICN에서 출발하는 경로를 만들되, 가능한 경로가 여러 개면 알파벳순으로 가장 앞선 경로를 구하는 문제다. 공항 이름은 모두 대문자 3글자라 경로의 알파벳순 비교는 앞에서부터 한 공항씩 비교한 결과이므로, 각 공항에서 도착지가 알파벳순으로 앞선 항공권부터 써 가며 깊이 우선으로 경로를 늘리...
문제 링크 1. 아이디어 원소 중 일부를 골라 $k$개 이상씩 묶었을 때 각 묶음의 최댓값들로 이루어진 집합의 MEX를 최대로 만드는 문제다. MEX를 $x$ 이상으로 만들려면 0부터 $x - 1$까지의 모든 값 $v$마다 최댓값이 $v$인 묶음이 하나씩 필요하다. 최댓값이 $v$인 묶음은 값이 $v$인 원소를 하나 이상 포함하고 나머지는 $...
문제 링크 1. 아이디어 1번 노드에서 최단경로의 간선 수가 가장 많은 노드가 몇 개인지 세는 문제로, 간선에 가중치가 없으므로 1번 노드에서 BFS를 하면 노드가 처음 닿는 레벨이 곧 최단경로의 간선 수이고, 가장 먼 노드는 마지막 레벨의 노드들이므로 마지막 레벨의 크기가 답이다. 노드가 최대 20,000개라 인접 행렬은 칸이 4억 개나 되...
문제 링크 1. 아이디어 명령 $[i, j, k]$마다 배열의 $i$번째부터 $j$번째까지를 잘라 정렬하고 $k$번째 수를 고르면 되는 문제이다. 지문은 위치를 1부터 세므로 0부터 세는 반열린 구간으로는 $[i - 1, j)$이고 $k$번째 수는 인덱스 $k - 1$에 있다. 2. 코드 풀이 [Java][C++][Python] im...
문제 링크 1. 아이디어 논문 $n$편 중 $h$번 이상 인용된 논문이 $h$편 이상이고 나머지는 $h$번 이하 인용되는 $h$의 최댓값을 구하는 문제로, 인용 횟수를 오름차순으로 정렬하고 0부터 센 위치를 $i$라 하면 위치 $i$부터의 $n - i$편이 가장 많이 인용된 논문들이다. $h = n - i$로 두면 $h$번 이상 인용된 논문이...
문제 링크 1. 아이디어 0이 있는 칸의 행과 열을 모두 0으로 만드는 문제이다. 0을 발견하자마자 바꾸면 새로 생긴 0을 원래 있던 0과 구분할 수 없어 다른 행과 열로 번지므로, 먼저 0이 있는 행과 열을 표시해 두고 나중에 한꺼번에 바꾼다. 행마다 하나, 열마다 하나씩 표시를 두면 보조 공간은 $O(m + n)$이다. 지문의 Follo...
문제 링크 1. 아이디어 정수의 자릿수를 낮은 자리부터 하나씩 떼어 결과의 뒤에 붙이면 뒤집힌 수가 되고, 64비트 정수를 쓸 수 없으므로 범위를 벗어나는지는 붙이기 전에 확인해야 한다. 붙이면 결과가 10배가 되므로 결과가 $2^{31} - 1$을 10으로 나눈 몫 214,748,364를 넘거나(음수는 $-2^{31}$을 10으로 나눈 몫 ...
문제 링크 1. 아이디어 32비트 정수의 비트 순서를 뒤집는 문제로, 입력의 가장 낮은 비트부터 하나씩 떼어 결과를 한 칸 왼쪽으로 밀고 그 자리에 붙이면 먼저 뗀 비트가 밀려 올라가 결국 가장 높은 자리에 놓여 순서가 뒤집힌다. 입력이 0이 될 때까지가 아니라 32번을 정확히 돌려야 하는데, 입력의 높은 자리가 0이면 일찍 0이 되어 멈추고...
문제 링크 1. 아이디어 정수가 회문인지, 즉 문자열로 바꿨을 때 앞뒤로 똑같이 읽히는지 보는 문제로, 문자열을 뒤집어 원래와 같은지 비교하면 된다. 지문의 Follow-up은 문자열로 바꾸지 않고 푸는 것을 묻고, 절반 뒤집기가 그것에 맞춘 풀이이다. 수 전체를 뒤집으면 2,147,483,647이 7,463,847,412가 되듯 뒤집은 값...