Algorithm/Programmers93

• 

  [PRGRMS]42747번: H-Index 문제: https://programmers.co.kr/learn/courses/30/lessons/42747 시뮬레이션 문제입니다. 논문이 인용될 수 있는 최대 크기만큼 int[] 배열을 잡아놓은 뒤 논문 정보가 들어올 때 마다 해당 논문 인용 횟수를 ++ 해줍니다. int[] refCounts; refCounts[1] = 1번 인용된 논문의 갯수 refCounts[2] = 2번 인용된 논문의 갯수 refCounts[3] = 3번 인용된 논문의 갯수 H-Index의 최댓값을 구해야하므로 (최대 인용 횟수 ~ 최소 인용 횟수)만큼 for loop를 돌며 해당 인용 횟수가 H-Index 조건을 만족하는지 확인합니다. 만족하면 바로 break로 빠져나와서 해당 횟수를 정답으로 리턴하면 됩니다. H-Index .. Algorithm/Programmers 2022. 3. 17.

• 

  [PRGRMS]72411번: 메뉴 리뉴얼 문제: https://programmers.co.kr/learn/courses/30/lessons/72411 시뮬레이션 문제입니다. 놓치기 쉬운 조건은 아래 두 가지입니다. 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다. 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다. 예를 들어, 요리 2개 코스 후보가 AB -2번 주문, AC - 3번 주문, AD - 3번 주문 이렇게 주어진 경우 AC, AD만 정답에 포함됩니다. 그러므로 AB도 2명이상으로부터 시켰다고 정답에 포함시키면 안되겠습니다. 1. 임의의 메뉴 2개 String 선택 (두 String 중 길이가 짧은 String을 A, 길이가 긴 String을.. Algorithm/Programmers 2022. 3. 15.

• 

  [PRGRMS]49191번: 순위 문제: https://programmers.co.kr/learn/courses/30/lessons/49191 그래프 탐색 문제입니다. 순위를 알 수 있는 선수는 자신의 부모, 자식 노드에 대해 BFS를 돌렸을 때 방문하는 노드가 N-1개인 선수입니다. 그러므로 N번 전부 루프를 돌면서 하나의 선수에 대해 BFS를 돌려봅니다. N 제한이 작으므로 모든 선수에 대해 전부 BFS 탐색을 해도 O(N^2)으로 통과가 가능합니다. 코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%EC%88%9C%EC%9C%84.java Algorithm/Programmers 2022. 3. 15.

• 

  [PRGRMS]1844번: 게임 맵 최단거리 문제: https://programmers.co.kr/learn/courses/30/lessons/1844 기본 BFS문제입니다. 매 탐색마다 4방향을 탐색해서 진행할 수 있는지 체크해줍니다. 상태배열(visited)을 만들어 해당 칸을 이전에 방문한 적 있는지 표시하여 중복방문을 막습니다. 모든 칸을 방문했는데도 (n,m)에 도달하지 못했다면 갈 방법이 없는 것이므로 -1을 반환합니다. 코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%EA%B2%8C%EC%9E%84%20%EB%A7%B5%20%EC%B5%9C%EB%8B%A8%EA%B1%B0%EB%A6%AC.java Algorithm/Programmers 2022. 3. 11.

• 

  [PRGRMS]72412번: 순위 검색 문제: https://programmers.co.kr/learn/courses/30/lessons/72412 여러 해결 방법이 있지만 저는 시뮬레이션 + 이분 탐색으로 해결했습니다. 지원자의 4가지 항목에 대해 생길 수 있는 81가지(4x3x3x3)의 상태를 분기하여 리스트를 만듭니다. 그리고 지원자의 정보를 입력받을 때 마다 지원자의 정보가 조회될 수 있는 상태 리스트에 모두 지원자의 점수를 넣어습니다. 그리고 쿼리 수행전에 오름차순 정렬을 해놓습니다. 그러면 하나의 쿼리를 이분 탐색을 통해 해결할 수 있습니다. 시간 복잡도는 O(NlogM)입니다. (지원자의 수: N, 쿼리의 수 M) 코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%EC%88%.. Algorithm/Programmers 2022. 3. 10.

• 

  [PRGRMS]67257번: 수식 최대화 문제: https://programmers.co.kr/learn/courses/30/lessons/67257 시뮬레이션 문제입니다. 1. 순열을 통해 해당 연산자의 모든 우선순위쌍을 만듭니다. 2. 하나의 우선순위쌍을 기준으로 연산을 수행합니다. 연산을 수행하는 방법은 다양하지만, 제가 구현한 방식은 2개의 큐를 사용해서 우선순위가 높은 연산자를 먼저 연산하도록 했습니다. 한 가지 주의할 점은 연산을 수행하면서 최초의 식 순서가 바뀌면 안 됩니다ㅠㅠ 그러면 최종 연산 결과가 최적해와 다를 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%EC%88%98%EC%8B%9D%20%EC%B5%9C%EB%8C%80%ED%99%94.java Algorithm/Programmers 2022. 3. 10.