프로그래머스 적응기
1 - 해시 = Map
1. 폰켓몬
https://school.programmers.co.kr/learn/courses/30/lessons/1845
문제점
1. 프로그래머스에서 max와 min함수 사용 불가? = 가능함.
2. 바보 같이 10000개인 것에 DFS를 사용하여 NM문제처럼 풀려고 함.
(DFS는 20정도까지가 적당)
(visited만 체크하는 일방향성인 DFS의 경우에는 상관없다)
(그리고 만약에 10000개를 백트래킹까지 해야하는 경우에도,
조건에 따라 10000개를 돌지 않게 막을 수 있다면 가능)
아래 3번 참고
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
using namespace std;
int N;
set<int> s;
bool visited[10001];
vector<int> t_num;
int answer = 0;
void DFS(int n, int num)
{
if(n==t_num.size()/2)
{
//answer = max(answer, s.size());
answer < s.size() ? answer = s.size() : answer = answer;
}
else
{
for(int i=num;i<t_num.size();i++)
{
if(!visited[i])
{
visited[i] = true;
s.insert(t_num[i]);
DFS(n+1, i);
s.erase(t_num[i]);
visited[i] = false;
}
}
}
}
int solution(vector<int> nums)
{
ios::sync_with_stdio(0);
cin.tie(0);
t_num = nums;
DFS(0, 0);
return answer;
}구현
- 10000개에서 2개를 뽑아서 출력해라 라는 말이 아니므로..
그냥 입력에서 중복을 제외한 값을 구했을 때,
입력의 반의 이상이라면, 딱 반개까지 고르는게 최대이므로,
그냥 반개를 출력....
너무 어렵게 생각했던 문제..
#include <vector>
#include <set>
using namespace std;
int solution(vector<int> nums)
{
int answer = 0;
set<int> s;
for(auto i : nums)
{
s.insert(i);
}
if(s.size()>=nums.size()/2)
{
//cout <<
answer = nums.size()/2;
}
else
{
//cout <<
answer = s.size();
}
return answer;
}2. 달리기
https://school.programmers.co.kr/learn/courses/30/lessons/42576?language=cpp
구현
- 참여자 / 완주자 vector가 주어진다. 총 2개.
- 완주하지 못한 사람은 딱 1명, 동명이인이 있을 수 있다.
- 그 사람을 출력해라.
- 두 벡터를 sort한 뒤에 for문을 차례대로 돌렸을 때, 다르면 출력.
문제점
1. 프로그래머스는 iostream을 넣어야한다.
그래야 내가 쓰는 cin cout을 사용할 수 있다.
2. 그리고 기억난다면, ios::sync_with_stdio(0)과 cin.tie(0)을 넣는다.
- 안넣어도 되는게,, 프로그래머스는 출력이 아니라 return을 기준으로 답을 매긴다.
따라서 debug용으로 iostream을 넣는 것 외에는 불필요.
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
string solution(vector<string> participant, vector<string> completion) {
string answer = "";
sort(participant.begin(), participant.end());
sort(completion.begin(), completion.end());
/*
for(auto i : participant)
{
cout << i << " ";
}
cout << "\n\n";
for(auto i : completion)
{
cout << i << " ";
}
*/
for(int i=0;i<participant.size();i++)
{
if(i==participant.size()-1)
{
answer = participant[i];
break;
}
if(participant[i]!=completion[i])
{
answer = participant[i];
break;
}
}
return answer;
}3. 전화번호 접두사
https://school.programmers.co.kr/learn/courses/30/lessons/42577?language=cpp
구현
- 한 전화번호가 다른 전화번호의 앞부분과 동일하면,
ex) 123 / 1234false를 리턴해라.- 100 0000이라서 2중 for문을 절대 못돌린다.
2개씩 뽑아서 비교해야만 풀릴 것 같지만, 그렇게 하지 않아도 된다.- 그 이유는 sort하고 바로 다음 것과만 비교하면 된다.
그렇게 되면 100 0000번 이하의 연산을 하게 된다.- 바로 다음 것만 비교하는 이유는, 어짜피 사전순으로 정렬이 되어있는 바로 다음것도 아니라면,
그 다음것도 무조건 아니기 때문.
문제점
1. 이전에 사용했던 개념이라 쉽게 풀었지만, 몰랐다면 한참 고민했을 듯
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool solution(vector<string> phone_book) {
bool answer = true;
sort(phone_book.begin(), phone_book.end());
for(int i=0;i<phone_book.size()-1;i++)
{
for(int j=0;j<phone_book[i].length();j++)
{
if(phone_book[i][j] != phone_book[i+1][j])
{
break;
}
if(j==phone_book[i].length()-1)
{
return false;
}
}
}
return answer;
}4. 의상
https://school.programmers.co.kr/learn/courses/30/lessons/42578?language=cpp
구현
- 옷의 종류가 주어질 때, 같은 종류의 옷은 동시에 입을 수 없다.
- 옷을 입는 경우의 수를 출력하면 됨.
- map을 이용하여 같은 종류면 value를 증가하도록 했다.
문제점
1. map관련 함수들이 익숙하지 않음.
find, insert, 키로 인덱스처럼 접근, value값을 가져오려면 second이용 등등...
#include <string>
#include <vector>
#include <iostream>
#include <map>
using namespace std;
int solution(vector<vector<string>> clothes) {
int answer = 1;
map<string, int> m;
for(auto i : clothes)
{
if(m.find(i[1])!=m.end())
{
m[i[1]]++;
}
else
{
m.insert({i[1], 1});
}
}
for(auto i : m)
{
answer *= i.second+1;
}
return answer-1;
}5. 베스트 앨범
https://school.programmers.co.kr/learn/courses/30/lessons/42579?language=cpp
구현
- 규칙
- 이를 위해서 genres, plays라는 2개의 벡터가 주어진다.
- 이를 구현하기 위해 map을 2개 생성한다.
문제점
1. map으로 구조적으로 어떻게 구현해야할지 몰랐다.
그래서 풀이를 카피했다.
https://mungto.tistory.com/196 참고
#include <string>
#include <vector>
#include <map>
#include <iostream>
using namespace std;
vector<int> solution(vector<string> genres, vector<int> plays) {
vector<int> answer;
map<string, int> music; // 장르의 빈도를 측정하기 위한 map
map<string, map<int, int>> musiclist; // 장르 - 노래번호, 플레이횟수
for (int i = 0; i < genres.size(); i++) {
music[genres[i]] += plays[i];
musiclist[genres[i]] [i] = plays[i]; //장르의 i번째에 plays, i가 노래의 번호가 됨.
}
while (music.size() > 0) {
string max_genre;
int max = 0;
//장르중에서 제일높은것 찾기
for (auto mu : music){
if (max < mu.second){
max = mu.second;
max_genre = mu.first;
}
}
//2곡을 넣어야하므로 2번반복
for (int i = 0; i < 2; i++){
int val = 0, ind = -1;
//노래중에서 제일높은것 찾기
for (auto ml : musiclist[max_genre]) {
if (val < ml.second) {
val = ml.second;
ind = ml.first;
}
}
//만약 노래가 0~1곡밖에없다면 반복문 탈출
if (ind == -1) break;
//리턴할 리스트에 노래번호 추가
answer.push_back(ind);
musiclist[max_genre].erase(ind);
}
//map 에서 사용한 장르삭제
music.erase(max_genre);
}
return answer;
}2 - BFS/DFS
1. 타겟 넘버
https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=cpp
구현
- 수의 배열이 주어지고, 수의 부호를 적절히 바꾸어 target을 완성하면 되는 문제.
- 2차원 map에선 dfs를 4방향으로 했는데,
그걸 2방향(-1 +1)으로 한다고 생각하면 편하다.- 하나의 최단 경우가 아니라, 모든 경우를 판단해야 하므로,
DFS와 백트래킹을 이용한다.
문제점
1. visited를 구현해야만 하고,
visited의 인덱스를 i로 적어서 문제가 되었었다.
n으로 수정하여 해결.
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int answer=0;
int arr[21];
bool visited[21];
int t_target;
vector<int> v;
void DFS(int n)
{
if(n==v.size())
{
int result = 0;
for(int i=0; i<v.size();i++)
{
//cout << arr[i]*v[i] << " ";
result += arr[i]*v[i];
}
if(result == t_target)
{
answer++;
}
}
else
{
for(int i=0;i<2;i++)
{
if(!visited[n])
{
if(i==0)
{
arr[n] = 1;
}
else if(i==1)
{
arr[n] = -1;
}
visited[n] = true;
DFS(n+1);
visited[n] = false;
}
}
}
}
int solution(vector<int> numbers, int target) {
v = numbers;
t_target = target;
DFS(0);
return answer;
}2. 네트워크(섬개수)
https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=cpp
구현
- visited를 false로 다시 back시키 않는 DFS를 통해 구현한다.
문제점
1. DFS의 for문을 작성하는데 인덱스의 범위가 헷갈렸다.
#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
vector<vector<int>> t_computers;
bool visited[201];
void DFS(int num)
{
for(int i=0; i<t_computers[num].size(); i++)
{
if(!visited[i] && t_computers[num][i])
{
visited[i] = true;
DFS(i);
}
}
}
int solution(int n, vector<vector<int>> computers) {
int answer = 0;
t_computers = computers;
for(int i=0;i<computers.size();i++)
{
if(!visited[i])
{
visited[i] = true;
DFS(i);
answer++;
}
}
return answer;
}3. 최단거리
https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=cpp
구현
- BFS를 통한 최단거리 정석 문제
문제점
1. 시작점도 더해야 했다.
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
vector<vector<int>> t_maps;
bool visited[101][101];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};
int solution(vector<vector<int>> maps)
{
int answer = 987654321;
t_maps = maps;
queue<pair<pair<int, int>, int>> q;
q.push({{0,0}, 1});
visited[0][0] = 1;
while(!q.empty())
{
int x = q.front().first.first;
int y = q.front().first.second;
int count = q.front().second;
if(x==t_maps.size()-1 &&
y==t_maps[0].size()-1)
{
answer > count ? answer=count : answer=answer;
}
q.pop();
for(int i=0;i<4;i++)
{
int cx = x + dx[i];
int cy = y + dy[i];
if(cx < 0 || cx >= t_maps.size()
|| cy < 0 || cy >= t_maps[0].size())
{
continue;
}
if(!visited[cx][cy]&&t_maps[cx][cy]==1)
{
visited[cx][cy] = 1;
q.push({{cx, cy}, count+1});
}
}
}
if(answer==987654321)
{
answer = -1;
}
return answer;
}4. 단어 변환
https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=cpp
구현
- 목록으로 주어진 단어중에서 현재 단어로부터 한 글자씩 변환해서 목표로 가는 문제.
- BFS로 그냥 막 풀어도 되는 문제였다.
- 문자열 자체를 하나의 노드로 보고,
다음 노드의 판별 및 큐의 삽입할 노드의 확인은,
한 글자만 다른지 확인을 통해서 넣는다.
문제점
1. 아래처럼 비교를 해야했는데, s[i]라고 적었어서 오류.
if(words[i][k]!=s[k])
2. min을 비교해야하는데,
프로그래머스는 answer = 0이 기본으로 적혀있어서if(answer==987654321) { answer = 0; }기본값 987654321을 넣어주지 않았어서 오류.
#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
bool visited[51];
int solution(string begin, string target, vector<string> words) {
int answer = 987654321;
queue<pair<string, int>> q; // 현재 단어, count
words.push_back(begin);
q.push({begin, 0});
while(!q.empty())
{
string s = q.front().first;
int count = q.front().second;
q.pop();
if(s==target)
{
answer > count ? answer=count:answer=answer;
}
else
{
for(int i=0;i<words.size();i++)
{
if(!visited[i])
{
int incorrect=0;
for(int k=0;k<words[i].size();k++)
{
if(words[i][k]!=s[k])
{
incorrect++;
}
}
if(incorrect!=1)
{
continue;
}
visited[i] = 1;
q.push({words[i], count+1});
}
}
}
}
if(answer==987654321)
{
answer = 0;
}
return answer;
}5. 아이템 줍기
구현
- 그냥 구현하면 겹치는 부분이 생겨서 길이를 x2배 하여,
2배로 늘려서 구현한다.
문제점
1. 2배로 늘렸기 때문에 BFS의 visited index도 2배로 늘려줬어야 했는데
그러지 않았다.
#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
int visited[102][102];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,-1,0,1};
int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
int answer = 1987654321;
// 사각형 범위 내를 모두 1로 채우기
characterX *= 2, characterY *= 2, itemX *= 2, itemY *= 2;
for(int i=0;i<rectangle.size();i++)
{
for(int a=rectangle[i][0]*2;a<=rectangle[i][2]*2;a++)
{
for(int b=rectangle[i][1]*2;b<=rectangle[i][3]*2;b++)
{
visited[a][b]=1;
}
}
}
// 시작+1 끝-1을 하여 사각형 내부 0으로 다시 채우기
for(int i=0;i<rectangle.size();i++)
{
for(int a=rectangle[i][0]*2+1;a<=rectangle[i][2]*2-1;a++)
{
for(int b=rectangle[i][1]*2+1;b<=rectangle[i][3]*2-1;b++)
{
visited[a][b]=0;
}
}
}
queue<pair<pair<int, int>,int>> q;
visited[characterX][characterY] = 1;
q.push({{characterX,characterY},0});
while(!q.empty())
{
int x = q.front().first.first;
int y = q.front().first.second;
int count = q.front().second;
q.pop();
if(x==itemX && y == itemY)
{
answer=min(answer,count);
}
else
{
for(int i=0;i<4;i++)
{
int cx = x + dx[i];
int cy = y + dy[i];
if(cx < 1 || cx >101 || cy < 1 || cy > 101)
{
continue;
}
if(visited[cx][cy])
{
visited[cx][cy] = 0;
q.push({{cx, cy}, count+1});
}
}
}
}
return answer/2;
}6. 여행 경로
https://school.programmers.co.kr/learn/courses/30/lessons/43164?language=cpp#
구현
- 모든 경로를 방문했을 때, 사전순으로 가장 빠른 경로를 출력한다.
- 사전순이 들어간다면, vector의 sort연산을 거의 필수로 해야했다.
- 어쨌든 for문에서 순서대로 들어가는 것이고, 해당 우선순위가 중요하기 때문에,
sort연산을 해서 정렬한다.- Vector는 push_back, pop_back()을 통해서 백트래킹한다.
- 백트래킹을 하지만, 모든 경로를 전부는돌지 않아도 되고,
조건이 존재하므로 DFS로 풀 수 있다.
그리고 BFS로 풀면 안풀린다.
문제점
1. DFS를 그만두는 연산을 몰라서 c=0으로 놓고,
가장 최초의 답만 결과로 복사하도록 하였다..
2. push_back("111")의 짝꿍은 pop_back..
3. 왜 BFS로 안풀리지??
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
bool visited[10001];
vector<vector<string>> t_tickets;
vector<string> answer;
vector<string> t_answer;
int c = 0;
void DFS(string to, int n)
{
if(n==t_tickets.size())
{
if(c==0) // DFS를 나갈 방도를 모르겠다..
{
t_answer = answer;
c++;
}
}
else
{
for(int i=0;i<t_tickets.size();i++)
{
if(!visited[i] && t_tickets[i][0] == to)
{
visited[i] = 1;
answer.push_back(t_tickets[i][1]); // 다음 장소 결과 벡터에 저장
DFS(t_tickets[i][1], n+1);
answer.pop_back();
visited[i] = 0;
}
}
}
}
vector<string> solution(vector<vector<string>> tickets) {
sort(tickets.begin(), tickets.end());
t_tickets = tickets;
answer.push_back("ICN");
DFS("ICN", 0);
return t_answer;
}
Time Waits for No One