프로그래머스

프로그래머스 - 미로탈출

1. 문제 문제 설명 1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다. 미로를 나타낸 문자열 배열 ma..

프로그래머스 - 시소짝꿍

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/152996# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 접근방식 구현 + 계수정렬을 이용해 접근하면 된다. 계수정렬이란? 입력 배열의 원소값을 계수하여 새 배열에 누적합으로 담아 정렬하며 값 비교없이 수행하는 정렬방법이다. 사용 가능한 조건은? 원소 값이 양의 정수인 경우 원소 최대값의 자리수가 작을 경우 -> 해당 문제에선 weights의 값 범위가 100~1000으로 작음 구현시 주의해야 할점은? 무게값이 같은 경우 -> 예를 ..

프로그래머스 - 숫자 변환하기

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/154538# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 접근 방식 처음에 dfs로 접근을 시도하다 최소값을 찾는 조건을 다시 한번 확인하고 bfs로 바꿨다. 뭔가 계속 풀릴듯 안 풀릴듯 헤매다 결국 다른 사람의 정답을 보고 dp + bfs로 접근해야 함을 알게 됐다. dp만 잘 사용하면 굳이 bfs 방식으로 접근할 필요도 없을 듯하다. 가장 중요한 점은 dp를 활용하는 것이다. y+1크기의 배열에 연산을 한 결과값을 인덱스로하는 원..

프로그래머스 - 뒤에 있는 큰 수 찾기

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/154539 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 접근 방식 단순히 이중 for문으로 접근하면 시간 초과가 발생하는 케이스가 있다. 당연하겠지만.. 이 문제의 해결법은 2중 for문의 시간을 단축시키는데 있다. 핵심은 다음과 같다. 테케를 예로 들면 아래와 같은 배열에서 9 1 5 3 6 2 answer의 2,3번째 인덱스의 값이 6임을 알 수 있다. 즉, 큰 수가 나올 때까지 탐색을 하고, 그 사이의 모든 수들의 뒷 큰수 값은..

프로그래머스 - 무인도 여행

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 접근방식 전형적인 dfs, bfs방식의 문제다. 처음 접근은 dfs로 진행하고 시간초과로 틀릴 경우 bfs로 접근하려고 했는데 다행히 한번에 합격했다. String배열로 온 maps를 int배열로 바꿔준다. (X->0으로 바꿔서 넣어주기.굳이 0이 아니어도 상관은 없다. 구별가능한 다른 숫자면 무엇이든 가능) 방문한적이 없고(!visited) , 바다이지 않은 경우(map[i][..

프로그래머스 호텔대실 자바

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/155651 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 접근 방식 해당 문제의 시간을 시, 분 따로 나눠서 범위를 정하면 문제가 꽤나 복잡해진다. 그래서 (시간 * 60분 + 분)으로 전체시간을 분으로 변환 해주고 입실~퇴실 범위에 값을 누적해주면된다. 다만 매번 입실~퇴실 시간의 범위에 반복문을 돌려 값을 누적하기엔 시간복잡도가 증가한다. 입실 시간엔 +1, 퇴실 시간엔 -1의 값을 대입해 준 뒤 배열을 누적합 해주고 최대값을 반환..