say repository

출처: 프로그래머스

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

def solution(id_list, report, k):
    answer = [0] * len(id_list)
    cnt = {id:0 for id in id_list} # id 별 신고된 횟수
    d = {id:[] for id in id_list} # 이용자 id 가 신고한 id들 딕셔너리

    for repo in set(report):
        rep = repo.split(' ') # 이용자id와 신고한 id 분리
        d[rep[0]].append(rep[1]) # 딕셔너리에서 이용자 id 키에 신고한 id들 추가
        cnt[rep[1]] += 1 # 신고횟수

    # print(d)
    for key,values in d.items():
        for val in values:
            if cnt[val] >= k: # 신고횟수가 k번 이상이면
                answer[id_list.index(key)] += 1
    # print(answer)
    return answer

풀이 

딕셔너리를 사용해 풀이했다.

문제 풀이에 필요한 딕셔너리와 답 배열이다.

이용자와 신고한 id가 같아서 헷갈리기에 정리를 잘 하고 코딩을 하자.

• d = { 이용자 id : [신고한 id들...]}
• cnt = { 신고당한 id : 신고당한 횟수 }
• answer = [ id_list 순서대로 k번 이상 신고당한 유저를 신고한 회원들에게 메일 보낸 횟수 +1 ]

• 각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다.
  • 신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다.
  • 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다.

이 조건에서 한 유저가 한 유저를 계속 신고하는 것은 1회로 처리하기에 set(report)를 해준다.

이는 테스트케이스2를 보고 이해하면 된다.

공백 기준으로 set(report)를 잘라주고 만들어둔 d 딕셔너리에 삽입한다.

또, cnt 딕셔너리에 신고당한 id 별 신고 횟수를 적는다.

모두 딕셔너리에 넣고, cnt 딕셔너리에서 k번 이상 신고당한 유저들을 신고한 유저인 d 딕셔너리의 key를

answer에서 메일 보낸 횟수 +=1 해준다. 

* 딕셔너리 작성

cnt = {id:0 for id in id_list} # id 별 신고된 횟수
d = {id:[] for id in id_list} # 이용자 id 가 신고한 id들 딕셔너리

말이 쫌 길긴 하지만, 충분히 풀 수 있다.

카카오 2022 블라인드 코딩테스트 채용 문제라고 한다. 

출처 : 프로그래머스

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

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

int solution(vector<int> sco, int K) {
    int answer = 0;
    //우선순위큐 minheap생성
    priority_queue<int, vector<int>, greater<int>> pq(sco.begin(), sco.end());
    
    while(pq.size()>1 && pq.top()<K){
        //큐에 음식 2개이상있고, 가장 작은 스코빌 지수가 k보다 작을때
        int tmp1 = pq.top();
        pq.pop();
        int tmp2 = pq.top();
        pq.pop();
        int tmp3 = (tmp1+ (tmp2*2));
        pq.push(tmp3);
        answer ++; // 섞어주기
    }
    if (pq.top()>=K)
        return answer;
    else
        return -1;
}

1. 힙에 음식 넣고 오름차순 정렬한다.

2. 가장 작은 두 음식을 뽑고, 규칙에 맞게 섞는다. 섞은 음식을 다시 넣고 정렬한다.

3. 음식이 2개 이상 있고, 가장 작은 음식이 k보다 작을 때 계속 진행한다.

이는 우선순위 큐를 이용해 풀었다.

우선순위 큐를 이용하면 알아서 정렬된다.

곧... 12시 지났으니까 오늘 보는 코테만 끝나면 다시 파이썬으로 코테 준비하련다... c++ 좋은데 파이썬으로 계속 준비했어서 헷갈린다 ㅡㅡ

c++에서의 우선순위큐

priority_queue<int, vector<int>, greater<int>> pq; //minheap

priority_queue<int> pq; //maxheap

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

출처: 프로그래머스

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

int answer = 50;
bool visited[50]; //방문words

//begin과 한 글자만 다른 words 찾는 함수
bool oneDiff(string a, string b){
    int cnt_diff = 0;
    for(int i=0; i<b.size(); i++){
        if(a[i]!=b[i]){
            cnt_diff ++;
        }
    }
    if(cnt_diff == 1) //하나만 다르면
        return true;
    else
        return false;
}

void dfs(string begin, string target, vector<string> words, int idx){
   
    if(begin == target){ //종료조건
        answer = min(idx, answer);
        return; //종료
    }
    
    for(int i=0; i<words.size(); i++){
        //한글자만 다르고 아직 방문하지 않았으면
        if(oneDiff(begin, words[i]) && !visited[i]){
            visited[i] = true;
            dfs(words[i], target, words, idx+1);
            visited[i] = false; //dfs종료 후 돌아오면, 백트래킹
        }
    }
    return;
}

int solution(string begin, string target, vector<string> words) {

    dfs(begin, target, words,0);
    if(answer == 50){ //변환할 수 없으면 0
        answer = 0;
    }
    return answer;
}

