전체 글 (37) 썸네일형 리스트형 프로그래머스_기둥과 보 설치_60061 문제 링크 조건 n : 2차원 벽면의 크기 (n x n), 범위는 5~100 이하의 자연수 기둥과 보를 설치(삭제)하는 데, 조건에 위배되면 설치(삭제) 작업명령을 무시함 기둥 : 바닥 위 or 보의 한쪽 끝 부분 위 or 다른 기둥 위 에만 설치 가능 보 : 한쪽 끝 부분이 기둥 위 or 양쪽 끝 부분이 다른 보와 동시에 연결된 경우에만 설치 가능 작업명령 배열 [x, y, a, b] : [가로좌표, 세로좌표, 구조물 종류, 설치or삭제] 로 주어짐 접근 방법 처음에 설치 시 구조물별 조건과 삭제 시 구조물별 조건을 따로 생각해 작업 명령에 따라 매번 조건을 확인하는 식으로 접근 => 테스트케이스 몇 개 씩 계속 틀림.. 문제에는 설치 시 조건만 나와있음 구조물 삭제 시 조건에서 놓친 부분이 있어 테스.. 프로그래머스_가장 긴 팰린드롬_12904 문제 링크 조건 s : 입력 문자열, 소문자로만 구성, 길이 2500이하 주어진 s 문자열에서 가장 긴 팰린드롬(앞뒤를 뒤집어도 똑같은 문자열) 찾기 접근 방법 1. 완전탐색 - s의 길이가 2500 이하 => O(N3)이어도 1초 이하 - 가장 긴 팰린드롬을 찾아야 하기 때문에 긴(s 문자열의 길이) 경우부터 탐색 2. DP - s의 길이가 더 커질 경우 DP가 안전하다 생각 - dp[i][j] = true : s 문자열에서 i~j까지의 substring이 팰린드롬임을 뜻함 솔루션 1. 완전탐색 public int solution(String s) { int len = s.length(); int answer = len; int f, b; top: for(int i = answer; i > 0; i--.. 프로그래머스_스킬트리_49993 문제 링크 조건 선행스킬 조건 적용 : 스파크 -> 라이트닝 볼트 -> 썬더와 같이 배우는 순서가 정해져 있는 스킬들이 있음 스킬은 알파벳 대문자로 표기 skill : 선행 스킬 순서, 길이 1~26 skill_trees : 스킬을 나타내는 문자열, 길이 2~26 접근 방법 26개의 알파벳 길이에 맞게 int 배열을 선언해 주어진 skill 정보로 선행스킬순서를 저장 주어진 선행 스킬 순서대로 학습하고 있는지 확인하기 위해 skillCnt 이름의 int 변수 활용 솔루션 class Solution { public int solution(String skill, String[] skill_trees) { int[] check = new int[26];//선행스킬 순서 int answer = 0; for(i.. 프로그래머스_방의개수_49190 문제 링크 조건 (0,0)에서 시작, 8방으로 이동 가능 arrows : 이동 방향을 담은 배열 (길이 1 ~ 100,000 | 범위 0 ~ 7) 방은 다른 방으로 둘러 싸여질 수 있음 접근 방법 최대 10만번 이동이 가능 => col, row 최대 -10만 ~ 10만 범위 => 배열 불가능 => HashSet 사용 이미 찍혀있던 정점에 도달하거나, 대각선으로 이동할 때 반대 대각선을 통과할 경우 새로운 방이 만들어짐 주의 : 정점(Point) 객체와 간선(Edge) 객체를 만들고, 각 객체를 HashSet에 저장할 때 같은 객체임을 나타내는 조건을 재정의해야함 equals, hashCode 메소드 Override 필요 솔루션 import java.util.*; /* arrows 배열 따라서 선을 그린다.. 프로그래머스_호텔 방 배정_64063 문제 링크 조건 K - 전체 방 개수(1 ~ 10^12) room_number - 고객이 원하는 방 번호 : length 1~200,000 / 범위 1 ~ K 접근 방법 Union Set으로 이미 배정된 방들 중 붙어있는 방 끼리 Union 처리 K의 범위가 long type이기 때문에 방마다의 parent 정보 를 배열로 저장할 수 X => HashMap 사용 주의 : 이미 배정한 방일 경우 아직 배정하지 않은 방 중 가장 작은 방 번호를 탐색해야 함 => findSet => 여기서 기존 배정한 방들의 parent 정보를 계속 갱신해줘야 이후의 findSet 탐색이 빨라짐 솔루션 import java.util.*; /* union set!!! if - hashmap에 고객이 요청한 방 번호가 있다면 =.. 이전 1 2 3 4 5 다음