Programmers 커뮤러닝/3기/JAVA/코딩테스트 실력 UP 패키지 - 1주차_기지국
❤️ github 주소 : https://github.com/qkralswl689/programmers/tree/main/out/production/exercise
1주차_세번째 문제 : Programmers 기지국
https://programmers.co.kr/learn/courses/30/lessons/12979
- 나의 풀이
전파가 가능한 곳 0으로 표시한 배열을 생성하고, 전파하지 않은 곳을 List에 담아 비교하려했지만
초반에 기지국이 설치된 곳하고만 비교가 되어서 실패..
int[] tmp = new int[n];
for(int i = 0; i < tmp.length; i++){
tmp[i] = i+1;
}
// 전파가능한곳 0 으로 표시
for(int i = 0; i < stations.length; i++){
for(int j = 0; j < tmp.length; j++){
if(stations[i] == tmp[j]){
if(tmp[j] == 1 ){
tmp[j+w] = 0;
break;
}else if(tmp[j] == n) {
tmp[j-w] = 0;
tmp[j] = 0;
break;
}else {
tmp[j+w] = 0;
tmp[j-w] = 0;
}
tmp[j] = 0;
}
}
}
// 전파하지 않은곳 담기
ArrayList<Integer> tmp2 = new ArrayList<>();
for(int i = 0; i < tmp.length; i++){
if(tmp[i] != 0){
tmp2.add(tmp[i]);
}
}
for(int i = 0; i < tmp2.size(); i++){
int k = (tmp2.size() / 2)-1;
int q = tmp2.get(k);
if(tmp2.get(k) == q-1){
answer++;
break;
}else if(tmp2.get(k-1) != tmp2.get(k-1) -1){
int p = tmp2.get(k-1);
if(tmp2.get(0) == p-1){
answer++;
break;
}
}
break;
}
System.out.println( "answer : " + answer);
for(int num : tmp2){
System.out.println(num);
}
- 나와 비슷하게 푼 사람의 코드
나와 비슷한 방법으로 문제를 푼 사람의 코드를 참고할 수 있어서 좋았다
int answer = 0;
boolean[] apts = new boolean[n+1];
ArrayList<Integer> noSgn = new ArrayList<>();
apts[0] = true;
// 전파 터지는 아파트 표시
for (int i = 0; i < stations.length; i++) {
for (int j = stations[i] - w; j <= stations[i] + w; j++) {
try {
apts[j] = true;
}
catch (Exception e) {
continue;
}
}
}
// 안 터지는 아파트 구역별 구분
int sum = 0;
for (int i = 1; i <= n; i++) {
if (!apts[i]) {
sum += 1;
// System.out.println(i);
}
else if (apts[i] && sum != 0) {
noSgn.add(sum);
sum = 0;
}
if (i == n && sum != 0) noSgn.add(sum);
}
// 답 도출
for (int i = 0; i < noSgn.size(); i++) {
answer += (noSgn.get(i) / (w * 2 + 1));
answer += noSgn.get(i) % (w * 2 + 1) == 0 ? 0 : 1;
}
// System.out.println(noSgn.get(i));
- 강사님 풀이
처음에 Queue 로 문제풀이를 해주셔서 Queue사용법을 배울 수 있어서 좋았고, Queue를 사용했을 때엔 효율성이 떨어져
인덱스를 사용하는 방법으로 문제풀이를 해주셨다
// 아파트의 개수
int n = 11;
// 기지국이 설치된 아파트의 번호
int[] stations = {4, 11};
// 전파의 도달거리
int w = 1;
int answer = 0;
int si = 0; // 스테이션의 인덱스를 사용한다
/* // Queue 사용시 효율성 떨어짐
Queue<Integer> sq = new LinkedList<>();
for(int s : stations) sq.offer(s);*/
int position = 1; //
while (position <=n){ //아파트 전체 돌때까찌
// 인덱스가 끝까지 가지 않아있을때
if( si < stations.length && stations[si] - w <= position){
position = stations[si] + w + 1; //인덱스 번째의 값을 꺼내오고
si ++; // 인덱스 증가
}else {// 그렇지 않다면
answer += 1; // 기지국 설치
position += w + 1 + w; // 최대 전파범위(왼) + 현재위치 + 최대 전파범위(오)
// -> 전체 전파범위 == w * 2 + 1
}
}
// queue 사용시
/* while (position <=n){ //아파트 전체 돌때까찌
// Queue 가 비어있지 않은것 체크
if( !sq.isEmpty() && sq.peek() - w <= position){ // 현재 있는곳이 기지국이 있는곳의 왼쪽끝 전파범위 보다 현재위치가 오른쪽이라면 기지국의 전파범위 안에 있는것이면
position = sq.poll() + w + 1; // 위치는 기지국의 전파범위 오른쪽 끝의 다음위치로 간다
}else {// 그렇지 않다면
answer += 1; // 기지국 설치
position += w + 1 + w; // 최대 전파범위(왼) + 현재위치 + 최대 전파범위(오)
// -> 전체 전파범위 == w * 2 + 1
}
}
Author And Source
이 문제에 관하여(Programmers 커뮤러닝/3기/JAVA/코딩테스트 실력 UP 패키지 - 1주차_기지국), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@alswl689/Programmers-커뮤러닝3기JAVA코딩테스트-실력-UP-패키지-1주차기지국저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)