'프로그래머스' 카테고리의 글 목록 (3 Page)

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

코딩테스트 연습 - 탑 | 프로그래머스

수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7

programmers.co.kr

왼쪽으로 레이저 신호를 발사할 것이므로 신호를 송신할 탑보다 앞쪽 인덱스의 탑들을 검사해주면 된다.

앞쪽의 탑들 중 송신하는 탑보다 높은 탑이 있다면 그 탑의 인덱스를 스택에 넣어준다.

앞쪽의 탑들을 모두 검사했는데 송신탑보다 높은 탑이 하나도 없다면 0을 스택에 넣어준다.

가장 왼쪽에 있는 탑은 신호를 수신할 탑이 앞쪽에 없으므로 스택에 바로 0을 넣어주어서 따로 처리를 해준다.

그리고 다시 왼쪽에 있는 탑부터 수신 탑의 인덱스를 출력하기 위해서 스택에서 꺼낸 값들을 바로 answer에 넣어준다.

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

#include <string>
#include <vector>
#include <stack>
 
using namespace std;
 
vector<int> solution(vector<int> heights) {
    
    vector<int> answer;
    stack<int> st;
    
    int size = heights.size();
    for(int i=size-1; i>0; i--) {
        bool flag = false;
        
        //왼쪽으로 레이저 신호를 발사
        for(int j=i-1; j>=0; j--) {
            if(heights[i] < heights[j]) {
                st.push(j+1);
                flag = true;
                break;
            }
        }
        
        //수신할 수 있는 탑이 하나도 없다.
        if(!flag) {
            st.push(0);
        }
    }
    
    
    //가장 왼쪽 탑
    st.push(0);
    
    while(!st.empty()) {
        answer.push_back(st.top());
        st.pop();
    }
    
    
    return answer;
}
Colored by Color Scripter

 

저작자표시

'프로그래머스' 카테고리의 다른 글

프로그래머스 (2018년)KAKAO BLIND RECRUITMENT 실패율 c++ (0)	2019.08.22
프로그래머스 (2018년)KAKAO BLIND RECRUITMENT 오픈채팅방 c++ (0)	2019.08.22
프로그래머스 프린터 (c++) (0)	2019.08.20
프로그래머스 위장 (0)	2019.08.19
프로그래머스 전화번호 목록 (0)	2019.08.19

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

코딩테스트 연습 - 프린터 | 프로그래머스

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다. 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에

programmers.co.kr

먼저 큐에 인쇄 대기목록을 모두 넣어주고 우선순위 큐를 하나 더 만들어서 중요도를 모두 넣어준다.

우선순위 큐는 기본적으로 최대 힙이기때문에 큰 값이 먼저 나온다.

이제 큐에 넣은 인쇄 대기목록을 순차적으로 처리해줄건데

먼저 중요도가 가장 높아야 하고 그 다음에는 순차적으로 앞에 있는 문서를 인쇄하면 된다.

먼저 큐에 있는 값을 뽑아와서 pop한 후에

우선순위 큐의 top에 있는 값과 현재 문서의 중요도가 같다면 인쇄하면 된다.

현재 우선순위가 사용되었으므로 우선순위 큐도 pop해주고 인쇄를 한 번 했으므로 answer도 1 증가시킨다.

이때 만약 인쇄한 문서가 내가 요청한 문서라면(location) 더 이상 인쇄를 할 필요가 없으므로 break해준다.

우선순위 큐의 top에 있는 값과 문서의 중요도가 같지 않았다면

현재 문서보다 중요도가 더 높은 문서가 존재한다는 뜻이므로 인쇄를 하지 않고 다시 큐에 넣어준다.

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

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
 
