반응형

문제출처

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


효율성 테스트가 있는 문제이다. 

전체 탐색을 하면 효율성 테스트에서 통과하지 못한다. idea는 정렬을 통해 가장 작은 값의 시간을 한번에 빼는 방법을 사용하였다.


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool comp(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}
 
int solution(vector<int> food_times, long long k) {
    vector<pair<int, int>> food;
    int size = food_times.size();
    for(int i=0; i<size; i++)
        food.push_back(make_pair(food_times.at(i), i+1));
    
    sort(food.begin(), food.end());
    
    int time=0;
    for(vector<pair<int, int>>::iterator it=food.begin(); it!=food.end(); it++, size--) {
        long long leadTime = (long long)(it->first - time) * size;
        if(leadTime == 0)
            continue;
        
        if(leadTime <= k) {
            k-=leadTime;
            time=it->first;
        } else {
            k%=size;
            sort(it, food.end(), comp);
            return (it+k)->second;
        }       
    }
    return -1;
}
cs




반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 10809] 알파벳 찾기  (0) 2019.01.07
[BOJ_11724] 연결 요소의 개수  (0) 2019.01.07
[BOJ 11004] K번째 수  (0) 2019.01.07
[BOJ 3047] ABC  (0) 2019.01.06
[BOJ 1987] 알파벳  (0) 2019.01.05
반응형

문제출처

https://www.welcomekakao.com/learn/courses/30/lessons/42888


닉네임은 중복이 가능하므로 Set이 아니라 Map을 사용하였습니다.

1번문제인만큼 난이도는 낮네요!


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
 
public class Solution
{
    public String[] solution(String[] record) {
        Map<String, String> idMap = new HashMap<>();
        List<String[]> tmp = new LinkedList<>();
 
        for (String records : record)
        {
            String[] keyWord = records.split(" ");
            if (keyWord[0].equals("Enter"))
            {
                idMap.put(keyWord[1], keyWord[2]);
                tmp.add(keyWord);
            } else if (keyWord[0].equals("Change"))
            {
                idMap.put(keyWord[1], keyWord[2]);
            } else
            {
                tmp.add(keyWord);
            }
        }
 
        String[] answer = new String[tmp.size()];
        int idx = 0;
        for (String[] keyWords : tmp)
        {
            String nickName = idMap.get(keyWords[1]);
            if (keyWords[0].equals("Enter"))
                answer[idx++] = nickName + "님이 들어왔습니다.";
            else
                answer[idx++] = nickName + "님이 나갔습니다.";
        }
        return answer;
    }
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 3047] ABC  (0) 2019.01.06
[BOJ 1987] 알파벳  (0) 2019.01.05
[카카오 2019] 코딩테스트 - 실패율  (0) 2019.01.03
[프로그래머스 42842] 카펫  (2) 2019.01.02
[프로그래머스 43162] 네트워크  (0) 2019.01.01
반응형

문제 출처

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

정답률 : 55.57%


sorting문제이다. 정렬을 활용하는 법을 확인하는 듯 하다. 역시 앞쪽이라 문제를 급하게 안읽고 차근차근 읽어나가면 쉽게 풀 수 있는 문제다.

전체사용자 수를 구하고 stages를 돌면서 몇명의 사용자가 도달했는지 카운트합니다. 다음으로 이 값과 stages를 참조하여 실패율을 계산하고 내림차순으로 정렬하면 되는 문제입니다.


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool compare(pair<double, int> a, pair<double, int> b)
{
    // 실패율이 같다면 스테이지 번호가 작은것!
    if(a.first == b.first)
        return a.second < b.second;
    
    // 실패율이 큰것이 앞!
    return a.first > b.first;
}
 
vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    int users[501]={0};
    int userSize = stages.size();
    vector<pair<double, int>> failure;
    
    // 각각의 스테이지에 도달한 유저수
    for(vector<int>::iterator it = stages.begin(); it!=stages.end(); it++)
        users[*it-1]++;
    
    for(int i=0; i<N; i++)
    {
        if(users[i] == 0)
            failure.push_back(make_pair(0, i+1));
        else
        {
            failure.push_back(make_pair((double)users[i]/userSize, i+1));
            userSize -= users[i];
        }
    }
    
    sort(failure.begin(), failure.end(), compare);
    
    for(vector<pair<double, int>>::iterator it = failure.begin(); it!=failure.end(); it++)
        answer.push_back(it->second);
 
    return answer;
}
 
cs



반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 1987] 알파벳  (0) 2019.01.05
[카카오 2019] 코딩테스트 - 오픈채팅방  (0) 2019.01.03
[프로그래머스 42842] 카펫  (2) 2019.01.02
[프로그래머스 43162] 네트워크  (0) 2019.01.01
[BOJ 6603] 로또  (0) 2018.12.31

+ Recent posts

티스토리툴바