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

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 { ..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 - bfs + 비트마스킹 - 입력이 8개이하이므로 비트마스킹(32bit)을 사용 class Solution { int n, answer; public void bfs(int k, int[][] dungeons, int visit, int cnt){ answer = Math.max(answer, cnt); for(int i=0; i

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 - 끊었을 때 한 쪽 전력망 개수만 cnt해서 (전체)-cnt와 차이를 구한다. => dfs를 시작할 때, 제거할 선과 연결된 노드는 방문처리하여 다시 방문하지 않게 함으로써 "끊어짐"을 고려한다. - n-1개의 선으로, 전체 가능한 간선(n*(n-1))에 비해 매우 적은 편이므로 LinkedList로 구현 import java.util.*; class Solution ..

1. 문제 https://www.acmicpc.net/problem/1917 1917번: 정육면체 전개도 세 개의 입력 데이터가 주어지며, 각각의 입력 데이터는 여섯 개의 줄로 이루어져 있다. 각 데이터는 여섯 개의 줄에 걸쳐 여섯 개의 숫자가 빈 칸을 사이에 두고 주어진다. 숫자는 0 또는 1로 이 www.acmicpc.net 2. 풀이 과정 주사위의 위치와 번호를 이용하는 아이디어는 다른 코드를 보다가 얻어서 아쉽지만, 코드는 보지 않았기에 같은 아이디어라도 다르게 구현할 수 있었던 것 같다. 아이디어를 한 줄로 정리해보면, 원래의 주사위를 전개도로 펼친다고 볼 수 있다. 1. 주사위 위치에 따라 1~6번호를 저장하는 배열을 만든다. 2. 위로, 왼쪽으로, 오른쪽으로, 아래로 굴려가면서 배열 정보를 ..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 1. 균형 잡힌 괄호 문자열 + 올바른 괄호 문자열을 동시에 확인한다. - 열린 괄호가 오면 +1, 닫힌 괄호가 오면 -1 => 중간에 한 번이라도 음수가 되면, 올바른 괄호 문자열이 아니다. 2. u가 올바른 괄호 문자열인지에 따라, 다르게 처리하고 재귀함수를 돌린다. - '올바른'이면, u + 재귀(v) - '올바른'이 아니면, ( 재귀(v) ) + 뒤집은 u cla..

1. 문제 https://www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net 2. 풀이 과정 1. '0'으로 벽 세우기 2. 1~9까지 같은 수 dfs탐색 2-1. 주변에 자신보다 작은 값이 있으면 수영장 X 2-2. 주변에 자신보다 작은 값이 없으면 물 채우기 실행 예시 1. 1을 찾으면서 방문한 곳은 check한다. 2. 방문한 곳 주변이 자기보다 작은 값이 없다면, 1) 주변 값들인 5, 9중에 작은 5에 맞춰 채우고 방문 체크를 다..

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 1. game_board의 빈칸과 table의 퍼즐을 dfs로 탐색 1) 각 덩어리의 좌표들을 저장 2) 각 덩어리의 개수를 저장 3) 각 덩어리의 시작값 저장 2. 평행이동을 이용하여 같은 블럭인지 확인 & 회전을 반복한다. *회전은 블럭 하나하나를 생각하지 않고, 판 전체를 돌린다는 생각으로 좌표를 이동시켰다. import java.util.*; class Block{..

1. 문제 https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 2. 풀이 과정 1. 자신의 오른쪽만 보면서 업데이트한다. 2. 기울기가 증가하는 지점만 count한다. import java.io.*; import java.util.*; public class Boj1027 { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(..

1. 문제 https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 2. 풀이 과정 1) 지도의 색깔 정보 = 2차원 배열 2) 말의 위치 = 2차원 연결 리스트 배열에 '말 번호'를 저장 => 0번부터 말을 순서대로 이동시킨다. import java.io.*; import java.util.*; public class Boj17780 { static int N, K, map[][], nodes[][];//node정보 static LinkedList n..

1. 문제 https://www.acmicpc.net/problem/23791 23791번: K번째 음식 찾기 1 한식 [1..3], 양식 [1..3]을 오름차순으로 나열하면 1 2 3 5 8 10이고 여기서 세 번째로 맛있는 음식 맛은 3이므로 첫 번째 질의 정답은 양식 2번이다. 한식 [1..3], 양식 [1..4]를 오름차순으로 나열하면 www.acmicpc.net 2. 풀이 과정 병합 정렬 + 이진 탐색 문제이다. 여기서 시간 단축을 위해 누적합 개념을 추가적으로 사용했다. 예를 들어, 입력이 아래와 같이 주어진다면 4 1 5 10 15 2 3 8 9 병합 정렬하면서 한식, 양식 수를 세서 누적합을 구해놓고 이진탐색할 때 이용한다. 1 2 3 5 8 9 10 15 한식 1 1 1 2 2 2 3 4..