int solution(vector<int> priorities, int location) {
    int answer = 0;
    priority_queue<int> pq;
    queue<pair<int,int>> q;
    
    int size = priorities.size();
    for(int i=0; i<size; i++) {
        q.push(make_pair(i, priorities[i]));
        pq.push(priorities[i]);
    }
    
    
    while(!q.empty()) {
        int i = q.front().first;
        int p = q.front().second;
        q.pop();
        
        //현재 문서의 중요도가 가장 높은 중요도라면 인쇄
        if(p == pq.top()) {
            pq.pop();
            answer += 1;
            
            //현재 문서가 내가 인쇄를 요청한 문서다
            if(i == location) {
                break;
            }
            
        } else {
            //다시 큐에 넣는다.
            q.push(make_pair(i,p));
        }
 
    }
    
    return answer;
}
Colored by Color Scripter

 

저작자표시

'프로그래머스' 카테고리의 다른 글

프로그래머스 (2018년)KAKAO BLIND RECRUITMENT 오픈채팅방 c++ (0)	2019.08.22
프로그래머스 탑 (c++) (0)	2019.08.20
프로그래머스 위장 (0)	2019.08.19
프로그래머스 전화번호 목록 (0)	2019.08.19
프로그래머스 완주하지 못한 선수 (1)	2019.08.19

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

코딩테스트 연습 - 위장 | 프로그래머스

programmers.co.kr

map을 이용해서 간단하게 풀 수 있는 문제이다.

옷의 종류를 key로 해당 종류에 속하는 옷들의 개수를 value로 넣는다.

즉, 해당 옷의 종류가 map에 존재하지 않으면 값을 1로 새로 추가해주고

이미 존재한다면 값을 증가시킨다.

그리고 map을 검사하면서 정답을 구해준다.

각 옷의 종류의 개수 + 1 한 값을 answer에 곱해주고 마지막에 -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

#include <string>
#include <vector>
#include <map>
 
using namespace std;
 
int solution(vector<vector<string>> clothes) {
    int answer = 1;
    
    map<string, int> m;
    
    for(auto elem : clothes) {
        if(m.find(elem[1]) == m.end()) {
            m.insert(make_pair(elem[1],1));
        } else {
            m[elem[1]]++;
        }
    }
 
    for(auto iter=m.begin(); iter != m.end(); iter++) {            
        answer *= (iter->second + 1);
    }
    answer -= 1;
 
    
    return answer;
}
Colored by Color Scripter

 

저작자표시

'프로그래머스' 카테고리의 다른 글

프로그래머스 (2018년)KAKAO BLIND RECRUITMENT 오픈채팅방 c++ (0)	2019.08.22
프로그래머스 탑 (c++) (0)	2019.08.20
프로그래머스 프린터 (c++) (0)	2019.08.20
프로그래머스 전화번호 목록 (0)	2019.08.19
프로그래머스 완주하지 못한 선수 (1)	2019.08.19

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

코딩테스트 연습 - 전화번호 목록 | 프로그래머스

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 r

programmers.co.kr

정렬시킨 후에 현재 전화번호와 다음 전화번호를 비교해주면 된다.

문자열로 된 숫자이기 때문에 숫자 크기가 아니라 사전 순으로 정렬되므로 앞부분이 같다면 벡터에서 옆에 위치하게 될 것이다.

현재 전화번호가 다음 전화번호의 접두어인지를 확인해주면 되는데

다음 전화번호를 현재 전화번호 길이만큼 잘라서 같은 문자열이 되는지 확인해보고 같아지는 경우가 있다면 바로 false를 리턴한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool solution(vector<string> phone_book) {
    bool answer = true;
    sort(phone_book.begin(),phone_book.end());
    
    int size = phone_book.size();
    for(int i=0; i<size-1; i++) {
        if(phone_book[i] == phone_book[i+1].substr(0, phone_book[i].size())) {
            return false;
        }
    }
    
    return answer;
}
Colored by Color Scripter

 

저작자표시

'프로그래머스' 카테고리의 다른 글

프로그래머스 (2018년)KAKAO BLIND RECRUITMENT 오픈채팅방 c++ (0)	2019.08.22
프로그래머스 탑 (c++) (0)	2019.08.20
프로그래머스 프린터 (c++) (0)	2019.08.20
프로그래머스 위장 (0)	2019.08.19
프로그래머스 완주하지 못한 선수 (1)	2019.08.19

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

