백준 7785 회사에 있는 사람 (JAVA 자바 풀이)

백준 7785 회사에 있는 사람 (JAVA 자바 풀이)

 

---

 

 

 

---

💡 잘못된 풀이 

 

 

초기 구현한 코드는 문제의 요구사항을 그대로 따른 코드였다. 

 

1) 입력을 받으면서 

2) 리스트에 직원 객체를 넣는다. 

3) 이때 이미 입력으로 받은 직원이면 상태를 업데이트해주고 

4) 새롭게 들어온 직원이면 객체를 생성해서 넣어준다.

5) 역순으로 정렬하고 

6) 회사에 있는 직원만 출력한다. 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException {

		int memberCounts = Integer.parseInt(bufferedReader.readLine());
		List<Member> members = new ArrayList<>();

		while (memberCounts-- > 0) {
			StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
			String name = stringTokenizer.nextToken();
			String status = stringTokenizer.nextToken();
			members.stream()
				.filter(member -> member.isMe(name))
				.findFirst()
				.ifPresentOrElse(
					member -> member.updateStatus(status),
					() -> members.add(new Member(name, status))
				);
		}

		members.sort(Member::compareTo);
		members.stream().filter(Member::isAtOffice).forEach(System.out::println);
	}

	static class Member implements Comparable<Member>{
		private String name;
		private String status;

		public boolean isMe(String name) {
			return name.equals(this.name);
		}

		public Member(String name, String status) {
			this.name = name;
			this.status = status;
		}

		public void updateStatus(String status) {
			this.status = status;
		}

		public boolean isAtOffice() {
			return status.equals("enter");
		}

		@Override
		public String toString() {
			return name;
		}

		@Override
		public int compareTo(Member that) {
			return that.name.compareTo(this.name);
		}
	}
}

 

 

동명이인이 없고 이름이 전부 다르다는 조건 때문에 아주 쉬운 풀이라고 생각하면서 제출했는데 

 

 

아니나 다를까 역시 이상하게 쉽다고 느낄 때는 이유가 다 있다.

 

처음 시간복잡도를 계산할 때 잘못 계산했던 것이 실수의 이유였다. 

 

입력으로 받는 부분에서 while 반복문으로 n개의 데이터를 처리하는 것을 생략하고 내부 스트림만 고려해서 입력 부분 시간 복잡도를 O(n)으로 생각했었다. 

 

while문이 반복되고 내부에 한번 더 최대 n개의 데이터를 돌리기 때문에 시간 복잡도가 O(n^2)이 되어버린다. 

 

while (memberCounts-- > 0) {
			StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
			String name = stringTokenizer.nextToken();
			String status = stringTokenizer.nextToken();
			members.stream()
				.filter(member -> member.isMe(name))
				.findFirst()
				.ifPresentOrElse(
					member -> member.updateStatus(status),
					() -> members.add(new Member(name, status))
				);
		}

 

총 1,000,000의 데이터이기 때문에 n^2은 1억이며, 백준 기준 1초의 1억 번 연산이면 거의 시간 초과가 난다. 

 

시간 초과가 뜨고 나서 List 구현체를 ArrayList에서 LinkedList로도 바꿔보고, Set으로 변경해 LinkedHashSet으로도 변경해보았지만 전부 시간초과가 떴다. 연산 횟수에서 이미 졌기 때문에 같은 복잡도 내에서의 효율 향상이 아니라 근본적인 개선이 필요했다. 

 

 

 

💡 맞는 풀이

 

우선 이 문제에서는 배열을 사용하기로 했다. 삽입 삭제와 검색 연산이 많이 드는 만큼 상수 시간 내에 접근 가능한 배열이 가장 효율이 좋다고 생각했다. 

 

결국 입력 데이터에서 O(n^2)을 줄여야하는데 방법이 생각이 나지 않아서 고민을 하다가 갑자기 그런 생각이 들었다. 

 

따지고 보면 주어지는 데이터가 출근 아니면 퇴근이므로, 이름이 홀수 번 등장하면 출근, 짝수 번 등장하면 퇴근인 것이다. 이 아이디어로 풀이하면 결과적으로 status 즉, "enter"인지 "leave"인지 조차도 체크해줄 필요가 없어졌다. 

 

객체지향적 코드와 함수형 코드를 바꾸는 게 아쉽지만 이 아이디어를 사용해 풀기로 했다. 

 

역순으로 정렬을 시킨 members 배열에 대해, 각각의 member들을 체크하되 홀수 번 등장할 때만 출력 버퍼에 넣어주는 것이다. 

 

count = 1;
for (int i =1; i< members.length; i++){
   if (members[i].equals(members[i-1]) ) {
      count++;
      continue;
   }
   if(count % 2 !=0){
      stringBuilder.append(members[i-1]).append("\n");
   }
   count =1;
}
if (count%2!=0){
   stringBuilder.append(members[members.length-1]);
}

 

데이터가 정렬이 되어 있기 때문에 앞뒤를 비교하는 것만으로 홀짝 여부를 판단할 수 있다. 

 

배열의 요소를 검사할 때 마지막 항목은 누락이 발생하기 때문에 반복문이 종료되고 한 번 더 검증해준다. 

 

 

 

💡 코드 구현

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Objects;
import java.util.StringTokenizer;

public class Main {

   private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

   public static void main(String[] args) throws IOException {

      int memberCounts = Integer.parseInt(bufferedReader.readLine());

      Member[] members = new Member[memberCounts];
      int count =0;
      while (memberCounts--> 0) {
         StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
         String name = stringTokenizer.nextToken();
         String status = stringTokenizer.nextToken();
         members[count++] = new Member(name, status);
      }

      StringBuilder stringBuilder = new StringBuilder();

      Arrays.sort(members);
      count = 1;
      for (int i =1; i< members.length; i++){
         if (members[i].equals(members[i-1]) ) {
            count++;
            continue;
         }
         if(count % 2 !=0){
            stringBuilder.append(members[i-1]).append("\n");
         }
         count =1;
      }
      if (count%2!=0){
         stringBuilder.append(members[members.length-1]);
      }

      System.out.println(stringBuilder);
   }

   static class Member implements Comparable<Member> {
      private String name;
      private String status;

      public Member(String name, String status) {
         this.name = name;
         this.status = status;
      }
      @Override
      public String toString() {
         return name;
      }

      @Override
      public int compareTo(Member that) {
         return that.name.compareTo(this.name);
      }

      @Override
      public boolean equals(Object o) {
         if (this == o)
            return true;
         if (!(o instanceof Member))
            return false;
         Member member = (Member)o;
         return name.equals(member.name);
      }

      @Override
      public int hashCode() {
         return Objects.hash(name);
      }
   }
}