최대 words의 길이가 50이니까 answer도 50, visited크기도 50으로 맞춘다.

이 말은 최대로 50번 변환할 수 있다는 것이다.

우리는 최단 횟수를 구해야 하기에 횟수 0부터 시작해서 50이랑 비교해서 최솟값을 구해낸다.

dfs로 풀이했다.

begin과 words에 있는 단어를 비교했을 때, 한 글자만 다른 단어만 방문 가능하다.

한 글자만 다른 것을 판별하는 함수를 따로 oneDiff()로 만들었다.

아직 방문하지 않았고 한 글자만 다른 단어만 방문 표시하고 다음 단계인 dfs 진행한다.

dfs가 종료되었을 때, 다시 백트래킹으로 visited [i]= true 했던 것을 visited[i] = false 처리해준다.

백트래킹...............

연습하자

출처: 프로그래머스

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

#include <string>
#include <vector>
using namespace std;
bool visited[201]; //방문검사

void dfs(vector<vector<int>> &arr, int idx){
    visited[idx] = true;
    for(int i=0; i<arr[idx].size(); i++){
        if(arr[idx][i] == 1 && visited[i] == false){ //1이고 아직 방문하지 않은 컴
            // arr[idx][i] = 0;
            // visited[i] = true;
            dfs(arr, i); //dfs 진행
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for(int i=0; i<n; i++){
        if (visited[i]==false){
            dfs(computers,i); //dfs 진행
            answer++;
        }
    }
    return answer;
}

dfs로 풀이했다.

연결되어 있는 것이 1로 표시되어 있다.

dfs로 computers 벡터를 돌면서 인접한 1을 찾고 dfs진행이 끝나면 인접한 1 찾는 과정이 끝난 것이다.

끝날 때마다 answer++해준다.

출처: 프로그래머스

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

#include <string>
#include <vector>

using namespace std;
int answer = 0;
void dfs(vector<int> numbers, int target, int total, int index){
    if (index == numbers.size()){
        if (total == target){
            answer ++ ;
        }
        return;
    }
    
    dfs(numbers, target, total + numbers[index], index + 1);
    dfs(numbers, target, total - numbers[index], index + 1);
}
int solution(vector<int> numbers, int target) {
    dfs(numbers, target, numbers[0], 1);
    dfs(numbers, target, -numbers[0], 1);
    return answer;
}

# 14503
import sys
from collections import deque
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
n, m = map(int,sys.stdin.readline().split())
r, c, d = map(int,sys.stdin.readline().split())
arr = []
for _ in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))

def rotate_left(d): # 현재 바라보고있는 방향에서 왼쪽으로
    return (d+3) % 4

def back(d): # 후진
    return (d+2) % 4

def bfs(r,c,d):
    q = deque()
    q.append([r, c, d])
    arr[r][c] = 2 # 청소
    cnt = 1
    while q:
        qr, qc, qd = q.popleft()
        tmp_qd = qd
        for i in range(4):
            tmp_qd = rotate_left(tmp_qd) # 현재 방향에서 왼쪽으로
            nr = qr + dx[tmp_qd]
            nc = qc + dy[tmp_qd]
            # 왼쪽에 청소안한 방이 있다면
            if 0<=nr<n and 0<=nc<m and arr[nr][nc] == 0:
                # 아직 청소 안했으면 청소하고 방향바꾸기
                arr[nr][nc] = 2
                cnt += 1
                q.append([nr,nc,tmp_qd])
                break

            # 갈 곳이 없다면
            elif i==3:
                # 방향 유지한채 한칸 후진
                nr = qr + dx[back(qd)]
                nc = qc + dy[back(qd)]
                q.append([nr, nc, qd])

                if arr[nr][nc] == 1: # 뒤에도 벽이 있다면 중단
                    return cnt

print(bfs(r,c,d))

풀이

bfs로 풀이했다.

dx, dy 방향 배열을 북, 동 , 남, 서 (0, 1, 2, 3) 으로 저장해둔다.

왼쪽으로 이동하는 함수와 후진하는 함수를 구현해뒀다.

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

출처 : 프로그래머스

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

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    int carpet = brown + yellow;
    
    //carpet의 약수 구하기 (n가로, m세로)
    for (int m=3; m<carpet/2; m++){
        if (carpet % m == 0){
            int n = carpet / m;
            
            //노란색 개수와 맞는지 확인
            if((m-2)*(n-2) == yellow){
                answer.push_back(n);
                answer.push_back(m);
                break;
            }
        }
    }
    return answer;
}

그림을 그리며 생각해보면 규칙을 찾을 수 있다.

테두리가 갈색이어야하고 가운데에 노란색이 있어야하니까 세로의 최소 길이는 3이다.

3이상부터 가로가 세로보다 같거나 길어야하니까 이 조건을 주의해서 약수를 찾는다.

찾은 약수 쌍 중, 만들 수 있는 노란색의 개수가 네오가 본 노란색의 개수와 같다면 answer에 가로, 세로 추가하고 break

아니면 다른 약수 찾는다.