개발 블로그

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42747

접근 방법

문제 조건에 주어진대로 구현하면 된다.

citations중 최대값이 maxNum부터 검사를 해 나가는데, h번 이상 인용된 논문의 수인 cnt가 h편 이상이고, 나머지가(len-cnt)가 h번 이하로 인용되면 answer에 값을 저장하고 검사를 중단한다.

h의 max를 찾는 것이므로 더 작은 값은 검사할 필요가 없다.

import java.util.*;
class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        Arrays.sort(citations);
        int len = citations.length;
        int maxNum = citations[len-1];
        
        for(int i = maxNum; i>=0; i--){	//h의 max를 찾는 것이므로
            int cnt = 0;
            for(int j = 0; j<len; j++){
                if(citations[j]>=i) cnt+=1;
            }
            if(cnt>=i && (len-cnt)<=i) {
                answer = i;
                break;
            }
        }
        return answer;
    }
}

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43238?language=java# 

접근 방법

이분탐색으로 푸는 문제인데 형변환에 주의해야 한다.

처음에는 아래와 같이 우선순위 큐로 풀었는데 시간초과가 떴다.

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        int len = times.length;
        
        PriorityQueue<Long> pq = new PriorityQueue<Long>();
        
        for(int i = 0; i<len; i++){
            for(int j = 1; j<=n; j++){
                pq.add((long)times[i]*j);
            }
        }
        long cnt = 0;
        while(!pq.isEmpty()){
           cnt += 1;
            long num = pq.poll();
            //System.out.println(num);
            if(cnt==n){
                answer = num;
                break;
            }
        }
        
        return answer;
    }
}

그래서 이분 탐색으로 해결하였다.

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        
        int len = times.length;
        Arrays.sort(times);
        
        long maxi = (long) times[len-1] * n;		//여기서 형변환 안 하면 틀림.
        long answer = maxi;
        
        long left = 1;
        long right = maxi;
        while(left<=right){
            long mid = (left+right)/2;
            
            long sum = 0;					//sum 도 long 으로!
            for(int i = 0; i<len; i++){
                sum += mid/times[i];
            }

            if(sum>=n){
                if(mid < answer){
                    answer = mid;
                }
                right = mid - 1;
            } 
            else left = mid + 1;
            
        }

        return answer;
    }
}

문제 링크 : programmers.co.kr/learn/courses/30/lessons/42862#

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

접근 방법

매번 DFS를 돌 때마다 체육수업을 못 받는 학생 수를 카운트 해서 완전탐색으로 풀었다.

주의해야할 점은 제한사항 5번인데, 여분 체육복이 있고 도난당하지 않은 학생들의 번호만 vec에 넣어서 해결할 수 있었다.

처음에는  

DFS(int n, int toPick) 으로 파라미터를 하나 더 추가하고,

조건식을 하나 없애서 if(next<1 || next>n)  로 수정하고,

toPick 이 0이 될때 체육수업을 못 받는 학생 수를 카운트 하는 방식으로 했는데 이상하게 7번 테스트 케이스에서만 통과가 안 됐다. '질문하기'에서 나온 테스트케이스를 모두 넣어서 테스트 할 때는 통과 됐지만 제출하기를 누르면 통과가 되지 않았다. 

DFS 호출 전에 main 에서 이미 제한사항 5번을 처리해줬는데 어떤 부분이 문제인지 잘 모르겠다. 

//
//  DFS_프로그래머스_체육복.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/03/30.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <string>
#include <vector>

using namespace std;
vector<int> vec;
int arr[31];
int d[2] = {1, -1};
int visited[31] = {0};
int mini = 100;
void DFS(int n){

    int cnt = 0;
        for(int i = 1; i<=n; i++){
            if(arr[i]==0) cnt++;
        }
        if(cnt<mini) mini = cnt;
        
    for(int i = 0; i<vec.size(); i++){
        for(int j = 0; j<2; j++){
            int next = vec[i] + d[j];
            if(next<1 || next>n || arr[next]!=0) continue;      //범위 넘어가거나 옆사람 줄 필요 없으면
            
            if(visited[vec[i]]==0){
                visited[vec[i]] = 1;
                arr[vec[i]] -= 1;
                arr[next] += 1;
                DFS(n);
                arr[next] -= 1;
                arr[vec[i]] += 1;
                visited[vec[i]] = 0;
            }
            
        }
    }
}


