220630_w3_랜덤유형 - Sunny-W-Park/elice-sw2-algorithms GitHub Wiki
박선우 -
문제 해석
접근
풀이 과정
주지호 -프로그래머스- 오픈채팅방
문제 해석
- 마지막으로 변경된 해당 아이디의 닉네임을 반영해서, 최종적으로 보여질 메세지를 리턴하는 문제
접근
- 딕셔너리에서 해당 아이디의 마지막으로 선언된 닉네임을 할당 후, enter와 leave인 레코드에 반영해주기만 하면 되는 간단한 문제
풀이 과정
- record 안의 값들을 검사하여, 아이디의 닉네임이 변경되거나 (Change), 처음으로 아이디의 닉네임을 볼 수 있는 (Enter) 상황만 검사 후 딕셔너리에 {id : 닉네임} 으로 할당.
- 그 후, 다시한번 record를 순회하며 enter, leave 시 해당 id의 닉네임값을 할당 후 문자열을 리턴
지의신 - 프로그래머스 - 입국심사 이분탐색
문제 해석
- 모든 사람이 심사를 받는 최소의 시간을 구하는 것이다.
- 사람 수 n, 그리고 심사관 한명이 사람한명을 심사하는데 걸리는 시간이 담긴 배열 times가 주어진다. 배열의 길이는 심사원의 수가 된다.
- 심사원은 한번에 한명의 사람만 심사할 수 있으며, 심사원은 1명이상이다.
접근
- 이분탐색으로 범위를 반씩 좁혀가면서 최소의 시간의 값을 구한다.
- 처음 시작하는 범위는, 심사관 한명이 사람한명을 심사하는데 걸리는 시간중 가장 큰 값 * 사람수 이다.
- left, right, mid 변수를 사용하여 범위를 줄여나가자.
풀이 과정
- n(사람수), times 배열이 입력으로 주어진다.
- left는 0, right에는 n(사람수)* max(times)를 대입한다.
- while문을 돈다. 조건은 left <= right 이다.
- mid = left+right // 2로 대입하고, 심사받은 사람의 인원인 people이라는 변수를 0으로 초기화했다.
- times를 순회하면서, 심사받은 사람의 인원(people)을 갱신한다. people이 n보다 크다면, 순회를 멈추고 범위를 반으로 줄인다.
- 순회가 끝났다면, 두가지 경우가 있다.
- people >= n 인경우에는 answer를 mid로 갱신하고, right = mid-1로 범위를 줄인다.
- people < n 인경우에는 answer를 갱신하지 않는다. 왜냐하면 사람수 조건이 부합하지 않기 때문이다. 그리고 left = mid+1로 범위를 좁힌다.
- 갱신된 answer를 리턴하면 된다.
백성호 - 프로그래머스 - 3xn 타일링
문제 해석
- 가로의 길이가 2이고 세로의 길이가 1인 타일이 있을 때, 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 체워야한다.
- 이 때, 타일을 가로/세로로 배치하여 채울 수 있다.
- 가로의 길이 n이 주어졌을 때, 직사각형을 채우는 경우의 수를 1,000,000,007으로 나눈 나머지를 return하는 함수를 작성해야 한다 (n=< 5000 자연수)
접근
- dp 문제이므로 dp 배열을 만들어서 풀이
- n이 홀수일 경우, 3*홀수 = 홀수이므로 2x1타일로 채우는 것이 불가능하므로, 홀수 n만 고려
- dp(n-2)에 2*3을 채우는 경우는 3가지 방법으로 채울 수 있으므로 기본적으로 dp(n) = dp(n-2)*3
- 특이 케이스인 (세로+(가로*2) + 세로) 인 경우가 dp[0]부터 dp[n-4]까지 각각 2가지로 존재. 따라서 이 부분도 경우의 수에 추가 해야 함.
풀이 과정
- dp를 5001개의 0으로 이루어진 배열로 정의
- dp[0]=1, dp[2]=3으로 기본 값 설정
- dp[4]부터 dp[n]까지 짝수만 for 문으로 dp 계산
- dp[i] = dp[i-2]*3%1000000007
- dp[0] 부터 dp[i-4]까지 짝수만 for 문으로 특이 케이스 dp에 더하기
- dp[i]+=dp[j]*2%1000000007
- 마지막 결과 값이 1000000007를 초과 할 수도 있으니 다시 나머지 적용
- dp[n] return