Open Chat Room
프로그래머스 코딩테스트 연습
2019 KAKAO BLIND RECRUITMENT > 오픈채팅방
JAVA
문제 설명
오픈채팅방
카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다.
신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다.
“[닉네임]님이 들어왔습니다.” 채팅방에서 누군가 나가면 다음 메시지가 출력된다. “[닉네임]님이 나갔습니다.” 채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다.
- 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다.
- 채팅방에서 닉네임을 변경한다.
닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다.
예를 들어, 채팅방에 “Muzi”와 “Prodo”라는 닉네임을 사용하는 사람이 순서대로 들어오면 채팅방에는 다음과 같이 메시지가 출력된다.
“Muzi님이 들어왔습니다.” “Prodo님이 들어왔습니다.”
채팅방에 있던 사람이 나가면 채팅방에는 다음과 같이 메시지가 남는다.
“Muzi님이 들어왔습니다.” “Prodo님이 들어왔습니다.” “Muzi님이 나갔습니다.”
Muzi가 나간후 다시 들어올 때, Prodo 라는 닉네임으로 들어올 경우 기존에 채팅방에 남아있던 Muzi도 Prodo로 다음과 같이 변경된다.
“Prodo님이 들어왔습니다.” “Prodo님이 들어왔습니다.” “Prodo님이 나갔습니다.” “Prodo님이 들어왔습니다.”
채팅방은 중복 닉네임을 허용하기 때문에, 현재 채팅방에는 Prodo라는 닉네임을 사용하는 사람이 두 명이 있다. 이제, 채팅방에 두 번째로 들어왔던 Prodo가 Ryan으로 닉네임을 변경하면 채팅방 메시지는 다음과 같이 변경된다.
“Prodo님이 들어왔습니다.” “Ryan님이 들어왔습니다.” “Prodo님이 나갔습니다.” “Prodo님이 들어왔습니다.”
채팅방에 들어오고 나가거나, 닉네임을 변경한 기록이 담긴 문자열 배열 record가 매개변수로 주어질 때, 모든 기록이 처리된 후, 최종적으로 방을 개설한 사람이 보게 되는 메시지를 문자열 배열 형태로 return 하도록 solution 함수를 완성하라.
[제한사항]
- record는 다음과 같은 문자열이 담긴 배열이며, 길이는 1 이상 100,000 이하이다.
- 다음은 record에 담긴 문자열에 대한 설명이다.
- 모든 유저는 [유저 아이디]로 구분한다.
- [유저 아이디] 사용자가 [닉네임]으로 채팅방에 입장 - “Enter [유저 아이디] [닉네임]” (ex. “Enter uid1234 Muzi”)
- [유저 아이디] 사용자가 채팅방에서 퇴장 - “Leave [유저 아이디]” (ex. “Leave uid1234”)
- [유저 아이디] 사용자가 닉네임을 [닉네임]으로 변경 - “Change [유저 아이디] [닉네임]” (ex. “Change uid1234 Muzi”)
- 첫 단어는 Enter, Leave, Change 중 하나이다.
- 각 단어는 공백으로 구분되어 있으며, 알파벳 대문자, 소문자, 숫자로만 이루어져있다.
- 유저 아이디와 닉네임은 알파벳 대문자, 소문자를 구별한다.
- 유저 아이디와 닉네임의 길이는 1 이상 10 이하이다.
- 채팅방에서 나간 유저가 닉네임을 변경하는 등 잘못 된 입력은 주어지지 않는다.
입출력 예
입출력 예에 대한 설명
입출력 예1) 문제의 설명과 같다.
문제 풀이
먼저, 사람들의 상태(“Enter”, “Leave”, “Change”)와 아이디, 닉네임을 저장할 수 있는 클래스 User를 만들었습니다.
코드는 다음과 같습니다.
static class User {
private String state;
private String id;
private String nickname;
public User(String state, String id, String nickname) {
this.state = state;
this.id = id;
this.nickname = nickname;
}
public String getState() {
return state;
}
public void setState(String state) {
this.state = state;
}
public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
public String getNickname() {
return nickname;
}
public void setNickname(String nickname) {
this.nickname = nickname;
}
}
클래스를 먼저 만든 후에 로직을 만들었습니다.
List
(1) 파라미터로 받은 Record 배열을 하나씩 읽습니다. (2) String 클래스의 split(“ “) 함수를 이용해 문자열 (예: ”Enter uid1234 Muzi”)을 쪼개 각각 지역 변수 state, id, nickname에 저장합니다. (3) state에 따라 로직을 분리합니다. (4) state가 “Enter”이면, ArrayList userList에서 id가 같은 객체가 있으면, 동일한 id의 nickname을 새로운 nickname으로 모두 업데이트 해줍니다. (이전에 나간 유저가 닉네임을 새로 바꿔서 들어왔을 경우 대비) 이후, state, id, nickname으로 새로운 User 객체를 생성해 ArrayList userList에 add합니다. (5) state가 “Leave”이면, state, id, nickname으로 새로운 User 객체를 생성해 ArrayList userList에 add합니다. (6) state가 “Change”이면, ArrayList userList에서 동일한 id를 가진 객체를 모두 찾아, 새로운 닉네임으로 업데이트 해줍니다.
위 로직의 코드는 아래와 같습니다.
List<User> userList = new ArrayList<>();
// (1)
for (String rec : record) {
// (2)
String[] strings = rec.split(" ");
String state = strings[0];
String id = strings[1];
String nickname = null;
try {
nickname = strings[2];
} catch (IndexOutOfBoundsException e) {
for (User user : userList) {
if (user.getId().equals(id)) {
nickname = user.getNickname();
}
}
}
// (3)
switch (state) {
// (4)
case "Enter": {
for (User user : userList) {
if (user.getId().equals(id)) {
user.setNickname(nickname);
}
}
User user = new User(state, id, nickname);
userList.add(user);
break;
}
// (5)
case "Leave": {
User user = new User(state, id, nickname);
userList.add(user);
break;
}
// (6)
case "Change":
for (User user : userList) {
if (user.getId().equals(id)) {
user.setNickname(nickname);
}
}
break;
}
}
이제 인자로 Record 배열을 모두 순회했으니, ArrayList userList를 차례대로 읽어가면서 해당 user 객체의 state가 “Enter”이면 user.getNickname() + “님이 들어왔습니다.” 문자열을 반환해주고, 해당 user 객체의 state가 “Leave”이면 user.getNickname() + “님이 나갔습니다.” 문자열을 반환해줍니다.
구현한 코드는 아래와 같습니다.
for (User user : userList) {
if (user.getState().equals("Enter")) {
String message = user.getNickname() + "님이 들어왔습니다.";
result[i++] = message;
} else if (user.getState().equals("Leave")) {
String message = user.getNickname() + "님이 나갔습니다.";
result[i++] = message;
}
}
return result;
전체 코드는 아래와 같습니다.
public class OpenChatRoom {
public static void main(String[] args) {
String[] record = {"Enter uid1234 Muzi", "Enter uid4567 Prodo", "Leave uid1234", "Enter uid1234 Prodo", "Change uid4567 Ryan"};
System.out.println(Arrays.toString(solution(record)));
}
public static String[] solution(String[] record) {
List<User> userList = new ArrayList<>();
for (String rec : record) {
String[] strings = rec.split(" ");
String state = strings[0];
String id = strings[1];
String nickname = null;
try {
nickname = strings[2];
} catch (IndexOutOfBoundsException e) {
for (User user : userList) {
if (user.getId().equals(id)) {
nickname = user.getNickname();
}
}
}
switch (state) {
case "Enter": {
for (User user : userList) {
if (user.getId().equals(id)) {
user.setNickname(nickname);
}
}
User user = new User(state, id, nickname);
userList.add(user);
break;
}
case "Leave": {
User user = new User(state, id, nickname);
userList.add(user);
break;
}
case "Change":
for (User user : userList) {
if (user.getId().equals(id)) {
user.setNickname(nickname);
}
}
break;
}
}
String[] result = new String[userList.size()];
int i = 0;
for (User user : userList) {
if (user.getState().equals("Enter")) {
String message = user.getNickname() + "님이 들어왔습니다.";
result[i++] = message;
} else if (user.getState().equals("Leave")) {
String message = user.getNickname() + "님이 나갔습니다.";
result[i++] = message;
}
}
return result;
}
static class User {
private String state;
private String id;
private String nickname;
public User(String state, String id, String nickname) {
this.state = state;
this.id = id;
this.nickname = nickname;
}
public String getState() {
return state;
}
public void setState(String state) {
this.state = state;
}
public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
public String getNickname() {
return nickname;
}
public void setNickname(String nickname) {
this.nickname = nickname;
}
}
}
코드를 모두 구현하여, IntelliJ에서 하나의 테스트케이스를 돌려 예상된 결과를 얻어냈으나, Programmers에서는 시간 초과 문제로 실패하고 말았습니다…
다른 사람들의 코드를 살펴보니, Class를 사용한 경우는 거의 없고 대부분 HashMap을 사용했습니다. 저도 처음에는 HashMap을 생각했으나, “Enter uid1234 Muzi” 다음과 같이 3개의 정보를 저장하기 위해서는 Class를 사용하는 게 낫다고 판단하였습니다. 그런데, 굳이 3개의 정보를 한꺼번에 저장할 필요는 없다는 걸 깨달았습니다. 그래서 Class를 사용하지 않고, HashMap과 ArrayList로 다시 구현해 보았습니다.
물론, Class를 이용해서도 문제를 풀 수 있겠지만, 위 코드의 결정적인 문제는 “시간 초과”였습니다. 아직 알고리즘 공부가 많이 부족해, 시간복잡도 문제는 고려하지 않은 채 코드를 구현하기에만 급급했는데, 처음 “시간초과” 문제로 통과하지 못하고 보니 이런 부분도 신경 써야겠다고 느꼈습니다.
제가 구현한 코드를 다시 살펴보니 for 문 안에 for 문이 있는 코드가 2군데나 있었습니다. 즉, 이중 for 문은 O(n^2)의 시간 복잡도로 되도록이면 지양해야 합니다. 아래는 이중 for 문을 사용한 부분을 표시한 것입니다.
for (String rec : record) {
...
try {
nickname = strings[2];
} catch (IndexOutOfBoundsException e) {
for (User user : userList) {
if (user.getId().equals(id)) {
nickname = user.getNickname();
}
}
}
...
switch (state) {
case "Enter": {
for (User user : userList) {
if (user.getId().equals(id)) {
user.setNickname(nickname);
}
}
}
...
}
문제 풀이 (개선)
새로 구현한 코드에서는 Class 대신에 HashMap을 사용하였고, 이중 for 문을 사용하지 않았습니다.
새로 만든 로직은 다음과 같습니다.
먼저, 아이디와 닉네임을 따로 저장하기 위한 HashMap과 파라미터 정보를 그대로 저장하기 위한 ArrayList를 만들었습니다.
Map<String, String> userMap = new HashMap<>();
List<String[]> log = new ArrayList<>();
(1) 인자로 받은 String[] record를 순회하면서 (2) split() 함수 이용하여 문자열을 자른다. ex) “Enter uid1234 Muzi” 에 split 함수를 적용하면 { “Enter”, “uid1234”, “Muzi” } 배열이 반환됩니다. (3) 앞 부분이 “Enter”이면, userMap에 <아이디:닉네임> 저장하고 log에 split 한 후 반환된 배열을 ex) { “Enter”, “uid1234”, “Muzi” } 통째로 저장합니다. **(4)** 앞 부분이 “Leave”이면, log에 배열 ex) { “Leave”, “uid1234” }을 저장합니다. **(5)** 앞 부분이 “Change”이면, userMap에 <아이디, 닉네임>을 저장합니다. 어차피 HashMap은 key 값의 중복을 허용하지 않기 때문에 이미 존재하는 아이디(key값)가 있을 경우 닉네임을 새로 업데이트 해줍니다.
(6) String[] record 순회가 끝났으면, (문제 예시대로라면) log에 다음과 같이 저장이 되어 있을 것입니다. [ {“Enter”, “uid1234”, “Muzi”}, {“Enter”, “uid4567”, “Prodo”}, {“Enter”, “uid1234”, “Prodo”}, {“Change”, “uid1234”, “Ryan”} ] (7) log를 순회하면서 배열[0]이 (Enter or Leave의 값을 가짐) “Enter”이면 아이디 정보를 가지고 userMap에서 해당 닉네임을 찾아 <닉네임 + “님이 들어왔습니다.”> 문자열을 생성하고, “Leave”이면 <닉네임+”님이 나갔습니다.” 문자열을 생성합니다.
전체 코드는 아래와 같습니다.
public static String[] solution(String[] record) {
Map<String, String> userMap = new HashMap<>();
List<String[]> log = new ArrayList<>();
// (1)
for (String rec : record) {
// (2)
String[] info = rec.split("\\s+");
// (3)
if (info[0].equals("Enter")) {
userMap.put(info[1], info[2]);
log.add(info);
// (4)
} else if (info[0].equals("Leave")) {
log.add(info);
// (5)
} else if (info[0].equals("Change")) {
userMap.put(info[1], info[2]);
}
}
String[] result = new String[log.size()];
int index = 0;
// (6)
for (String[] l : log) {
// (7)
if (l[0].equals("Enter")) {
result[index++] = userMap.get(l[1]) + "님이 들어왔습니다.";
} else if (l[0].equals("Leave")) {
result[index++] = userMap.get(l[1]) + "님이 나갔습니다.";
}
}
return result;
}