쵼쥬
쵼쥬의 개발공부 TIL
쵼쥬
전체 방문자
오늘
어제
  • 분류 전체보기 (276)
    • 코딩테스트 (192)
      • [알고리즘] 알고리즘 정리 (7)
      • [백준] 코딩테스트 연습 (126)
      • [프로그래머스] 코딩테스트 연습 (59)
    • Spring (71)
      • [인프런] 스프링 핵심 원리- 기본편 (9)
      • [인프런] 스프링 MVC 1 (6)
      • [인프런] 스프링 MVC 2 (4)
      • [인프런] 실전! 스프링 부트와 JPA 활용1 (7)
      • [인프런] 실전! 스프링 부트와 JPA 활용2 (5)
      • [인프런] 실전! 스프링 데이터 JPA (7)
      • [인프런] 실전! Querydsl (7)
      • JWT (5)
      • [인프런] Spring Cloud (17)
      • [인프런] Spring Batch (4)
    • Java (6)
      • [Java8] 모던인자바액션 (4)
      • [부스트코스] 웹 백엔드 (2)
      • [패스트캠퍼스] JAVA STREAM (0)
    • CS (6)
      • 디자인 패턴과 프로그래밍 패터다임 (2)
      • 네트워크 (4)

블로그 메뉴

  • 홈

공지사항

인기 글

태그

  • Spring Data JPA
  • 타임리프
  • MVC
  • spring
  • 부스트코스
  • BFS
  • 프로그래머스
  • 스프링
  • 자바
  • 비트마스킹
  • 백분
  • 위클리 챌린지
  • jpa
  • querydsl
  • 인프런
  • 코딩테스트
  • 누적합
  • 구현
  • 알고리즘
  • 백준

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
쵼쥬
코딩테스트/[프로그래머스] 코딩테스트 연습

전화번호 목록

코딩테스트/[프로그래머스] 코딩테스트 연습

전화번호 목록

2021. 7. 9. 20:55

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

  • 구조대 : 119
  • 박준영 : 97 674 223
  • 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

  • phone_book의 길이는 1 이상 1,000,000 이하입니다.
    • 각 전화번호의 길이는 1 이상 20 이하입니다.
    • 같은 전화번호가 중복해서 들어있지 않습니다.

 

입출력 예제

 

phone_book return
["119", "97674223", "1195524421"] false
["123","456","789"] true
["12","123","1235","567","88"] false

 

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

 

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

 

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

 


푸는 방법 생각

해시 문제로 나와있는데 해시를 이용한 방법이 감이 안잡혀 주어진 배열을 이용해 2중 반복문을 사용해서 풀이했다. 문자열을 비교하기 위해 subString을 생각했지만 접두사를 비교하는 startsWith 함수가 있다는 것을 이번에 알게되서 적용해보았다. 접두사뿐만 아니라 접미사로는 endsWith 함수도 있다.

 

내 코드

class Solution {
    public boolean solution(String[] phone_book) {

        for(int i  = 0; i < phone_book.length - 1; i++){
            for(int j = i + 1; j< phone_book.length;j++){
                if(phone_book[j].startsWith(phone_book[i]))
                    return false;
                if(phone_book[i].startsWith(phone_book[j]))
                    return false;
            }
        }
        return true;
    }
}

 

다른 사람 풀이

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phone_book) {
            HashMap<String, Integer> hashMap = new HashMap<>();

            for (String number : phone_book) hashMap.put(number, 0);
            for (String key : hashMap.keySet())
                for (int j = 1; j <= key.length() - 1; j++)
                    if (hashMap.containsKey(key.substring(0, j))) return false;
            return true;
    }
}

다른 사람 풀이를 통해 해시를 이용한 방법을 알게 되었다. key값으로 hashMap에 전화번호를 넣고 value로는 0을 넣었다. 다음 for문을 이용해 hashMap에 있는 전화번호(key)를 가져와 substring으로 각 key마다 앞에서부터 하나씩 추가하고 containsKey를 이용해 접두사인지 확인했다.

value에 0을 주고 사용하지 않을거면 HashMap이 아닌 HashSet을 이용해도 될 것 같다.

'코딩테스트 > [프로그래머스] 코딩테스트 연습' 카테고리의 다른 글

H-Index  (0) 2021.07.12
가장 큰 수  (0) 2021.07.12
K번째수  (0) 2021.07.09
위장  (0) 2021.07.09
완주하지 못한 선수  (0) 2021.07.08
    '코딩테스트/[프로그래머스] 코딩테스트 연습' 카테고리의 다른 글
    • 가장 큰 수
    • K번째수
    • 위장
    • 완주하지 못한 선수
    쵼쥬
    쵼쥬

    티스토리툴바

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.