개발자 김수진

[풀이]

단순 구현 문제로 문제 조건만 잘 맞추고 문자열을 잘 다뤄주면 된다.

나는 우선 시간들을 convertTime 함수를 통해 int형으로 바꿔놓고 시작했다.

시간 string을 읽어와 분/초를 분리한뒤 {60*분 + 초}를 사용해 int형으로 계산했다.

이를 기반으로 commands의 작업들으 수행했는데 

1. check_opening을 통해 현재 시간이 opening 구간에 존재하는지 판단

2. prev, next 인지에 따라 시간 계산하도록 구현했다.

위의 과정을 반복하며 현재 시간을 계산한 뒤 

convertTimeToString 함수를 통해 현재 시간을 다시 mm:ss 타입의 String으로 변환하도록 하였다.

String.format 함수를 사용하여 문자열의 형식을 지정해줬다.

[코드]

class Solution {
    static int cur_pos;

    public String solution(String video_len, String pos, String op_start, String op_end, String[] commands) {
        int video_len_int = convertTime(video_len);
        int op_start_int = convertTime(op_start);
        int op_end_int = convertTime(op_end);
        cur_pos = convertTime(pos);
        
        for (String command : commands) {
            check_opening(op_start_int, op_end_int);
            if(command.equals("prev"))  move_prev();
            else move_next(video_len_int);
        }
        check_opening(op_start_int, op_end_int);
        return convertTimeToString();
    }
    
    public static void move_prev() {
        if(cur_pos - 10 <= 0)   cur_pos = 0;
        else    cur_pos -= 10;
    }
    
    public static void move_next(int end_time) {
        if(cur_pos + 10 >= end_time)   cur_pos = end_time;
        else    cur_pos += 10;
    }
    
    public static int convertTime(String time) {
        String[] parts = time.split(":");

        int min = Integer.parseInt(parts[0]); // 분
        int sec = Integer.parseInt(parts[1]); // 초
        return 60 * min + sec;
    }
    
    public void check_opening(int op_start, int op_end) {
        if(op_start <= cur_pos && op_end >= cur_pos){
            cur_pos = op_end;
        }
        return;
    }
    
	// mm:ss 형식의 문자열로 변환
    public static String convertTimeToString() {
        int minutes = cur_pos / 60;
        int seconds = cur_pos % 60;

        String formattedTime = String.format("%02d:%02d", minutes, seconds);
        return formattedTime;
    }
}

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/340213

재귀 문제로 유명한 하노이의 탑

나무위키에 등록될 정도이다.

https://school.programmers.co.kr/learn/courses/30/lessons/12946?language=java

알고보니 굉장히 간단한 문제였다.

시작점을 a , 경유지를 b, 목적지를 c라고 하면

원판을 목적지까지 다 옮기기 위해서는 결국 



1. a  지점에서 제일 아래에 존재하는 가장 큰 원반을 제외한 원반들은 b 옮겨져야 한다.

2. 그리고 가장 큰 원반을 c로 옮기고

 3. b에 존재하는 원반들을 a 지점을 경유지로 두고 c로 옮겨야 한다.

1,2,3의 과정을 모두 수행하는 곳이 move 함수가 되는 것이다.

이걸 move 함수로 보면 a가 start, b가 tmp, c가 end가 된다.

import java.util.*;
class Solution {
    private static List<int[]> arr = new ArrayList<>();

    public int[][] solution(int n) {
        move(1,2,3,n);
        int[][] answer = arr.stream()
                .toArray(int[][]::new);

        return answer;
    }
    
    private static void move(int start, int tmp, int end, int cnt) {
         if(cnt == 0) {
             return;
         }
        move(start, end, tmp, cnt-1);
        arr.add(new int[]{start,end});
        move(tmp, start, end, cnt-1);
    }
}

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/17677

[풀이]

input string에 대해 두 글자씩 끊어서 다중 집합을 만들고 두 집합 간의 교집합/합집합 * 65536을 구해서 return 해주면 되는 문제

첫 번째로 각 input string에 대해 모두 lower case로 변환해주었다.

다음으로 연속된 두 글자가 알파벳인 경우 vector에 push 해주었다.

이중 for문을 통해 교집합을 구하고 교집합의 중복을 막기 위해 한번 확인한 글자는 #로 변환해주었다.

[코드]

#include <string>
#include <cmath>
#include <vector>
using namespace std;

bool isChar(char ch){
    if(ch>='a' && ch<='z')  return true;
    if(ch>='A' && ch<='Z')  return true;
    return false;
}