int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    int cnt=0;
    for(int i = 0; i<=31; i++){
        arr[i] = 1;
    }
    for(int i = 0; i<lost.size(); i++){ arr[lost[i]] -= 1;}             //안 가져온 사람
    for(int i = 0; i<reserve.size(); i++){ arr[reserve[i]] += 1;}       //여분 가져온 사람
    
    for(int i = 1; i<=n; i++){
        if(arr[i]==2) vec.push_back(i); //여분 체육복 갖고 온 사람이 도둑 맞은 경우는 arr[i] = 1이므로 arr[i] = 2인 경우만 인덱스 push
    }
    
    DFS(n);
    answer = n-mini;

    
    return answer;
}

문제 링크 : programmers.co.kr/learn/courses/30/lessons/49191#

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

입출력 예

입출력 예 설명

2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.
5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

접근 방법

자신의 순위를 알려면, 자신을 제외한 n-1명과의 승/패 관계를 모두 알아야한다.

vecArrWin[i] 에는 승리한 사람 i를 기준으로 잡고 i에게 진 사람들을 저장했다.

vecArrLose[i]에는 패배한 사람 i를 기준으로 잡고 i를 이긴 사람들을 저장했다.

입력 예시를 표현하면 아래와 같다.

vecArrWin[]

vecArrLose[]

1부터 n까지 BFS를 돌린다.

BFS안에서는 init 노드를 기준으로 init이 이긴 사람들과 Init에게 진 사람들을 카운트한다.

검사할 때는 init 노드에서 시작해서 벡터 배열 안에 있는 노드들을 queue에 넣으면서 탐색을 진행해 나간다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <string.h>
using namespace std;

int cntArr[101] = {0};


int BFS(int init, vector<int>* vecArrWin, vector<int>* vecArrLose){
    queue<int> que;
    que.push(init);
    int cnt = 0;
    int visited[101] = {0};
    visited[init] = 1;
    while(!que.empty()){
        
        int startNode = que.front();
        que.pop();
        
        for(int i = 0; i<vecArrWin[startNode].size(); i++){	//i가 승리자 -> i에게 진 사람들 카운트
            if(visited[vecArrWin[startNode][i]] == 0){
                visited[vecArrWin[startNode][i]] = 1;
                que.push(vecArrWin[startNode][i]);
                cnt++;
            }
        }
    }
    memset(visited, 0, sizeof(visited));
    que.push(init);
    visited[init] = 1;
    while(!que.empty()){
        int startNode = que.front();
        que.pop();
        
        for(int i = 0; i<vecArrLose[startNode].size(); i++){ //i가 패배자 -> i가 이긴 사람들 카운트
            if(visited[vecArrLose[startNode][i]] == 0){
                visited[vecArrLose[startNode][i]] = 1;
                que.push(vecArrLose[startNode][i]);
                cnt++;
            }
        }
    }
    cout << endl;
    return cnt;
    
}



int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    vector<int> vecArrWin[101];
    vector<int> vecArrLose[101];
    
    int winner, loser;
    for(int i = 0; i<results.size(); i++){
        winner = results[i][0];
        loser = results[i][1];
        
        vecArrWin[winner].push_back(loser);
        vecArrLose[loser].push_back(winner);
    }
    for(int i = 1; i<=n; i++){
        if(n-1 == BFS(i, vecArrWin, vecArrLose)){		//자신을 제외한 n-1명과 승/패 관계 알아야 함
            answer++;
        }
    }
    return answer;
}

