전체 글
프로그래머스 - (Java)입국심사
https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 1. 유형 이분탐색 2. 시뮬레이션 이분탐색과 수학적 지식이 있어야 풀 수 있는 문제다. 우선 시뮬레이션일 돌려보자. 그렇다면 위의 과정에서 28은 어떻게 구해야할까. 이분탐색이다. 로직 먼저 head, tail의 초기값을 설정 head가 tail보다 커질때까지 반복문을 돌린다 조건에 따라 mid값을 변경해준다. 3. 코드 class Solution { publi..
백준 - 1600 말이되고픈 원숭이 (Java)
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 1. 유형 DP, BFS 2. 로직 bfs를 돌리면서 조건에 맞는 경우만 큐에 넣어주기 시뮬레이션을 돌리면 위 같은 상황이 나온다. 현재 좌표에서는 이전에 말처럼 이동했는지 알수 없다. 따라서 dp[말처럼 이동 횟수][행][열]인 3차원 배열에 이동거리를 저장하고, 저장한 것 보다 더 작은 이동회수가 있을겨우만 큐에 삽입하면 된다. 3. 코드 import java.io.*; imp..
프로그래머스 - (Java) 경주로 건설
https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 1. 유형 DP, BFS 2. 로직 테스트 케이스가 약간 빈약한것 같다. 반례가 존재하..
프로그래머스 - (Java) 보석쇼핑
https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 1. 유형 해쉬맵, 큐 2. 로직 총 보석의 종류를 파악 해쉬맵에서 {보석이름, 개수}형태로 딕셔너리 생성 투포인터를 사용해서 모든 종류의 보석을 포함하고 있는 범위를 구함 gems가 아래처럼 주어졌다고 할때, ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] 위의 그림처럼 시뮬레이션을 하면 start=3, end=4가 된다. 위의 방법처럼..
프로그래머스 - (Java)단체사진 찍기
https://programmers.co.kr/learn/courses/30/lessons/1835 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 1. 유형 구현, 순열 2. 로직 순열 구하기 사람들끼리의 거리를 구한다 data배열의 조건대로 내가 구한 순열이 만족한지 판단 각 사람들끼리 떨어진 거리는 String.indexOf를 사용해서 쉽게 구할수 있었다. 3. 코드 class Solution { static char info[] = {'A', 'C', 'F', 'J', 'M', 'N', 'R', '..
프로그래머스 - (Java)땅따먹기
https://programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 1. 유형 동적프로그래밍 2. 로직 그림으로 이해 제한 조건을 잘 읽어보면 N이 100,000씩 되는걸 확인 가능하다 이러면, 부르트포스로는 4*3^(n-1)시간이 걸리고 시간초과로 실패가 뜰것이다. 제한조건을 잘 읽어보고 푸는 습관을 들이자 3. 코드 import java.util.*; class Solution { int solution(..
프로그래머스 - (Java)뉴스클러스터링
https://programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 1. 유형 해시맵, 구현 2. 로직 모두 대문자로 변환 2자리씩 끊어서 {문자열, 갯수} 형태의 딕셔너리 만든다 str1, str2의 딕셔너리의 key값으로 합집합, 교집합을 구한다 refine함수를 통해 "aa1+aa2"문자열을 {aa:2 } 해쉬맵으로 리턴해준다. 교집합 합집합은 contains라이브러리를 사용하여 판단. 3. 코드 im..
프로그래머스 - (Java) 괄호 회전하기
https://programmers.co.kr/learn/courses/30/lessons/76502 코딩테스트 연습 - 괄호 회전하기 programmers.co.kr 1. 유형 구현, 문자열, 스택 2. 로직 문자열 회전하는 코드 올바른 괄호인지 판단 [](){}문자열을 회전하면 ](){}[이 된다. 이런 문자열을 만드려면 덱 자료구조를 사용한다. 맨 앞의 엘리먼트를 빼고 맨 뒤에 추가해준다. 이것을 s의 길이만큼 반복해준다. 올바른 괄호판단은 너무 흔한 유형이고, Stack을 사용해서 판단한다 닫는 괄호가 나왔을때, stack의 맨 위의 엘리먼트가 한쌍을 이루는지 판단 만약 닫는 괄호인 경우, stack이 비어있거나, 쌍이 맞지 않으면 틀린 문자열이 된다. 3. 코드 import java.util.*..
프로그래머스 - (Java) 수식 최대화
https://programmers.co.kr/learn/courses/30/lessons/67257?language=java 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 1. 유형 구현 2. 로직 expression문자열을 숫자, 기호를 따로 파싱한다 + - * 간의 순열을 구한다. 3!밖에 안되니 그냥 하드코딩해도 된다 각 기호의 순서대로 계산한다 3. 코드 import java.util.*; class Solution { static char[] cmd = {'+', '-', '*'}; static..
프로그래머스 - (Java) 프렌즈4블록
https://programmers.co.kr/learn/courses/30/lessons/17679 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr 1. 유형 시뮬레이션 2. 로직 1) 2*2부분 빈칸으로 바꾸기 2) 빈칸만큼 아래로 내리기 3) 위의 조건을 반복 이 문제에서 그나마 구현이 어려운 부분이 빈칸만큼 내리는 코드다. 3. 코드 import java.util.*; class Solution { static char table[][]; static boolean visited..