[취업준비일지] - 138
(1).백준 6064번 카잉 달력은 일정한 규칙에 따라 날짜를 표기하는데
특정 날짜가 몇 번째 순서로 나타나는지를 구하고
해당 날짜가 존재하지 않을 경우 -1을 출력해야 하는 문제였다.
날짜를 카운팅 하는 방법은 좌, 우측이 둘 다 동시에 올라가며
한도에 도달한 경우 0이 아닌 1로 변경되는 방식이다.
예를 들어 10, 12의 한도가 각각 존재할 경우
10,10까지는 같이 올라가고 그 다음 숫자가 1,11이 나오며
2,12로 오른쪽 한계에 도달할 경우 3,1로 넘어가는 것이 반복된다.
간단히 말해서 둘 다 i라는 값이 증가할 경우
(i+1)%N, (i+1)%M이라는 값이라고 볼 수 있었고
i를 1씩 증가시키며 해당 값이 일치하는 것을 확인해야겠다고 생각해서 제출해보니 시간초과가 났고
도대체 뭐가 문제인가 조건을 보니 4만이라 거의 16억번까지 갈 수 있었다.
특정 조건을 대충 입력해서 보니 아래 사진과 같이 65초나 걸리는 것도 볼 수 있었다.
결국 최적화를 위해 나머지 공식을 끄적여보다가
결국은 좌, 우 한칸씩 증가할 경우만 체크하면 된다는 사실을 알 수 있었고
while문으로 접근하며 좌, 우를 더해보려고 하다가
둘 중 하나만 더하고 반대편 숫자로 나눠도 동일한 결과를 얻을 수 있다는 것을 알게 되고
M과 N 중 더 큰 숫자(1~40000까지 가능하기 때문에 4만배까지 속도 차이가 날 수 있다)를 찾고
큰 숫자를 기준으로 더해가며 체크해 훨씬 빠르게 결과를 도출해낼 수 있었다.
결과적으로 기존 65초나 걸렸던 문제도 5ms로 13000배 빨라졌다는 결과를 볼 수 있었고
5를 보고 눈을 의심하며 5ms가 맞는지 1초를 더해서 확인해보니
1005가 출력되는 것을 보고 5ms만에 처리되었다는 것을 확인할 수 있었다.
const input = `4
10 12 3 9
10 12 7 2
13 11 5 6`.split('\n')
const result = []
const lcm = (x,y) => {
const multiplied = x*y
while (y > 0) {
const temp = x
x = y
y = temp % y
}
return multiplied/x
}
const kaingCheck = (M,N,x,y) => {
const lmcValue = lcm(M,N)
for(let i = x ; i <= lmcValue ; i += M){
if((i-1) % N +1 === y){
return i
}
}
return -1
}
for(let i = 1 ; i < input.length ; i++){
const [M,N,x,y] = input[i].split(' ').map(Number)
if(M > N){
result.push(kaingCheck(M,N,x,y))
}
else{
result.push(kaingCheck(N,M,y,x))
}
}
console.log(result.join('\n'))
//수도코드
// 1.쪼개기
// 2.for문으로 각각 카잉 체크 함수에 넣어주기
// 3.받은 값을 for문으로 순회하며 해당 값이 나올 경우 return하기
// 4.가능 범위(x*y까지 순회해도 없는 경우로 하려고 했지만 1만, 1만인 경우 1억이 아닌 1만까지만 해도
// 내용 확인이 가능하기 때문에 lcm을 구하기로 했다.
// 5.시간초과로 인한 나머지 문제를 확인해보니 어차피 나눠진다고 친다면 하나의 M 또는 N을 더한 값 중 하나가 되기 때문에
// 1씩 더하는 것이 아니라 M 또는 N 중 큰 값을 더해야 했다.
// 최적화를 위해 더 M과 N중 더 큰 값을 확인해 해당 값만큼씩 더하도록 조건문도 추가했다.극단적이지만 1과 40000이 들어갈 경우 4만배의 차이가 난다.
(2).프로그래머스 바탕화면 정리는 드래그를 통해 한번에 모든 파일을 선택해야 할 때
최소로 움직이기 위한 시작과 종료 위치의 좌표를 구해야 하는 문제였다.
특이하게도 파일의 크기는 1x1이기 때문에 (0,0)의 위치에서 시작한다고 하더라도
(0,0), (0,1), (1,0), (1,1)의 네 칸을 각각 점유한다고 볼 수 있다.
파일을 선택할 때는 결국 직사각형 모양으로 선택해야 하며
좌측 상단에서 우측 하단으로 드래그 하는 것 이기 때문에
간단하게 각각의 좌표값에 들어갈 minX, minY, maxX, maxY를 구했다.
배열에도 시작점의 위치만 표기되어 있기 때문에
최소 x,y값은 max치를 넣어두고
최대 x,y값은 각각 0을 넣은 다음
시작점의 x,y 좌표를 min x,y와 비교하고
시작점의 x,y에 +1을 한 값은 max x,y와 비교해줬다.
결과적으로 모든 파일의 최소, 최대의 x,y값을 각각 구했기 때문에
그 값들을 그대로 출력해 문제를 해결할 수 있었다.
function solution(wallpaper){
let lux = wallpaper.length
let luy = wallpaper[0].length
let rdx = 0
let rdy = 0
for(let i = 0 ; i < wallpaper.length ; i++){
for(let j = 0 ; j < wallpaper[0].length ; j++){
if(wallpaper[i][j] === "#"){
lux = Math.min(lux, i)
luy = Math.min(luy, j)
rdx = Math.max(rdx, i+1)
rdy = Math.max(rdy, j+1)
}
}
}
return [lux, luy, rdx, rdy]
}