int solution(string str1, string str2) {
    int answer = 0;
    string tmp1="";
    string tmp2="";
    
    for(int i=0;i<str1.size();i++){
        str1[i]=tolower(str1[i]);
    }
    for(int i=0;i<str2.size();i++){
        str2[i]=tolower(str2[i]);
    }
    
    vector<string> p1;
    vector<string> p2;
    for(int i=0;i<str1.size()-1;i++){
        if(isChar(str1[i]) && isChar(str1[i+1]))
            p1.push_back(str1.substr(i,2));
    }    
    for(int i=0;i<str2.size()-1;i++){
        if(isChar(str2[i]) && isChar(str2[i+1]))
            p2.push_back(str2.substr(i,2));
    }
    
    int intersection=0; //교집합
    int _union= p1.size()+ p2.size(); //합집합
    
    for(int i=0;i<p1.size();i++){
        for(int j=0;j<p2.size();j++){
            if(p1[i]==p2[j]){
                intersection++;
                p2[j]="#";
                break;
            } 
        }
    }
    _union-=intersection;
    if(_union == 0)    return 65536;
    answer = intersection * 65536 /_union;
    return answer;
}

문제

https://school.programmers.co.kr/learn/courses/30/lessons/118666?language=cpp

풀이

검사자의 선택지 사이즈만큼 반복하여 결과를 구한다.

map을 사용하여 각 유형의 점수를 관리하였다.

이와 같이 점수를 다 구하여 각 지표별 성격 유형을 구한다.

코드

#include <string>
#include <vector>
#include <map>

using namespace std;

int score[8] = {0,3,2,1,0,1,2,3};


string solution(vector<string> survey, vector<int> choices) {
    string answer = "";
    map <char, int> m;
    for( int i=0;i<survey.size();i++) {
        string sur= survey[i];
        int ans= choices[i];

        m[sur[ans/4]] += score[ans];
    }
    
    answer += m['R'] >= m['T'] ? "R" : "T";
    answer += m['C'] >= m['F'] ? "C" : "F";
    answer += m['J'] >= m['M'] ? "J" : "M";
    answer += m['A'] >= m['N'] ? "A" : "N";

    return answer;
}

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/12978

[풀이]

해당 문제는 하나의 정점에서 다른 정점들까지의 최단거리를 구하는 문제이므로 다익스트라 알고리즘을 사용해 풀었다.

map이라는 벡터 배열을 선언하여 각 정점마다 인접한 정점까지의 거리를 가지고 있도로 했다.

또한 1번 정점부터 다른 정점들까지의 거리를 구하기 저장하기 위해 dist 변수를 선언하고 정점의 개수만큼 1e9로 초

기화했다.

다음으로 dijkstra 함수에서는 priority_queue를 사용해 1번 정점에서 다른 정점들까지의 최단거리를 구하도록 했다.

priority_queue는 {1번 정점에서 해당 정점까지의 최단 거리, 정점}을 pair로 가지도록 되어있고 시작점은 1번 정점이므로 먼저 {0,1}을 queue에 push 해줬다. 

다음으로 queue에서 top에 있는 정점을 뽑아 해당 정점과 인접한 정점들은 방문하고 해당 정점까지의 최단거리를 update 해주면 queue에 push 해준다. 이 때 queue는 거리를 기준으로 오름차순하여 정렬하기 때문에 최단거리를 구할 수 있다. 이러한 방식으로 queue가 empty가 아닐 때까지 반복하여 1번 정점으로부터 각 정점까지의 최단거리를 구하게 된다.

마지막으로 각 정점까지의 최단거리가 저장된 dist 배열에서 배달 가능 시간이 K보다 작거나 같은 정점들의 개수를 count 하여 return 해주면 된다. 

[코드]

#include <iostream>
#include <vector>
#include <queue>
#define MAX 51

using namespace std;

vector<int> dist;
vector<pair<int,int>> map[MAX];

void dijkstra()
{
    priority_queue< pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
    pq.push({0,1});
    dist[1] = 0;
    while(!pq.empty()) {
        int cost = pq.top().first;
        int from = pq.top().second;
        pq.pop();
        for(int i =0 ; i< map[from].size(); i++) {
            int to = map[from][i].first;
            int distance = map[from][i].second + cost;
            if (dist[to] > distance){
                dist[to] = distance;
                pq.push({distance, to});
            }
        }
    }
}

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;

    for(int i=0;i<road.size();i++){
        int start = road[i][0];
        int end = road[i][1];
        int cost = road[i][2];
        
        map[start].push_back({end,cost});
        map[end].push_back({start,cost});
        
    }
    
    dist.resize(N+1,1e9);
    dijkstra();
    for(int i=1;i<=N;i++){
        if ( dist[i] <= K)  answer++;
    }
    
    return answer;
}

[문제]

https://programmers.co.kr/learn/courses/30/lessons/17680

[풀이]

LRU 알고리즘으로 캐시를 관리하며, 캐시에서 읽어올 경우 +1, 캐시에 존재하지 않는 데이터일 경우 +5를 추가하여 총 실행시간을 구하는 문제이다. 

LRU란 Least Recently Used로 새로운 데이터가 들어올 경우, 가장 오랫동안 참고하지 않은 데이터를 빼고 새로운 데이터를 삽입하는 방식이다.

따라서 각 데이터에 대해 이미 캐시에 데이터가 존재하는지 확인 후 , 존재하지 않는다면 캐시에 삽입하고 +5를 해준다.

