https://school.programmers.co.kr/learn/courses/30/lessons/72412 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 이진탐색을 사용하여 풀 수 있다. 핵심 이 문제는 정확성만 보자면, 완전탐색으로 구할 수 있다. 하지만 효율성을 통과하기 위해 이진탐색을 사용해야 한다. info의 정보를 가지고 "-"를 포함한 모든 조합을 map의 키값으로 가지고 이후 value값을 정렬시켜 이진탐색을 하면 된다. 정답 코드 import java.util.*; class Solution { static Map map;..
https://school.programmers.co.kr/learn/courses/30/lessons/72411 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 조합을 이용한 문제이다. 핵심 사람들이 주문한 상품들을 갖고 조합을 만들어서 가장 많이 나온 조합으로 메뉴를 만드는 것이다. 로직 자체는 있는 단순하다. 정답 코드 import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.List;..
https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net bfs를 이용하여 풀 수 있다. 핵심 2차원 배열을 일렬로 두고 그 값자체를 가지고 판단하면 편하게 구할 수 있다. 값의 위치를 바꿀 때 각각의 index를 알아야 하는데, 이때 StringBuilder를 이용하면 쉽게 위치를 바꿀 수 있다. StringBuilder.setCharAt -> 특정 위치에 char를 삽입할 수 있다. 이를 활용하여 풀어보자. 정답 코드 import java.util.HashMap; import java.util.LinkedList; import..
https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 조합과 완전탐색을 사용하여 풀 수 있다. 핵심 궁수는 N+1위 치에 3명 배치할 수 있다. 1 턴에 1명을 맞출 수 있고, 다른 궁수도 같은 적을 맞 출 수 있다. 궁수의 위치를 바꾸어가며 그때마다 잡은 적의 수를 카운트해야 한다. 정답 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; ..
https://school.programmers.co.kr/learn/courses/30/lessons/87694 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr bfs를 사용하는 문제이다. 핵심 문제에서 주어진 사각형들에 대해 겉 테두리만 돌아서 아이템 위치에 가장 빠르게 도착하는 횟수를 구해야 한다. 중요포인트는 map을 2배로 늘리는 것이다. 이유는 맵을 탐색할 때 선이 아닌 좌표 기준으로 하기 때문에 바로 연결되어 있는지 판단하기 쉬운 방법이 2배로 늘리는 것이기 때문이다. 또한 내부 사각형과 테두리값을 구분해야 문제를 풀기 쉽다. 정답 코드 imp..
https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 핵심 우리가 각각의 이모티콘을 10,20,30,40 퍼로 할인시킬 수 있다. 이때 구독자수를 최대로 하고, 이후에 가장 많은 돈을 벌게 하자. 이모티콘은 최대 7개이다. 즉 4^7가지의 경우의 수가 생기기 때문에 완전탐색을 사용하였다. 정답 코드 class Solution { static int[] discount = {10,20,30,40}; static int maxOfSubscribe; s..
https://www.acmicpc.net/problem/15559 15559번: 내 선물을 받아줘 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000, 1 < N×M ≤ 1,000,000) 둘째 줄부터 N개의 줄에는 구사과가 있는 곳의 지도가 주어진다. 지도에 쓰여 있는대로 이동했을 www.acmicpc.net dfs 문제이다. 핵심 아래 알파벳에 따라 이동하는 길이 정해져 있고, 맵의 크기를 넘어서지 않는다. 즉 무조건 사이클이 생기게 된다. 이때 생기는 사이클의 수를 구하면 된다. 사이클을 구분하기 위해 depth를 증가시키면 탐색한다. 정답 코드 import java.io.BufferedReader; import java.io.IOException; imp..
https://www.acmicpc.net/problem/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문 www.acmicpc.net dfs와 dp를 활용한 문제이다. 핵심 어떠한 발판을 밟는 순간 이후의 동작은 동일해진다. 즉 이후에 탈출을 한다면 그 발판을 밟기 전에도 탈출을 한다는 의미이다. 이러한 사실을 이용해 dp를 적용할 수 있다. 또한 방문했던 곳을 다시 방문한다면 이것은 탈출을 할 수 없다는 의미이다. 이를 활용하여 풀어보자. 정답 코드 import java.util.Scanner; public c..
https://www.acmicpc.net/problem/1374 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 우선순위 큐를 활용해야 한다. 핵심 시작 시간이 빠른 순으로 정렬 후에 우선큐에서 현재 진행 중인 강의 중 종료 시간이 가장 빠른 강의를 비교한다. 진행 중인 강의의 end값이 다음 강의 start보다 크면 강의실 개수를 1 늘리고, 큐에 다음 강의를 넣는다. 반대의 경우 강의실 1개를 제거한다. 코드를 통해 알아보자. 정답 코드 import java.io.BufferedReader..
https://www.acmicpc.net/problem/1342 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net DFS를 사용하여 풀 수 있다. 핵심 사용할 알파벳이 있느냐, 이전 알파벳이 현재 알파벳과 같으냐 이것을 정의하고 풀 수 있다. 이러한 방법을 사용하면 같은 알파벳이지만, 배열위치가 다른 것도 1번만 확인하게 된다. ex) aba' == a'ba 정답 코드 import java.util.Scanner; public class Main{ static int[] alphabet = new int[27]; ..