코딩테스트 연습 - 완주하지 못한 선수 | 프로그래머스

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 partic

programmers.co.kr

이 문제는 해시 카테고리에 있지만 해시를 사용하지 않고 풀 수 있기때문에

그냥 정렬을 이용해서 먼저 풀어보고 map을 이용해서도 풀어봤다.

문제에서 completion의 길이는 participant보다 1이 작다고 했으므로 완주하지 못한 선수는 항상 1명뿐이다.

먼저 정렬을 이용한 풀이다.

participant와 completion 벡터를 각각 정렬해준다. 그러면 완주하지 못한 선수전까지는 같은 이름이라면 같은 위치에 올 것이다.

completion의 길이만큼 반복문을 돌면서 participant와 이름이 같은지 확인한다.

이름이 다르다면 그떄의 선수가 완주하지 못한 선수이다.

participant의 마지막 선수가 완주하지 못한 선수인 경우는 flag변수를 사용해서 따로 처리해주었다.

처음에 flag를 false로 초기화 해놓는다.

위에서 반복문을 돌다가 완주하지 못한 선수를 발견하였다면 flag를 true로 바꿔준다.

반복문이 끝났는데도 flag가 false라면 반복문 내에서 완주하지 못한 선수를 찾지 못한 경우이다.

즉, 마지막 participant에 남은 선수가 완주하지 못한선수이다.

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

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());
    
    int size = completion.size();
    bool flag = false;
    for(int i=0; i<size; i++) {
        if(participant[i] == completion[i]) continue;
        
        answer = participant[i];
        flag = true;
        break;
    }
    
    if(!flag) {
        answer = participant[size];
    }
    
    return answer;
}
Colored by Color Scripter

 

두 번째 풀이는 map을 사용하였다.

map은 key는 string으로 value는 int로 해서

string에는 선수의 이름, value에는 해당 이름을 가진 선수의 인원수로 저장한다.

먼저 completion에 있는 선수들을 map에 1값으로 추가한다.

동명이인이 있는 경우에는 해당 선수의 값을 증가시킨다.

그리고 모든 참가자들(participant)에 대해서 map에 존재하는지 확인한다.

map에 존재하지 않는다면 바로 그 선수가 완주하지 못한 선수이다.

map에 참가자가 존재한다면 값이 0인지 확인해주어야한다.

값이 0이면 이미 동명이인인 선수가 완주한 것을 나타내는 것이므로 그때의 선수가 완주하지 못한선수이다.

0이 아닌 경우에는 동명이인인 경우의 처리를 위해서 map의 값을 하나 빼준다.

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

#include <string>
#include <vector>
#include <algorithm>
#include <map>
 
 
using namespace std;
 
 
string solution(vector<string> participant, vector<string>  completion) {
    string answer = "";
    map<string, int> m;
    
    for(auto elem : completion) {
        //map에 없다면 값을 1로 주고 추가한다.
        if(m.find(elem) == m.end()) {
            m.insert(make_pair(elem, 1));
        } else {
            //map에 이미 있다면 값을 증가시킨다.
            m[elem]++;
        }
    }
    
    for(auto elem : participant) {
        //map에서 참가자를 찾지 못했다면 해당 참가자가 완주하지 못했다.
        if(m.find(elem) == m.end()) {
            answer = elem;
            break;
        } else {
            //map의 값이 0인 경우에도 해당 참가자가 완주하지 못한 경우이다.
            if(m[elem] == 0) {
                answer = elem;
                break;
            } else {
                //값을 감소시킨다.
                m[elem]--;
            }
            
        }
        
    }
    
    return answer;
}
Colored by Color Scripter

 

저작자표시

'프로그래머스' 카테고리의 다른 글

프로그래머스 (2018년)KAKAO BLIND RECRUITMENT 오픈채팅방 c++ (0)	2019.08.22
프로그래머스 탑 (c++) (0)	2019.08.20
프로그래머스 프린터 (c++) (0)	2019.08.20
프로그래머스 위장 (0)	2019.08.19
프로그래머스 전화번호 목록 (0)	2019.08.19

알고리즘매일매일