존재할 경우 가장 최신에 조회한 데이터이므로 벡터의 맨 뒤로 넣어주고 +1을 하여 총 실행시간을 구할 수 있다.

[코드]

#include <string>
#include <algorithm>
#include <vector>

using namespace std;

vector <string> v;

string solve(string tmp)
{
    string res = "";
    for(int i=0;i<tmp.size();i++){
        if(tmp[i] >= 97 && tmp[i] <= 122)   res += (tmp[i] - 32);
        else res += tmp[i];
    }
    return res;
}

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    for(int i=0;i<cities.size();i++){
        string city = solve(cities[i]);
        if(cacheSize == 0) {
            answer+=5;
            continue;
        }
        auto itr = find(v.begin(),v.end(), city);
        if( itr != v.end()) {
            answer += 1;
            v.erase(itr);
        }  
        else{
            if(v.size() == cacheSize){
                v.erase(v.begin());
            }
            answer += 5;
        }
        v.push_back(city);
    }
    return answer;
}

[문제]

https://programmers.co.kr/learn/courses/30/lessons/72411

[풀이]

우선 존재하는 모든 메뉴를 c라는 벡터에 insert 해준다.

결과값은 각 알파벳을 기준으로 오름차순으로 정렬되어 있어야 하므로 c를 오름차순으로 정렬해준다.

그 다음으로 course의 케이스마다 만들 수 있는 모든 메뉴 조합을 DFS 함수를 통해서 구한다.

course  배열의 각 개수를 만족하면 각 손님이 해당 메뉴 조합을 시킨 횟수를 count하고 가장 많이 시킨 메뉴 조합을 result를 위한 벡터인 v에 insert한다.

이러한 방식으로 각 course 케이스에 대한 메뉴 조합을 구하고, 가장 많이 시킨 순서대로 정렬하여 return 하면 된다 .

[코드]

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> order;
vector<char> c;
vector <pair<int , string>> v;
vector <int> comb;
int num=0;

bool comp(const pair<int,string> a, const pair<int,string> b)
{
    if(a.first>b.first) return true;
    else return false;
}

int solve()
{
    int cnt =0;
    for(int i=0;i<order.size();i++){
        bool bCheck = true;
        for(int j=0;j<comb.size();j++){
            if(order[i].find(comb[j]) == -1){
                bCheck= false;
                break;
            }
        }
        if(bCheck)  cnt++;
    }
    return cnt;
}
void DFS(int cnt,int idx)
{
    if(num == cnt)   {
        int res = solve();
        string tmp = "";
        for(int i =0 ;i<comb.size();i++)
            tmp+=comb[i];
        v.push_back({res, tmp});
        return ;
    }
    for(int i=idx;i<c.size();i++){
        comb.push_back(c[i]);
        DFS(cnt+1,i+1);
        comb.pop_back();
    }
}
vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    order = orders;
    
    for(int i=0;i<orders.size();i++){
        for(int j=0;j<orders[i].size();j++){
            if(find(c.begin(),c.end(),orders[i][j]) == c.end()) c.push_back(orders[i][j]);
        }
    
    }
    sort(c.begin(),c.end());
    for(int i=0;i<course.size();i++){
        num = course[i];
        DFS(0,0);
        comb.clear();
        sort(v.begin(),v.end(),comp);
        int res = v[0].first;
        if(res < 2 ) {
            v.clear();
            break;
        }  
        for(int j=0;j<v.size();j++){
            if(v[j].first == res)   answer.push_back(v[j].second);
            else break;
        }
        v.clear();
    }
    sort(answer.begin(),answer.end());
    return answer;
}

[문제]

https://programmers.co.kr/learn/courses/30/lessons/1835

[풀이]

처음 문제 봤을 때 Level2라는게 믿기지 않았다.

도저히 감이 안잡혀서 다른 분들의 풀이를 봤는데 생각보다 간단한 문제였다.

next_permutation 함수를 통해 프렌즈들이 일렬로 설 수 있는 모든 경우의 수를 구할 수 있다.

각 case마다 주어진 조건을 만족하는지 확인 후 , 모든 조건을 만족할 경우 answer에 +1을 해주어 

주어진 조건을 만족하여 사진을 찍는 모든 경우의 수를 구할 수 있다.

[코드]

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int len =0;
char sign;

bool check(int diff)
{
    if(sign == '=')
        return diff==len;
    else if(sign == '>')
        return diff > len ? true : false;
    else if(sign == '<')
        return diff < len ? true : false;
}
int solution(int n, vector<string> data) {
    int answer = 0;
    string friends = "ACFJMNRT";

    do{
        bool bCheck = true;
        for(int i=0;i<data.size();i++){
            int diff = friends.find(data[i][0]) - friends.find(data[i][2]);
            sign = data[i][3];
            len = data[i][4]-'0';
            bCheck = check(abs(diff)-1);
            if(!bCheck) break;
        }
        if(bCheck)  answer++;
    }while(next_permutation(friends.begin(),friends.end()));
        
    return answer;
}