문제 링크 : programmers.co.kr/learn/courses/30/lessons/49189

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

접근 방법

벡터 배열을 이용해서 양방향으로 연결된 노드들간의 관계를 표현했다. 그 후 BFS로 depth를 1씩 증가시켜나갔다. 

while문 안에서 depth가 answer과 같으면 cnt를 증가시켰으며 depth가 바뀌면 answer를 바뀐 depth로 초기화시키고 cnt도 다시 1로 초기화 시켜서 가장 먼 노드들의 개수를 구할 수 있었다.

#include <string>
#include <vector>
#include <queue>
#include <utility>

using namespace std;
int visited[20001] = {0};

queue<pair<int,int>> que;
int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    vector<int> vecArr[50000];					//벡터 배열
    
    int v1, v2;
    for(int i = 0; i<edge.size(); i++){			//양방향 엣지 연결
        v1 = edge[i][0];
        v2 = edge[i][1];
        vecArr[v1].push_back(v2);
        vecArr[v2].push_back(v1);
    }
    visited[1] = 1;
    que.push(make_pair(1,0));
    int cnt = 0;
    
    while(!que.empty()){
        
        pair<int,int> p = que.front();
        if(answer == p.second) cnt++;		//가장 먼 노드들의 개수 몇개인지 카운트
        else{								//depth 증가해서 바뀌면 값 재설정
            answer = p.second;
            cnt = 1;
        }
        que.pop();
        vector<int> vec = vecArr[p.first];
        for(int i = 0; i<vec.size(); i++){
            if(visited[vec[i]]==0){
                visited[vec[i]] = 1;
                que.push(make_pair(vec[i], p.second+1));
            }
        }
        
    }
    answer = cnt;
    
    return answer;
}

문제 링크 : programmers.co.kr/learn/courses/30/lessons/43164

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
• 주어진 공항 수는 3개 이상 10,000개 이하입니다.
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
• 주어진 항공권은 모두 사용해야 합니다.
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
• 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.

입출력 예

입출력 예 설명

예제 #1

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

접근 방법

테스트 케이스 중 3,4번만 맞았다면 그래프 연결이 끊긴 경우를 생각하지 않았을 것이다.  즉, 입력이 1,2 / 1,3 / 3,1 이라면 1->2까지만 탐색하고 종료해버리는 것이다.

이것을 DFS의 리턴 bool 값을 이용해서 처리해줘야 한다. 탐색을 하다가 끊겼을 경우엔 false 를 리턴해서 가장 뒤의 요소를 pop 하고 다시 탐색을 시작해서 1->2 가 아닌 1->3이 되도록 해준다. 제한사항인 "주어진 항공권은 모두 사용해야 합니다" 를 만족하면 DFS함수를 리턴 시킨다. 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>

using namespace std;

int visited[10000] = {0};

vector<string> res;

bool DFS(string start, vector<vector<string>> tickets, int chkcnt){
 
    if(chkcnt==tickets.size()) return true;		//1-1) 탐색 다 끝나면 true 리턴해서
   
   for(int i = 0; i<tickets.size(); i++){
       if(visited[i]==0 && start == tickets[i][0]){
           visited[i] = 1;
           res.push_back(tickets[i][1]);
           bool resbool = DFS(tickets[i][1], tickets, chkcnt+1);	
           if(resbool) return true;				//1-2) 더 이상 아래로 내려가지 않고 차례로 빠져나옴 
           
           visited[i] = 0;						//2-2) false 리턴됐으면 이 라인으로 내려오게 됨
       }
   }
    res.pop_back();	//길 끊겨서 항공권 다 탐색해도 이을게 없으면 마지막에 연결된 곳 pop
    return false;	//2-1) false 리턴해서 길 끊겼음을 알림
}


vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    sort(tickets.begin(), tickets.end());

    string start = "ICN";
    res.push_back(start);

    DFS(start, tickets, 0);
    answer = res;
       
    return answer;
}

참고 : yabmoons.tistory.com/528