이번에도 lv.0 문제인데 게다가 또 HashMap을 사용했다...
뭔가 레벨이 낮은 문제일수록 Map을 사용하기가 쉽달까.. 그만큼 어렵지 않은 문제라 그런가...
일단 시작해보자
문제
로그인하는 문자열을 담은 배열과 db에 저장되어있는 2차원 배열이 주어진다.
각 조건에 맞는 문자열을 리턴해주면 되는 문제다.
(제한 사항에는 딱히 문제가 있을 것 같지는 않다.)
입출력 예는 위와 같이 주어진다.
문제 풀이
일단 Map 부터 만들어 주도록 하겠다.
class Solution {
public String solution(String[] id_pw, String[][] db) {
HashMap<String, String> newMap = new HashMap<>();
for(String[] newDB : db) {
newMap.put(newDB[0],newDB[1]);
}
}
}맵의 Key는 id_pw 를 담은 배열에서 각각 id가 Key를 pw가 Value를 담당한다.
맵을 다 만들었다면 로그인 하는 1차원 배열을 가지고 Map에 접근하여 조건을 만족하는 값을 return해주면 된다.
class Solution {
public String solution(String[] id_pw, String[][] db) {
if (newMap.containsKey(id_pw[0])){
if(newMap.get(id_pw[0]).equals(id_pw[1])) {
return "login";
} else {
return "wrong pw";
}
} else {
return "fail";
}
}
}첫 번째 조건문의 경우 Id가 DB내에 존재하는지 부터 판단하도록 한다.
첫 번째 조건문이 만족하였다면 해당 Key를 토대로 Value에 접근하고 해당 Value와 pw가 일치하는지 판단하여 일치 한다면 login 아니라면 wrong pw를 return한다.
마지막으로 모두 일치하지 않는 경우 fail을 return하여 원하는 결과를 출력하도록 한다.
전체 코드
import java.util.*;
class Solution {
public String solution(String[] id_pw, String[][] db) {
HashMap<String, String> newMap = new HashMap<>();
for(String[] newDB : db) {
newMap.put(newDB[0],newDB[1]);
}
if (newMap.containsKey(id_pw[0])){
if(newMap.get(id_pw[0]).equals(id_pw[1])) {
return "login";
} else {
return "wrong pw";
}
} else {
return "fail";
}
}
}시간 복잡도
HashMap
일단 왜 hashMap을 또 썼느냐에 대해 얘기해보자면
이 문제와는 다른 케이스 이지만 만약 배열의 크기가 다를 경우도 고려해보자
2차원 배열에서 N은 전체 원소의 개수를 의미하고, 배열의 크기가 m x n이라면, 전체 원소의 수는 𝑚×𝑛 가 된다.
2차원 배열의 경우 순회를 하기 위해 반복문이 두 번 중첩되어야 하는데 이 경우에 시간복잡도는 최대 O(MN)까지 올라 갈 수 있다.
물론 단순 코딩에야 문제가 없을 수 있지만 결국 코테는 얼마나 최적화된 알고리즘을 짜느냐도 결과에 반영이 되는 경우가 많기 때문에 HashMap을 사용했다.
이 문제에 대해서
시간 복잡도에서 얘기해보도록 하자
위에서 시간 복잡도를 고려하여 HashMap을 사용했다고 했는데
일단 map을 만들기 위해서 배열 전체를 순회하기 때문에 O(N)
map에 접근하는 것은 상수시간 (1)
작성한 코드는 상수시간에 가까운 O(N)을 가진다.
반복문만 사용한 경우
그렇지만 만약에 반복문만 사용했다면 어떻게 될까?
map을 만들 때 처럼 반복문을 하나만 사용해서 순회가 가능하고 id_pw의 배열과 비교도 가능해질 것이다.
그렇다면 결국 배열의 크기가 N이고 최악의 경우도 N이 되므로 반복문만 사용했을 경우에도 역시 O(N)의 시간 복잡도를 가진다.
결론
겉보기에는 두 방식 모두 시간 복잡도는 O(N)으로 보일 수 있지만, HashMap을 사용하면 상수 시간 조회로 인해 실질적인 성능 차이가 발생하며 데이터의 크기가 많아질수록 Map의 성능이 향상된다.
반복문만 사용한 경우
맵을 사용한 경우
위의 사진과 같은 경우 제한사항에서의 DB가 매우 작기 때문에 오히려 Map이 시간적으로 손해이지만
만약 DB의 크기가 더 커진다면 다른 결과가 나올 것이라고 생각된다.
// 반복문 코드
class Solution {
public String solution(String[] id_pw, String[][] db) {
// id_pw 배열에서 아이디와 비밀번호 추출
String inputId = id_pw[0];
String inputPw = id_pw[1];
// db 배열을 순회하며 아이디와 비밀번호를 비교
for (int i = 0; i < db.length; i++) {
String dbId = db[i][0];
String dbPw = db[i][1];
if (dbId.equals(inputId)) { // 아이디가 일치하면
if (dbPw.equals(inputPw)) { // 비밀번호도 일치하면
return "login";
} else { // 비밀번호가 일치하지 않으면
return "wrong pw";
}
}
}
// 아이디가 없는 경우
return "fail";
}
}