[boj] 백준 1620

[블로그 이전]

2022.12.05

 

보통은 화가 날때마다 블로그 쓰는편...

🍒1620

https://www.acmicpc.net/problem/1620

처음 봤을 때는 쉬울 줄 알았다. 브루트포스로 했는데 시간초과..가.. 났어....

그래서 생각을 해봤다.

sort 해야되나...

근데 sort해도 별 달라질게 없을 것 같았다.

​

알고리즘을 보니 맵을 쓰라고 한다. 맵이 뭐지?

찾아보니 OS에서 배운 해시테이블 그거다.

​

c++로 작성하기로 바꾸었다. 자료구조는 아래에 들어있다.

#include <map>

중간은 생략하자.

시간초과만 오백번 났다.

---

​

결론적으로 두 가지에서 시간초과를 해결할 수 있었다.

< 1 >

ios::sync_with_stdio(false);  //c와 c++의 동기화를 해제한다. -> 버퍼 수 줄어듬
cin.tie(NULL);                //입력과 출력이 번갈아가며 실행될 때, cin과 cout가 원래 묶여있는데, 이 순서를 해제해준다.
cout.tie(NULL);

첫 번째 줄은 멀티 스레딩 환경이 아닐때는 효과가 없다. 그리고 이걸 쓰면 c 스타일은 사용할 수 없다.

두 번째 줄은 입출력이 번갈아가며 시행될 때만 효과가 있다.

​

< 2 >

endl 대신에 '\n'

endl 은 개행 + FLUSH 로 작동해서 시간이 오래 걸린다.

'\n'​은 개행 만 해주기 때문에 시간 초과를 해결할 수 있다.

​

​

---

내가 시도한 것

1. <map> 대신 <unordered_map> 사용
2. 지역변수를 전역변수로 빼주기
3. tonum()함수 작성했던거 제거하고 stoi() 사용
4. 0~9 사이 비교 대신 isdigit()사용
5. 입력 받을 때마다 출력하지 않고 출력을 한 번에 해주기
6. map 두 개 만들기(하나는 num search, 다른 하나는 name search)
7. 언어 바꾸기 / 변수 / 헤더파일 / 주석 / 인덱스 ...........