문제 https://school.programmers.co.kr/learn/courses/30/lessons/17678?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이 문제의 요점은, 콘이 언제와야 '마지막 버스' 를 탑승할 것인가 이다. 마지막 버스에 한자리라도 남아있다면 마지막 버스시간에 오면 되고, 마지막 버스에 사람이 꽉 차 있다면 마지막 버스에, 마지막에 탄 사람 -1 분에 도착하면 된다. 처음에는 마지막 버스라는거에 꽂혀 "뒤에서 부터 살펴봐야하나?" 했는데 애초에 수가 크지도 않고, 크루가 얼마나 일찍 도..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/1835 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 어떻게 풀면 좋을까 생각하다 완탐 (순열) 밖에 없는거 같아서 그렇게 풀었다. 우선 8명이 설 수 있는 모든 경우를 모두 구한다. 파이썬은 itertools 로 순열을 굉장히 쉽게 구할 수 있는 반면, 자바는 없다고 하더라. 그래서 perm이라는 순열을 만드는 함수를 만들었고 특정 순열이 한개 만들어지면 (8명이 모두 자리를 잡고 서있다면) 조건에 부합하는지 검사하도록 했다. 해당 배치가..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 dfs 에 dp 테크닉을 조금 섞은 문제였다. 우선 경로에 따른 값 처리를 생각했다. 직선도로 같은 경우에는 방문한 칸 - 1 개였다. 만약 7칸을 방문한다면 코너와 상관없이 직선코너는 6개가 있다. 코너같은 경우에는 이전에 내가 어느 방향에서 왔는지를 기억하고, 그에 따라서 코너인지 아닌지 판단하기로 했다. 만약 왼쪽에서 오른쪽으로 왔는데 내가 갈려는 방향이 오른쪽이면 같은 방향이므로..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/67258# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 (자바로 풀이했다.) 투포인터를 활용해야하는 문제이다. 배열 크기가 10만이므로, for문 돌리면 시간초과가 나니까.. 처음에는 난 양쪽 끝에서 투포인터를 사용하면 될 줄 알았다. 그러나 이럴 경우 중간에 가장 짧은 구간이 있을경우 캐치하지 못했다. 시간이 꽤나 걸려 카카오 공식 해설을 참조해서 풀었다. 우선 set과 같은 자료구조로 몇 종류의 보석이 존재하는지 체크한다. 이후에 r포..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/64064 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 우선 banned_id 에 있는 리스트를 돌면서, 이 포맷에는 어떤 user_id 들이 들어갈 수 있을지 초기화 했다. 예시를 보자면 객 패턴에 맞는 user_id를 저장했다. 패턴에 매칭되는걸 확인하는건 우선 길이를 먼저 체크했고, *가 아닌 경우에 문자열이 같은지 확인했다. 이후에는 dfs를 통해서 모든 경우의 수를 만들어보았다. 단, 배열에 중복된 요소는 들어가지 않게 말이다. 결..

문제 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 풀이 요구사항과 조건이 굉장히 많은 구현 문제다. 풀이를 하다보면 놓치는 부분이 많을것이라고 생각하여서 우선 요구사항을 내가 이해하기 편하도록 작성했고, 그에 따른 슈도코드나 솔루션도 생각나는대로 작성했다. 해당 문제의 큰 흐름을 확인해보자. 존재하는 블록그룹을 확인한다. 우선 탐색은 bfs로 가정한다. 블록그룹은 우선 무지개블록, 검은블록이 아닌 일반블록이 하나는 있어야한다. 또한 기준..

문제 https://www.acmicpc.net/submit/20058/63063274 로그인 www.acmicpc.net 풀이 해당 문제는 각 격자를 l의 값에 따라 잘 나누고, 접근해서 로직만 잘 수행하면 풀 수 있는 문제이다. 그 외에 배열 회전, 얼음 감소, 가장 큰 대륙 찾기등 부가적인 요소는 간단하게 해결할 수 있다. 예시를 보자. n이 8, l이 1일때는 64 / 4 => 16개의 격자가 생긴다. n이 8, l이 2일때는 64 / 16 => 4개의 격자가 생긴다. 이 값은 (2^n)^2 / (l^2)^2 라는 공식으로 얻을 수 있다. 이후에는 각 격자에 접근한다음에, 배열을 회전해줘야한다. 위와 같이 4군데에 접근해야하고 각 격자에 해당하는 부분만 탐색해야한다. 처음에 x, y는 0으로 시작..

문제 https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 풀이 꽤나 무식하게 풀이했다. 토네이도가 회전하는 방식 구현 단순하게 사진보고 유추했다. 1의 길이가 2번 반복, 2의 길이가 반복.. 그러다 n-1의 길이는 3번 반복되더라. 반복되면서 방향은 계속 바뀌고.. 보이는 대로 구현했다. 밑의 사진을 보면 이해가 좀 더 쉽다. 회전된 비율 배열 4방향이니까, 그냥 회전해서 좌표를 다 구하는 방식으로 했다. 사실 좀..

문제 https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 풀이 각 칸에 파이어볼을 정보를 담고있는 리스트를 요소로 가지는 2차원 배열을 선언한다. [[ [m1, s1, d1], [m2, s2, d2] ..] ] , [ [m3, s3, d3] ] , .... ] [[ [m4, s4, d4] ], .... 와 같은 형태로 칸에 접근해서 반복문을 돌림으로써 모든 파이어볼의 정보를 알 수 있는 구조로 말이다. 이후에..

문제 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 풀이 구현 + 완전탐색 문제다. 처음에는 greedy로 시도해봤으나, 맞지않았고 완탐이 맞았다. 재귀로 구현했는데, 스케일이 굉장히 큰 재귀라.. 굉장히 까다로웠다. 흐름자체는 간단하다. 물고기 작은 순서대로 swap 실행 나는 dictionary를 활용하여 [물고기번호] = [좌표] 식으로 저장했고, 번호순으로 오름차순 정렬하여 작은 물고기부터 swap할 수 있도록 구성했..