티스토리 뷰
728x90
https://programmers.co.kr/learn/courses/30/lessons/42842
코딩테스트 연습 - 카펫
Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과
programmers.co.kr
완전 탐색
카펫 문양의 규칙은 테두리 한줄은 brown으로 칠하고, 그 안쪽은 모두 yellow로 칠하는 것이다.
brown으로 칠해진 칸의 개수와 yellow로 칠해진 칸의 개수가 주어지면
카펫의 가로와 세로 길이를 담아 반환하는 문제
접근방법
처음에는 brown 개수와 yellow 개수를 합한 것이 카펫의 넓이니까
해당 넓이를 만족하는 가로,세로 쌍을 구하고 그 조건에서 brown 개수, yellow 개수를 구해서 주어진 값과 같으면 가로,세로를 반환하는 식으로 구현했다.
근데 풀이 후에 다른분들 코드를 보고 합을 구할 필요 없이 안쪽사각형 넓이만으로 답을 구할 수 있어서 다시 풀이했다.
yellow개수 = 안쪽 사각형 넓이. 이 넓이를 만족하는 가로,세로를 구하고(세로길이에 1부터 넓이의 제곱근까지 대입해가면서)
안쪽 사각형 가로,세로 길이에 따른 brown 개수 = 안쪽가로*2 + 안쪽세로*2 + 4(꼭짓점)
이 brown 개수가 주어진 brown 값과 일치하면 이때의 가로,세로를 배열에 담아 반환한다.
소스코드
import Foundation
func solution(_ brown:Int, _ yellow:Int) -> [Int] {
for yellowHeight in 1...Int(sqrt(Double(yellow))) {
if yellow % yellowHeight == 0 {
let yellowWidth = yellow/yellowHeight
let numOfBrown = yellowHeight*2 + yellowWidth*2 + 4
if brown == numOfBrown {
return [yellowWidth+2, yellowHeight+2]
}
}
}
return []
}
개선 풀이
import Foundation
func solution(_ brown:Int, _ yellow:Int) -> [Int] {
let sum:Int = brown + yellow
for d in 3...Int(sqrt(Double(sum))) {
if sum % d == 0 {
let r = d
let c = sum/d
let cbrown = 2*(r+c-2)
let cyellow = (r-2)*(c-2)
if brown == cbrown && yellow == cyellow {
return [c,r]
}
}
}
return []
}
최초 풀이
728x90
'알고리즘 문제풀이' 카테고리의 다른 글
[프로그래머스] 징검다리 (Swift) (0) | 2022.04.20 |
---|---|
[프로그래머스] 입국심사 (Swift) (0) | 2022.04.19 |
[프로그래머스] 가장 큰 수 (Swift) (0) | 2022.04.13 |
[프로그래머스] 여행경로 (Swift) (0) | 2022.04.08 |
[프로그래머스] 단어 변환 (Swift) (0) | 2022.04.07 |
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 자바
- c++
- 스택
- 정렬
- 다이나믹프로그래밍
- 최대힙
- 그리디알고리즘
- 게임이론
- 가장 큰 수 프로그래머스
- 수학
- dfs
- 이분탐색
- Swift
- 알고리즘
- 가장 큰 수 Swift
- dp
- BFS
- 프로그래머스
- 백트래킹
- 트리
- 파이썬
- 동적계획법
- 브루트포스
- 우선순위큐
- 최소힙
- 최단경로
- 백준
- 웹크롤링
- 투포인터
- 토마토
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
글 보관함