네발로 코딩하는 포메라니안

1. 문제 https://www.acmicpc.net/problem/18430 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 2. 풀이과정 방문체크를 3개씩 하는 DFS 문제이다. 처음에 N, M이 5이하라서 방문체크를 비트마스킹으로 풀었는데, boolean으로 풀었을 때가 1.5배나 빨랐다. 비트마스킹은 배열이 아닌 int로 풀어서 2차원 배열 1차원 배열 전환하는 연산이 많아서 느렸던 것 같다. +) 벽세우기를 한 후, 1.5배 더 빨라졌다. import java.io.*; import ..

1. 문제 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 2. 풀이과정 이 문제는 dfs나 bfs 둘 중 하나로 풀 수 있을 것 같은데, dfs를 선택한 이유는 n, m의 최대 크기가 100으로 작은 편이라 stack이 최대 100x100개정도 밖에 안 쌓이며, 코드도 더 짧기 때문이다. import java.util.*; import java.io.*; public class boj1743 { sta..

1. 문제 https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 2. 풀이과정 1. 부모 정보를 배열에 받아서 저장한다. 2. 뒷번호부터 검사(leaf노드부터 검사하기 위함) 1) 해당 숫자를 부모로 가진 자식들의 직간접적으로 이어진 자식들의 수를 구해서 정렬한다. 2) 자식들 중 아래에 있는 자식들이 많은 것부터 차례로 순서를 부여한다. 3) 순서 + 아래에 있는 자식들의 수가 가장 큰 값을 해당 숫자에 기록하며 업데이트 해간다. import java...

1. 문제 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 2. 풀이과정 1. 파티 정보를 Queue에 넣고, 결과는 Queue의 사이즈를 출력한다. 2. 진실을 아는 사람은 집합(set)으로 관리한다. 3. Queue에서 파티 하나를 꺼내서 거짓말 할 수 있는지 check 1) 파티의 참여자 중 set에 포함된 사람이 있으면 해당 파티 참여자도 set에 넣는다. 2) set에 한 명도 포함되지 않으면, 다시 queue에 넣는다. 4. 진실을 아는 사람 ..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/92342 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 1. 점수를 얻기 위한 최소 화살의 수를 계산하여 저장 + 남은 건 다 0에 넣는다. - 같은 점수면 낮은 점수에 화살이 많은 것을 선택하기 때문에 개수가 딱 떨어지지 않으면 0으로 넣는다. - 비트마스킹으로 낮은 점수에 화살이 많은 것을 구분한다. 2. dfs로 최대 점수를 계산한다. - 어피치의 점수를 뺏은 경우 2배로 얻는다. class Solution { int l..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/64064# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 요약 : Brute force(DFS), 집합, 비트마스킹 1. banned_id별로 가능한 user_id를 넣는다. (여기는 자료형 딱히 상관없을 것 같다.) 2. 배열의 크기가 8이하 => 비트마스킹 가능 3. 방문 체크한 int변수를 집합에 넣어서, 중복 검사를 한다. +) 문자열 비교(banned_id & user_id) 정규표현식에 익숙하지 않아서 로직을 직접..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/92341 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 HashMap에 을 기록한다. - 입/출차 기록 : 입차할 때는 +1, 출차할 때는 -1을 해서 마지막에 요금을 계산할 때 1이면 23:59분으로 출차! - 총_시간 : 입차할 때는 -minute, 출차할 때는 +minute으로 총 시간을 계산한다. Key들을 정렬해서, 차례대로 가격을 계산해서 결과를 출력한다. import java.util.*; class Soluti..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/72413# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 - 중간 지점을 W라고 하면 S=>W, W=>A, W=>B로 구간을 나눠서 생각한다. - 각 구간 별 최단 거리 구하기 문제 방법1. 플로이드 워샬 - 모든 노드에서 모든 노드까지 전체 최단 거리를 구한다. - S=>W, W=>A, W=>B까지 모두 더한 값이 최소인 값을 찾는다. (중복이 있든 말든 상관없지만, 최단거리의 결과는 아마 중복 없게 나올듯 => 왔던 길 ..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 Dijkstra import java.util.*; //돌아오는 건 생각X = 재방문이 가능하므로 갔던 길 똑같이 되돌아오자 class Solution { LinkedList list[]; public int[] solution(int n, int[][] paths, int[] gates, int[] summits) { int[] answer = {999_999_999..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/17676 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 1. 밀리초로 변환 2. 끝나는 지점을 기준으로 정렬되어 있으므로 뒤에서부터 탐색 3. 끝나는 지점에서 1초뒤에 있는 걸 기준으로 count : 갯수가 변하는 지점이 끝나는 지점과 일치하므로 4. priority queue로 시작점이 큰 순으로 정리해놓고, 지금 보는 끝지점+1초보다 더 크면 poll() import java.util.*; class Solution { ..